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

2024-01-07 18:20:43

前言

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

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];
        }
    };

后言

  • 今天这几题的递推公式有点感觉了,可惜初始化没想好过不了,继续加油吧~?

文章来源:https://blog.csdn.net/qq_56077562/article/details/135380167
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。