代码随想录算法训练营Day33| LeetCode 322 零钱兑换、279 完全平方数、139 ...

力扣 322 零钱兑换

本问题是一个组合问题，目标是获得硬币更少的找零方案。这里初始化必要设置为INT_MAX ，循环中用min来更新数组。同时开始前需将dp[0]标记为0，即最少利用0个硬币即可得到数额0。团体代码如下：

1. class Solution {
2. public:
3.     int coinChange(vector<int>& coins, int amount) {
4.         vector<int> dp(amount + 1, INT_MAX);
5.         dp[0] = 0;
6.         for(int i = 0; i < coins.size(); i++){
7.             for(int j = coins[i]; j <= amount; j++){
8.                 if (dp[j - coins[i]] != INT_MAX){
9.                     dp[j] = min(dp[j], dp[j - coins[i]] + 1);
10.                 }
11.             }
12.         }
13.         return dp[amount] == INT_MAX ? -1 : dp[amount];
14.     }
15. };

复制代码

还有一点，INT_MAX + 1 会溢出为负数，导致 min(dp[j], dp[j - coins] + 1) 出错。因此保险起见，循环中必要加上 if 防止溢出。
力扣 279 完全平方数 AC

第一遍ac代码如下：

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         int m = sqrt(n);
5.         vector<int> dp(n + 1);
6.         for(int j = 0; j <= n; j++){
7.             dp[j] = j;
8.         }
9.         for(int i = 2; i <= m; i++){
10.             for(int j = i * i; j <= n; j++){
11.                 dp[j] = min(dp[j], dp[j - i * i] + 1);
12.             }
13.         }
14.         return dp[n];
15.     }
16. };

复制代码

后发现因为最小值是1，所以无需额外初始化，可以放到团体的遍历过程里：

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         int m = sqrt(n);
5.         vector<int> dp(n + 1, INT_MAX);
6.         dp[0] = 0;
7.         for(int i = 1; i <= m; i++){
8.             for(int j = i * i; j <= n; j++){
9.                 dp[j] = min(dp[j], dp[j - i * i] + 1);
10.             }
11.         }
12.         return dp[n];
13.     }
14. };

复制代码

这里在更新第一个物品                                              1                            2                                       1^2                  12 的时间就已经把全部dp[j]初始化了，所以无需进一步担心循环中可能有INT_MAX + 1溢出的问题，没加额外判断。
力扣 139 单词拆分

定义dp数组：dp[j] 表示字符串长度为j时，假如可以拆分为字典里的一个或者多个词汇，那么记为true。本题本质上是分列，因此外层遍历背包，内层遍历物品。但对于本题，内层循环的写法稍有差别，它尝试把                                    [                         0                         ，                         j                         −                         1                         ]                              [0，j-1]                  [0，j−1] 拆成两部门举行判断：

• 前半部门                                         [                            0                            ,                            i                            −                            1                            ]                                  [0,i-1]                     [0,i−1] 是否可拆 ，这里利用 dp 判断。
  
• 后半部门                                         [                            i                            ,                            j                            −                            1                            ]                                  [i,j-1]                     [i,j−1] 是否在字典中，即i是否为最后一个单词的起点。
  

相当于dp是一个已知状态，它表示前i个字符是否可以拆分，而dp[j]是一个待判断的新状态，我们正在尝试dp用来更新它。代码如下：

1. class Solution {
2. public:
3.     bool wordBreak(string s, vector<string>& wordDict) {
4.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
5.         vector<bool> dp(s.size() + 1, false);
6.         dp[0] = true;
7.         for(int j = 1; j <= s.size(); j++){
8.             for(int i = 0; i < j; i++){
9.                 string word = s.substr(i, j - i);
10.                 if(wordSet.find(word) != wordSet.end() && dp[i]){
11.                     dp[j] = true;
12.                 }
13.             }
14.         }
15.         return dp[s.size()];
16.     }
17. };

复制代码

多重背包问题

给定一个容量为 W 的背包，和 N 种物品。每种物品有：

• 一个重量 weight
  
• 一个价值 value
  
• 最多可用的数量 count
  

要求在不超过背包容量 W 的前提下，选择若干物品放入背包，使得物品的总价值最大。
但事实上这里把count摊开又是一个0-1背包问题了：

1. int multipleKnapsack(int bagSize, const vector<int>& weight, const vector<int>& value, const vector<int>& count) {
2.     vector<int> newWeight;
3.     vector<int> newValue;
5.     // 把每个带数量限制的物品拆分成多个 0-1 背包物品
6.     for (int i = 0; i < weight.size(); i++) {
7.         for (int k = 0; k < count[i]; k++) {
8.             newWeight.push_back(weight[i]);
9.             newValue.push_back(value[i]);
10.         }
11.     }
13.     // 经典 0-1 背包（滚动数组）
14.     vector<int> dp(bagSize + 1, 0);
15.     for (int i = 0; i < newWeight.size(); i++) {
16.         for (int j = bagSize; j >= newWeight[i]; j--) {
17.             dp[j] = max(dp[j], dp[j - newWeight[i]] + newValue[i]);
18.         }
19.     }
21.     r

复制代码

背包问题总结

到这里背包问题基本竣事，总结一下碰到题型（cr. 代码随想录）：
问题范例状态转移公式LeetCode 例题说明✅ 是否能装满背包（或是最多能装多少）dp[j] = max(dp[j], dp[j - nums] + nums)416. 分割等和子集 1049. 最后一块石头的重量 II转换成是否存在子集使和为 target✅ 装满背包的方案数（组合or分列）dp[j] += dp[j - nums]494. 目标和 518. 零钱兑换 II 377. 组合总和 IV 70. 爬楼梯（完全背包）问方案个数，利用 += 叠加方案数，常用于分列/组合问题✅ 装满背包的最大价值（最优解）dp[j] = max(dp[j], dp[j - weight] + value)474. 一和零标准的 0-1 / 完全 / 多重背包结构，求最大价值✅ 装满背包所需的最小物品数（最优解）dp[j] = min(dp[j], dp[j - coins] + 1)322. 零钱兑换 279. 完全平方数用最少物品凑出目标
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。