代码随想录算法训练营第三十八天|Day38 动态规划

322. 零钱兑换

视频讲解：https://www.bilibili.com/video/BV14K411R7yv

https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

思路

#define min(a, b) ((a) > (b) ? (b) : (a))
int coinChange(int* coins, int coinsSize, int amount) {int* dp = (int*)malloc(sizeof(int) * (amount + 1));for (int j = 0; j < amount + 1; j++) {dp[j] = INT_MAX;}dp[0] = 0;for(int i = 0; i <= amount; i++){for(int j = 0; j < coinsSize; j++){if(i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX){dp[i] = min(dp[i], dp[i - coins[j]] + 1);}}}if(dp[amount] == INT_MAX){return -1;}return dp[amount];
}

学习反思

动态规划解决硬币找零问题的实现。函数coinChange接受三个参数：coins表示可用的硬币面额，coinsSize表示硬币种类数量，amount表示要找零的金额。首先，代码定义了一个大小为(amount + 1)的数组dp，用来保存每个金额所需的最少硬币数。然后将dp数组的所有元素初始化为INT_MAX，表示暂时无法找零。接下来，将dp[0]初始化为0，表示找零金额为0时不需要任何硬币。然后，通过两层嵌套循环遍历所有金额，以及所有硬币面额，计算每个金额所需的最少硬币数。如果当前金额减去某个硬币面额大于等于0，并且之前的金额所需的最少硬币数不等于INT_MAX（表示该金额无法找零），则更新当前金额所需的最少硬币数。这个更新的过程通过min宏来实现，它选择较小的值作为新的最少硬币数。最后，判断最后一个金额所需的最少硬币数是否等于INT_MAX，如果是，则表示无法找零，返回-1；否则，返回最后一个金额所需的最少硬币数。

279.完全平方数

视频讲解：https://www.bilibili.com/video/BV12P411T7Br

https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

思路

​#define min(a, b) ((a) > (b) ? (b) : (a))
int numSquares(int n) {int* dp = (int*)malloc(sizeof(int) * (n + 1));for (int j = 0; j < n + 1; j++) {dp[j] = 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];
}​

学习反思

动态规划解决完全平方数问题的实现。函数numSquares接受一个参数n，表示要判断的数。首先，代码定义了一个大小为(n + 1)的数组dp，用来保存每个数最少需要的完全平方数的个数。然后将dp数组的所有元素初始化为INT_MAX，表示暂时无法求解。接下来，将dp[0]初始化为0，表示数字0不需要任何完全平方数。然后，通过两层嵌套循环遍历所有数字，以及所有完全平方数。如果一个完全平方数的平方小于等于当前数字i，则更新当前数字需要的最少完全平方数个数。更新的过程通过min宏来实现，它选择较小的值作为新的最少完全平方数个数。最后，返回数组dp的最后一个元素，它保存了n所需的最少完全平方数个数。

139.单词拆分

视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh

https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

思路

bool wordBreak(char* s, char** wordDict, int wordDictSize) {int len = strlen(s);    bool dp[len + 1];memset(dp, false, sizeof (dp));dp[0] = true;for (int i = 1; i < len + 1; ++i) {for(int j =  0; j < wordDictSize; j++){int wordLen = strlen(wordDict[j]);int k = i - wordLen;if(k < 0){continue;}dp[i] = (dp[k] && !strncmp(s + k, wordDict[j], wordLen)) || dp[i];}}return dp[len];
}

学习反思 

动态规划解决单词拆分问题的实现。函数wordBreak接受三个参数，分别是字符串s、字符串数组wordDict和wordDict的大小wordDictSize。首先，代码定义了一个长度为len + 1的bool型数组dp，用来保存 s 的前 i 个字符能否被拆分成字典中的单词。然后将dp数组的所有元素初始化为false，表示暂时无法拆分。接下来，将dp[0]初始化为true，表示空字符串可被拆分。然后，通过两层嵌套循环遍历每个字符以及字典中的单词。对于每个字符 i，再内层循环遍历字典中的单词。如果当前字符 i 减去单词长度 wordLen 大于等于 0，并且字典中的单词与 s 中的子串相等，则更新 dp[i] 为 true。这里使用了strncmp函数来比较字符串的子串是否与字典中的单词相等。最后，返回 dp[len]，它表示整个字符串 s 能否被拆分。

背包问题总结篇！

在进行背包问题的时候，我们都是按照如下五部来逐步分析，相信大家也体会到，把这五部都搞透了，算是对动规来理解深入了。

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

其实这五部里哪一步都很关键，但确定递推公式和确定遍历顺序都具有规律性和代表性，所以下面从这两点来对背包问题做一做总结。背包递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

• 动态规划：416.分割等和子集(opens new window)
• 动态规划：1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

• 动态规划：494.目标和(opens new window)
• 动态规划：518. 零钱兑换 II(opens new window)
• 动态规划：377.组合总和Ⅳ(opens new window)
• 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

• 动态规划：474.一和零(opens new window)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

• 动态规划：322.零钱兑换(opens new window)
• 动态规划：279.完全平方数(opens new window)

遍历顺序

01背包

在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

完全背包

说完01背包，再看看完全背包。

在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

相关题目如下：

• 求组合数：动态规划：518.零钱兑换II(opens new window)
• 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

• 求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数(opens new window)

对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。

总结

这篇背包问题总结篇是对背包问题的高度概括，讲最关键的两部：递推公式和遍历顺序，结合力扣上的题目全都抽象出来了。

而且每一个点，都进行了对应的力扣题目。

加油！！！！