算法训练营Day45 第九章 动态规划part7_区间dp 算法训练营

第二题 322. 零钱兑换 

        这道题也是一道完全背包问题，可以认为dp[amount]表示凑成amount所需的最少硬币个数。这道题需要注意的细节如下：因为是要求最少个数，递推公式为：dp[j] = min(dp[j], dp[j - coins[i]] + 1);那么，初始化时，除了dp[0]根据题意应当初始化为0，其余应初始化为INT_MAX,如果初始化为0，那么接下来的推导就全是0了，这是需要注意到的！！！至于遍历顺序，其实先遍历背包还是先遍历物品都是一个效果，因为这道题不是求组合数or排列数。还有就是要注意，当dp[j - coins[i]]为INT_MAX时，不应该再进行比较，此时加1会爆int，直接跳过就好了。

代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);//dp[amount]表示凑成amount所需的最少硬币个数
        dp[0] = 0;
        for(int i = 0; i < coins.size(); i++) {
            for(int j = coins[i]; j <= amount; j++) {
                if(dp[j - coins[i]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

第三题 279.完全平方数

        这道题和上一题基本一样，都是完全背包问题，只需要对递推公式稍加改动即可。在这道题中，我设置dp[0] = 0，完全是为了递推公式。还要将其他初始为INT_MAX，因为我们要求的是最小值。给出代码：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);  //dp[n]表示和为 n 的完全平方数的最少数量
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i * i; j <= n; j++) {
                if(dp[j - i * i] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};

        Day45打卡！