【代码随想录】刷题笔记Day45

前言

早上又赖了会床......早睡早起是奢望了现在，新一年不能这样！支棱起来！

377. 组合总和 Ⅳ - 力扣（LeetCode）

这一题用的就是完全背包排列数的遍历顺序：先背包再物品，从前往后
求的也是有几种方法，dp[j] += dp[j - nums[i]]; dp[0] = 1
测试用例有坑，dp[j]求和不能超过32位整数范围......

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for(int j = 0; j <= target; j++){  // 遍历背包
            for(int i = 0; i < nums.size(); i++){  // 遍历物品
                if(j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]])  
                // 如果求和大于INT_MAX就不求了
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

322. 零钱兑换 - 力扣（LeetCode）

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
初始化：dp[0] = 0; 其他为INT_MAX
遍历顺序，求最小个数，排列/组合无影响，先物品还是先背包都行
没凑满就用是否是初始值判断，dp[j - coins[i]] 更新过了说明可以凑满

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        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 - coins[i]]是初始值，没凑满，跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

279. 完全平方数 - 力扣（LeetCode）

完全平方数就是硬币，总和n就是背包，求最小值，和上一题类似

// 先背包后物品
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};
// 先物品后背包
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) { // 遍历物品
            for (int j = i * i; j <= n; j++) { // 遍历背包
                dp[j] = min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
};