题解 | #兑换零钱(二)#动态规划解法

时间复杂度：O(mn)，空间复杂度：O(n)

可以把总金额看做背包的容量，把不同面值的硬币看做待装的物品，因为凑出总金额的组合与顺序无关，即(1,2)和(2,1)凑出3属于同一种情况，所以该问题可以看做是完全背包问题的变种。本解法基于读者已经对背包问题有了一定程度的了解，所以给出的是经过了一维优化的代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        vector<int> dp(target + 1, 0); // 每一种可能的剩余金额都初始化为0种组合
        dp[0] = 1; // 当剩余金额为0时，说明已经凑出一种组合
        // 遍历每一种硬币，开始填表
        for (const auto& v : nums) {
            // 从小到大遍历每一种剩余金额，从v开始的原因是，当剩余金额小于当前硬币的
            // 面值时，其现有组合数不发生变化
            for (int i = v; i <= target; ++i) {
                // 1. dp[i]表示当前硬币v一个都不含时，靠之前的硬币凑出金额i的组合数
                // 2. dp[i-v]表示当前硬币v至少含一个时，靠之前的硬币和当前硬币v共同
                // 凑出剩余金额i-v的组合数
                // 显然1,2两种情况互为补集，其和，就是只考虑到当前硬币v为止，凑出总金
                // 额i的所有组合数，理解不了的同学可以多看看完全背包的一维优化内容
                dp[i] += dp[i - v];
            }
        }
        return dp[target];
    }
};