文章目录

• 题目描述
• 知识点
• 结果
• 实现
• • 码前思考
  • 代码实现
  • 码后反思
• 二刷代码

题目描述

知识点

动态规划之完全背包

结果

实现

码前思考

1. 使用的是完全背包

代码实现

//带输出解决方案数量的充满完全背包问题
class Solution {
public:
    static const int maxa = 5010;
    static const int maxn = 510;
    int dp[maxa];

    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        if(amount==0){
            return 1;
        }
         
        if(n==0){
            return 0;
        }


        fill(dp,dp+maxa,0);
        dp[0]=1;

        for(int i=0;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=dp[j-coins[i]]+dp[j];
                //printf("%d %d %d\n",i,j,dp[j]);
            }
        }

        return dp[amount];
    }
};

码后反思

1. 这道题目有一个注意的地方就是它不是求最值的dp，而是计数型dp；
2. 这里dp[0]要初始化为1，这样才能方便解题！

二刷代码

二刷的时候发现Coin Change2和之前的Coin Change是不同的概念，这里的Coin Change2是完全背包，而Coin Change是单纯的递推型的DP！

这就导致了Coin Change2是绝对不能使用Coin Chage那样使用递推来做的，因为对于测试用例：

3
[1,2]

如果使用递推则是

1->2[[1,1],[2]]
2[[1,1],[2]]->1

这样就重复计算了！！！

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int m = amount;
        int n = coins.size();

        vector<int> dp(m+1,0); //初始化
        dp[0]=1;

        for(int i=1;i<=n;i++){
            for(int j=coins[i-1];j<=m;j++){
                dp[j] = dp[j] + dp[j-coins[i-1]];
            }
        }

        return dp[m];
    }
};