代码随想录算法训练营第三十八天|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 能否被拆分。