自学内容网 自学内容网

代码随想录算法训练营第三十八天|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]); ,对应题目如下:

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

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

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

遍历顺序

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循环遍历物品

相关题目如下:

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

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

总结

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

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

加油!!!!


原文地址:https://blog.csdn.net/a6666999d/article/details/143576785

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!