C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-02-20

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        // write code here
        vector<int> dp(target+1);
        dp[0] = 1;
        for(int i = 0; i < nums.size(); i++){
            for(int j = nums[i]; j <= target; j++){
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-05-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        // write code here
        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];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        // write code here
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int& coin : nums) {
            for (int i = coin; i <= target; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[target];
        
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-07-26

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        // write code here
        		vector<int> dp(target + 1, 0);
		dp[0] = 1;
		for (int coin : nums) {
			for (int i = coin; i <= target; i++) {
				dp[i] += dp[i - coin];
			}
		}

		return dp[target];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-02-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) {
        // write code here
        vector<int>dp(target+1);
        dp[0] = 1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j = nums[i];j<=target;j++)
            {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
        
        
    }
};