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

时间复杂度O(nm), 空间复杂度O(nm)。考虑使用滚动数组思想，可以将空间复杂度优化到O(m)

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        int n = nums.size();
        // dp[i][j]表示：在num数组的前i个元素中选择，可以凑成j的组合数
        vector<vector<int>> dp(n+1, vector<int>(target+1));
        // 初始化状态
        for(int i=0; i<=n; ++i) dp[i][0] = 1;

        for(int i=1; i<=n; ++i){
            for(int j=1; j<=target; ++j){
                // 如果前i-1个元素中有组成j，那么也属于前i个元素中组成j
                dp[i][j] = dp[i-1][j];
                // 考虑使用当前第i个元素，那么之前选择的元素只能组成j-nums[i-1]，这样加上当前第i个元素nums[i-1]后才能组成j
                if(nums[i-1] <= j){
                    dp[i][j] += dp[i][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
};