文章目录【322.零钱兑换】【279.完全平方数】【139.单词拆分】【56.携带矿石资源】【322.零钱兑换】思路重点在dp数组如何初始化首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;其他下标对应的数值呢考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。代码如下vectorintdp(amount1,INT_MAX);dp[0]0;解法classSolution{public:intcoinChange(vectorintcoins,intamount){vectorintdp(amount1,INT_MAX);// dp[i]表示凑成总金额i所需的最少的硬币个数// dp[j] min(dp[j-coins[i]] 1, dp[j])dp[0]0;intresult0;for(inti0;icoins.size();i){for(intjcoins[i];jamount;j){if(dp[j-coins[i]]!INT_MAX){dp[j]min(dp[j],dp[j-coins[i]]1);}}}if(dp[amount]INT_MAX)return-1;returndp[amount];}};【279.完全平方数】思路和上一题完全一样再次强调我们知道这是完全背包如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。解法先遍历背包再遍历物品classSolution{public:intnumSquares(intn){vectorintdp(n1,INT_MAX);// dp[i]表示凑成数i所需要的完全平方数个数// dp[j] min(dp[j-coins[i]] 1, dp[j])dp[0]0;for(inti0;in;i){// 遍历背包for(intj1;j*ji;j){// 遍历物品dp[i]min(dp[i],dp[i-j*j]1);}}returndp[n];}};先遍历物品再遍历背包classSolution{public:intnumSquares(intn){vectorintdp(n1,INT_MAX);// dp[i]表示凑成数i所需要的完全平方数个数// dp[j] min(dp[j-coins[i]] 1, dp[j])dp[0]0;for(inti1;i*in;i){// 遍历物品for(intji*i;jn;j){// 遍历背包dp[j]min(dp[j],dp[j-i*i]1);}}returndp[n];}};【139.单词拆分】思路动规五部曲分析如下确定dp数组以及下标的含义dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。确定递推公式如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。dp数组如何初始化从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。那么dp[0]有没有意义呢dp[0]表示如果字符串为空的话说明出现在字典里。但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。确定遍历顺序题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。还要讨论两层for循环的前后顺序。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。求组合数动态规划518.零钱兑换II 求排列数动态规划377. 组合总和 Ⅳ、动态规划70. 爬楼梯进阶版完全背包 求最小数动态规划322. 零钱兑换、动态规划279.完全平方数而本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。所以说本题一定是先遍历背包再遍历物品。举例推导dp数组classSolution{public:boolwordBreak(string s,vectorstringwordDict){unordered_setstringwordSet(wordDict.begin(),wordDict.end());// 先搞清楚这是一个完全背包问题vectorbooldp(s.size()1,false);dp[0]true;// dp[i]表示字符串长度为i时能否由wordDict组成false表示不能true表示能for(inti1;is.size();i){// 先遍历背包不然不能保证每次都尝试到每个单词其实是求排列数for(intj0;ji;j){string words.substr(j,i-j);if(wordSet.find(word)!wordSet.end()dp[j]){dp[i]true;}// 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。}}returndp[s.size()];}};【56.携带矿石资源】思路多重背包有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。多重背包和01背包是非常像的 为什么和01背包像呢每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。例如背包最大重量为10。物品为重量价值数量物品01152物品13203物品24302问背包能背的物品最大价值是多少和如下情况有区别么重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301毫无区别这就转成了一个01背包问题了且每个物品只用一次。// 超时了#includeiostream#includevectorusingnamespacestd;intmain(){intbagWeight,n;cinbagWeightn;vectorintweight(n,0);vectorintvalue(n,0);vectorintnums(n,0);for(inti0;in;i)cinweight[i];for(inti0;in;i)cinvalue[i];for(inti0;in;i)cinnums[i];for(inti0;in;i){while(nums[i]1){// 物品数量不是一的都展开weight.push_back(weight[i]);value.push_back(value[i]);nums[i]--;// n很大的话一个一个申请vector扩容会超时}}vectorintdp(bagWeight1,0);for(inti0;iweight.size();i){// 遍历物品注意此时的物品数量不是nfor(intjbagWeight;jweight[i];j--){// 遍历背包容量dp[j]max(dp[j],dp[j-weight[i]]value[i]);}}coutdp[bagWeight]endl;}另一种实现方式就是把每种商品遍历的个数放在01背包里面在遍历一遍。解法#includeiostream#includevectorusingnamespacestd;intmain(){intbagwWeight,n;cinbagwWeightn;vectorintweight(n,0);vectorintvalue(n,0);vectorintnums(n,0);for(inti0;in;i)cinweight[i];for(inti0;in;i)cinvalue[i];for(inti0;in;i)cinnums[i];vectorintdp(bagwWeight1,0);for(inti0;in;i){// 遍历物品for(intjbagwWeight;jweight[i];j--){// 遍历背包容量// 以上为01背包加一个遍历个数for(intk1;knums[i](j-k*weight[i])0;k){dp[j]max(dp[j],dp[j-k*weight[i]]k*value[i]);}}}coutdp[bagwWeight]endl;}