手机网站底部固定菜单,百度搜索工具,搭建是什么意思,网站联系方式要素题目#xff1a;322.零钱兑换 279.完全平方数 139.单词拆分 多重背包 背包总结
需要重做#xff1a;322#xff0c;139 322. 零钱兑换 思路#xff1a;零钱#xff0c;可取多次-》完全背包。 注意#xff1a; 五部#xff1a; 1.dp[j]:价值为j的时候#xff0c;最…题目322.零钱兑换 279.完全平方数 139.单词拆分 多重背包 背包总结
需要重做322139 322. 零钱兑换 思路零钱可取多次-》完全背包。 注意 五部 1.dp[j]:价值为j的时候最少需要几个coin 2.dp[j]min(dp[j],dp[j-coins[i]]1) 3.由递推式可知0一定是0其余的必须是INT——MAX或者根据题目要求的大的数才能保证后面的不被0覆盖而是由推出来的赋值的 4.先物品后bagsize 代码 class Solution {
public:int coinChange(vectorint coins, int amount) {int ncoins.size();vectorintdp(amount1,10001);dp[0]0;//初始化dp[0]为0即可。for(int i0;in;i){for(int j0;jamount;j){if(jcoins[i])dp[j]min(dp[j],dp[j-coins[i]]1);}}if(dp[amount]10001amount!0)return -1;else return dp[amount]; }
}; 279.完全平方数 思路跟上题的思路类似但是初始化的时候有点不一样。以下给出两种解法 注意初始化需要推导 五部 1.dp[j]:总价值为j我最少要多少个数 2.dp[j]min(dp[j],dp[j-val[i]]1);(代码1需要多一条特殊情况) 3.代码1 2给出两种 4.先val再bagsize或者先bagsize后val都行 代码1初始化dp[0]不初始化单独列出 class Solution {
public:int numSquares(int n) {int val[102]{0};for(int i0;i101;i){val[i]i*i;}vectorintdp(n1,10001);dp[1]1;for(int i1;val[i]n;i){for(int jval[i];jn;j){dp[j]min(dp[j],dp[j-val[i]]1);if(jval[i])dp[j]min(dp[j],1);}}return dp[n];}
}; 代码2初始化dp[0]0,无意义但是写法能统一 class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 1; i * i n; i) { // 遍历物品for (int j i * i; j n; j) { // 遍历背包dp[j] min(dp[j - i * i] 1, dp[j]);}}return dp[n];}
};139.单词拆分 思路可以想到回溯但是回溯对于字符串的处理复杂且不充分剪枝会超时考虑dp。 将字符串里不同的单词看作物品将整个字符串看作bagsize 注意 五部 1.dp[j]:该字符串长度为j的时候是否可以由字典的词组成 2.记 ij 如果i是true且i到j在字典里则j为true 3.初始化dp[0]true,其余为false 4.一定要先bagsize后物品因为有要求顺序是排列 代码 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {int bagsizes.size();int nwordDict.size();vectorintdp(bagsize1,0);dp[0]1;unordered_setstringwordSet(wordDict.begin(),wordDict.end());for(int j1;jbagsize;j){//先遍历背包容量for(int i0;ij;i){//再遍历背包的所有物品string words.substr(i,j-i);if(wordSet.find(word)!wordSet.end()dp[i]){dp[j]1;}}}return dp[bagsize];}
}; 关于多重背包你该了解这些 有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。 每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。 所以多重背包本质上是01背包 #includeiostream
#includevector
using namespace std;
int main(){int c,n;cincn;vectorintweight(n,0);vectorintval(n,0);vectorintnum(n,0);for(int i0;in;i)cinweight[i];for(int i0;in;i)cinval[i];for(int i0;in;i)cinnum[i];vectorintdp(c1,0);for(int i0;in;i){//遍历物品for(int jc;jweight[i];j--){//j为背包容量for(int k1;knum[i]jk*weight[i];k){//遍历个数dp[j]max(dp[j],dp[j-k*weight[i]]k*val[i]);}}}coutdp[c];
} 背包问题总结篇摘自代码随想录 五部 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导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) 对于背包问题其实递推公式算是容易的难是难在遍历顺序上如果把遍历顺序搞透才算是真正理解了。 #总结 这篇背包问题总结篇是对背包问题的高度概括讲最关键的两部递推公式和遍历顺序结合力扣上的题目全都抽象出来了。 而且每一个点我都给出了对应的力扣题目。 最后如果你想了解多重背包可以看这篇动态规划关于多重背包你该了解这些 (opens new window)力扣上还没有多重背包的题目也不是面试考察的重点。
