题解 | #兑换零钱(二)#

#include <vector>
class Solution {
public:
    //完全背包-种数-组合数
    //dp[j]：总金额为j，在nums存储的硬币面额中，有dp[j]种 组合 方式。
    //递推公式：求种数的问题，递推公式为dp[j]=dp[j] + dp[j-num[i] ]。原因详见代码随想录的“目标和”章节。
    //遍历顺序：外层物品，内层容量。如果内层是物品的话，会导致变成排列。由于是完全背包，物品可以重复使用，因此内层容量为正遍历。
    //初始化：dp[0]=1，目的是点燃“原初之火”，而其他都初始化为0，否则在递推的过程中会被反复叠加。
    //举例：5,[1,2,4,5]
    //物品1：dp=1，
    int change(int target, vector<int>& nums) {
        vector<int>dp(target+1,0);
        dp[0]=1;
        for(auto num:nums)
        {
            for(int j=num;j<dp.size();j++)//背包体积如果比当前物品小那就压根不用遍历了。
            {
                dp[j]+=dp[j-num];
            }
        }
        return dp[target];
    }
};