目录322. 零钱兑换动规五部曲279.完全平方数动规五部曲为什么相比上一题不需要if判断139.单词拆分动规五部曲多重背包问题解释代码的改动总结三种背包问题两种递推公式组合数与排列数322. 零钱兑换动规五部曲1.dp[j]的含义是凑齐j所用最少硬币数2.递推公式如果取当前硬币i就需要dp[j-coins[i]]个硬币数再1如果不取当前硬币i(前i-1个硬币就已经凑齐j) dp[j]个硬币二者取最小值故最终递推公式为dp[j]min(dp[j-coins[i]]1, dp[j])3.初始化方式凑齐0元需要0个硬币所以dp[0]0; 其余初始化为最大值否则会无法被递推公式覆盖。4.遍历顺序可以重复取硬币-正序遍历背包求的是硬币最小数所以先物品硬币后背包或者先背包后物品都无所谓class Solution { public: int coinChange(vectorint coins, int amount) { //dp数组dp[j]的含义是凑齐j所用最少硬币数 vectorint dp(amount1, INT_MAX); //初始化凑齐0元需要0个硬币并且其余可初始化为最大值否则会无法被递推公式覆盖。 dp[0] 0; //递推公式如果取当前硬币i就需要dp[j-coins[i]]个硬币数再1 //如果不取当前硬币i(前i-1个硬币就已经凑齐j) dp[j]个硬币二者取最小值 //故最终递推公式为dp[j]min(dp[j-coins[i]]1, dp[j]) //遍历顺序可以重复取硬币-正序遍历背包硬币数和顺序无关所以是组合数所以先硬币后背包 for(int i0;icoins.size();i){ for(int jcoins[i];jamount;j){ if(dp[j-coins[i]]!INT_MAX) dp[j]min(dp[j-coins[i]]1, dp[j]); } } if(dp[amount]INT_MAX) return -1; return dp[amount]; } };279.完全平方数动规五部曲1.dp[j]的含义是dp[j]的含义是凑齐n所用最少完全平方数2.递推公式如果取当前i的平方就需要dp[j-i*i]个完全平方数再1如果不取当前i的平方(前i-1个完全平方数就已经凑齐j)则就是不更新的dp[j]二者取最小值故最终递推公式为dp[j]min(dp[j-coins[i]]1, dp[j])3.初始化方式凑齐0需要0个完全平方数并且其余可初始化为最大值否则会无法被递推公式覆盖。4.遍历顺序可以重复取硬币-正序遍历背包可以重复取完全平方数-正序遍历背包求最小数所以先物品后背包或者先背包后物品都可以为什么相比上一题不需要if判断先背包后物品遍历容量1时只能塞下1所以dp[1]一定是1有了这个基础后面再遍历的时候不需要考虑前面还没有有效值覆盖的情况从而出现INT_MAX先物品后背包遍历平方数1的时候会把所有容量用1填满同样每个值都已经变成了有效值不是INT_MAX了所以可以。注本题一定有结果因为1可以填任意值。class Solution { public: int numSquares(int n) { //dp数组dp[j]的含义是凑齐n所用最少完全平方数 vectorint dp(n1, INT_MAX); //初始化凑齐0需要0个完全平方数并且其余可初始化为最大值否则会无法被递推公式覆盖。 dp[0] 0; //递推公式如果取当前i的平方就需要dp[j-i*i]个完全平方数再1 //如果不取当前i的平方(前i-1个完全平方数就已经凑齐j)则就是不更新的dp[j]二者取最小值 //故最终递推公式为dp[j]min(dp[j-coins[i]]1, dp[j]) //遍历顺序可以重复取完全平方数-正序遍历背包求最小数所以先物品后背包或者先背包后物品都可以 for(int i1;i*in;i){ for(int ji*i;jn;j){ dp[j] min(dp[j - i * i] 1, dp[j]); } } return dp[n]; } };139.单词拆分动规五部曲1.dp[j]的含义是dp[j]的含义是长度为j的字符串是否能被字典中字符串填满2.递推公式如果s[j:i]这个字符子串在字典内并且dp[j]为true则dp[i]为true3.初始化方式dp[0]必须为true否则后面全为false了其余初始值为false否则最后直接输出true了4.遍历顺序可以重复取字符串-正序遍历背包物品的顺序会影响dp值所以是排列数需要先背包后物品注物品是字典中的字符串但需要先匹配上也就是用j遍历到当前容量字符串索引截取i-j长度的子串如果和字典中的某元素能对上则为有效物品可以进行下一步判断(判断dp[j]是否为true)class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring wordSet(wordDict.begin(), wordDict.end()); vectorbool dp(s.size()1, false); dp[0] true; for(int i1;is.size();i){ for(int j0;ji;j){ string str s.substr(j,i-j); if(wordSet.find(str)!wordSet.end() dp[j]) dp[i]true; } } return dp[s.size()]; } };多重背包问题解释有N种物品和一个容量为V 的背包。第i种物品最多有M[i]件可用每件耗费的空间是C[i] 价值是W[i] 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。只要把每种物品的M[i]件展开就可以转化为0-1背包问题代码的改动在0-1背包的先物品后背包倒序的基础上再加一层循环意思是对于第i种物品求放1次、放2次、...、放M[i]次到底放多少次价值最大for(int i 0; i n; i) { // 遍历物品 for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量 // 以上为01背包然后加一个遍历个数 //遍历放入个数时需满足背包容量大于等于k个物品i的重量 for (int k 1; k nums[i] (j - k * weight[i]) 0; k) { // 遍历个数 dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i]); } } }总结三种背包问题0-1背包先物品后背包背包倒序完全背包先物品后背包或先背包后物品或两种都可以背包正序多重背包0-1背包变种同0-1背包两种递推公式最值问题尽量装满背包情况下dp[j] max(dp[j], dp[j - weight[i]] value[i]); //dp[j] min(dp[j], dp[j - weight[i]] value[i]);最多方案数问题dp[j] dp[j - weight[i]];其实不止两种非典型的还有单词拆分这种根据字符子串是否匹配物品和加上新子串前是否为true来推出当前状态的递推方式组合数与排列数组合数先物品后背包-先物品则路径固定排列数先背包后物品-后物品可遍历选择最后一个位置放哪个物品