全局变量定义#include iostream #include stdbool.h using namespace std; // 全局变量区 int count 0; // 用于“目标和”记录回溯的组合数量 bool istrue false; // 用于“单词拆分”记录回溯是否成功找到拆分方案一、最后一块石头的重量 II思路这道题是 0-1 背包的变体。将石头分成重量尽可能相近的两堆其实就是找最接近总和一半的元素组合。计算所有石头的总和sum目标容量设为target sum / 2。在容量为target的背包中最多能装多少重量的石头剩下的重量就是sum - dp[target] - dp[target]。代码int lastStoneWeightII(int stone[], int size) { int sum 0; // 就是找最接近总和一半的元素和与总和一半的差 for (int i 0; i size; i) sum stone[i]; int target sum / 2; int dp[target 1]; for (int j 0; j target; j) dp[j] 0; // 0-1 背包先遍历物品再倒序遍历容量 for (int i 0; i size; i) { for (int j target; j stone[i]; j--) { dp[j] getmax(dp[j], dp[j - stone[i]] stone[i]); } } return sum - 2 * dp[target]; }关键点① 容量遍历必须是倒序这是 0-1 背包保证物品只被使用一次的核心规律。二、目标和思路计算所有数字的和sum将sum与target相加除以 2得到的数字就是我们要凑出的容量targetpro。问题转化为去 nums 里找有哪些组合可以相加得到这个数。这里分别用回溯法暴力求解和动态规划0-1 背包方案数实现。代码// 1. 回溯法 void findTargetSumWaysback(int nums[], int targetpro, int nowsum, int start, int size) { if (nowsum targetpro) { count; // 这里不能 return因为后面可能有 0 元素 } for (int i start; i size; i) { nowsum nums[i]; findTargetSumWaysback(nums, targetpro, nowsum, i 1, size); nowsum - nums[i]; // 回溯 } } // 2. 动态规划 int findTargetSumWayss(int nums[], int size, int target) { int sum 0; for (int i 0; i size; i) sum nums[i]; // 如果 target 绝对值过大或无法整除直接无解 if ((target sum) % 2 1) return 0; int targetpro (target sum) / 2; int dp[targetpro 1]; // dp[i] 表示要满足和为 i有 dp[i] 种方法 for (int i 0; i targetpro; i) dp[i] 0; dp[0] 1; // 关键什么都不装就是一种方法 for (int i 0; i size; i) { // 遍历物品 for (int j targetpro; j nums[i]; j--) { // 倒序遍历容量 // 递推公式当前容量的方法数 不放当前数的方法数 放了当前数的方法数 dp[j] dp[j - nums[i]]; } } return dp[targetpro]; } // 主函数入口 int findTargetSumWays(int nums[], int size, int target) { int sum 0; for (int i 0; i size; i) sum nums[i]; int targetpro (target sum) / 2; count 0; // 全局变量重置 findTargetSumWaysback(nums, targetpro, 0, 0, size); return count; }提问Q1为什么dp[0]必须初始化为 1A因为在求方案数的递推公式中所有的数值都是靠前面的数值累加起来的。如果dp[0] 0那整张表就永远都是 0dp[0] 1是整张 DP 表的“火种”。三、一和零思路这是二维空间的 0-1 背包。物品是字符串它消耗的不仅是“重量”而是“0 的个数”和“1 的个数”两个维度的容量。背包的价值就是物品的个数加 1代码int findMaxForm(char** strs, int strssize, int m, int n) { int dp[m 1][n 1]; // dp[i][j] 表示最多有 i 个 0 和 j 个 1 的最大子集 int numof0[strssize]; int numof1[strssize]; for (int i 0; i m; i) { for (int j 0; j n; j) dp[i][j] 0; } for (int i 0; i strssize; i) { numof0[i] 0; numof1[i] 0; // 初始化 } for (int i 0; i strssize; i) { for (int j 0; strs[i][j] ! \0; j) { if (strs[i][j] 0) numof0[i]; else numof1[i]; // 统计各字符串 0 和 1 数量 } } for (int k 0; k strssize; k) { for (int i m; i numof0[k]; i--) { // 倒序 for (int j n; j numof1[k]; j--) { // 倒序 dp[i][j] getmax(dp[i][j], dp[i - numof0[k]][j - numof1[k]] 1); } } } return dp[m][n]; }关键点① 双重维度的背包内层的两个容量循环都必须严格遵守倒序遍历四、零钱兑换 II思路求凑成金额 $j$ 的组合数由于硬币可以无限次使用这是完全背包问题。要注意本题求的是组合数不强调顺序所以遍历顺序非常关键。代码// 一维优化版本 int change(int amount, int coins[], int coinsSize) { int dp[amount 1]; for (int j 0; j amount; j) dp[j] 0; dp[0] 1; // 初始化所有金额方法数设为 0但金额 0 的方法数为 1 // 完全背包求组合数核心先遍历物品再正序遍历容量 for (int i 0; i coinsSize; i) { for (int j coins[i]; j amount; j) { // 递推公式当前方法数 原有的方法数 放入当前硬币后的新方法数 dp[j] dp[j - coins[i]]; } } return dp[amount]; } // 二维原理解析版本 int changee(int amount, int* coins, int coinsSize) { long long dp[coinsSize 1][amount 1]; //定义dp[i][j] 表示使用前 i 个硬币凑成金额 j 的组合数 // 为了方便理解我们将行开大一位i0 代表不使用任何硬币 for (int i 0; i coinsSize; i) { for (int j 0; j amount; j) dp[i][j] 0; } for (int i 0; i coinsSize; i) dp[i][0] 1; // // 凑成金额 0 的方法只有 1 种什么都不放 for (int i 0; i coinsSize; i) { // 已修复 i 的初始化 for (int j 0; j amount; j) { if (j coins[i]) dp[i][j] dp[i][j - coins[i]]; // 完全背包本行累加 else dp[i][j] dp[i - 1][j]; } } return dp[coinsSize][amount]; }提问Q1为什么完全背包的内层循环是正序A0-1 背包倒序是为了防止物品被重复放入。完全背包的特性就是物品可以无限使用正序遍历使得dp[j]可以直接利用本轮刚刚更新过的dp[j - coins[i]]即已经放过该物品的状态从而实现无限次放取五、组合总和 IV思路求凑成target的方案数。注意本题{1, 2}和{2, 1}算作两种不同的方案。这说明它本质上是一个求排列数的完全背包问题。代码int combinationSum4(int* nums, int size, int target) { int dp[target1];//dpi表示能凑成i的组合的个数 for(int i 0;itarget;i) dp[i]0; dp[0]1;//注意遍历顺序先遍历物品再遍历背包就是组合先遍历背包再遍历物品就是排列 for(int j 1;jtarget;j) { for(int i 0;isize;i) { if(nums[i]j) dp[j]dp[j-nums[i]]; } } return dp[target]; }关键点① 求组合先遍历物品后遍历背包。② 求排列先遍历背包后遍历物品。对于每个容量把所有物品都尝试一遍产生不同顺序的排列。六、爬楼梯进阶版思路一步可以爬 1 到 m 阶。总容量是 n物品是1 - m。先爬 1 阶再爬 2 阶和先爬 2 阶再爬 1 阶是不同的方法因此这也是完全背包求排列数的问题。代码int climb(int n, int m) { int dp[n 1]; for (int i 0; i n; i) dp[i] 0; dp[0] 1; // 排列问题先背包再台阶 for (int j 1; j n; j) { for (int i 1; i m; i) { if (j i) { dp[j] dp[j - i]; } } } return dp[n]; }七、零钱兑换思路求凑满金额所需的最少硬币数。这是完全背包的求最值问题。因为只关心个数不关心顺序所以两层循环的先后顺序无所谓。代码int coinChange(int* coins, int size, int amount) { if (amount 0) return 0; if (amount 0) return -1; int dp[amount 1]; //dpi表示i金额最少硬币数 for (int i 0; i amount; i) dp[i] amount 1; // 必须用 amount 1 代表无穷大 dp[0] 0; // 凑齐 0 需要 0 个 for (int j 1; j amount; j) { for (int i 0; i size; i) { // 求最值顺序不重要 if (j coins[i]) { dp[j] getmin(dp[j], dp[j - coins[i]] 1); } } } if (dp[amount] amount 1) return -1; else return dp[amount]; }关键点① 初始值绝对不能设为 0。为了防止加 1 后发生整型溢出通常使用amount 1来代替理论上的“无穷大”。八、完全平方数思路与零钱兑换如出一辙。背包容量是n隐含的物品是完全平方数1, 4, 9, 16...。依然是完全背包求最小个数。代码int numSquares(int n) { int dp[n 1]; for (int i 0; i n; i) dp[i] n 1; dp[0] 0; dp[1] 1; for (int j 2; j n; j) { // 内层循环边界优化物品的重量不能超过背包总容量 j for (int i 1; i * i j; i) { if (j i * i) { dp[j] getmin(dp[j], dp[j - i * i] 1); } } } return dp[n]; }九、单词拆分回溯法思路尝试在字符串中切出一段如果能在字典里找到就递归处理剩下的部分。千万不要在外层套一个for(int i start; s[i]; i)这会允许程序跳过无法匹配的字符。必须固定start去匹配。代码void wordBreakback(char *s,char **wordDict,int wordDictSize,int start) { if(s[start]\0) { istrue true; return ; } //固定start去找 for(int j0;jwordDictSize;j) { int k 0; for( k 0;wordDict[j][k]!\0;k) { if(s[startk]!wordDict[j][k]) break; } if(wordDict[j][k]\0) { wordBreakback(s,wordDict,wordDictSize,startk); } } } bool wordBreak(char* s, char** wordDict, int wordDictSize) { wordBreakback(s,wordDict,wordDictSize,0); return istrue; } //如果递归逻辑的循环外层套一个i从start开始像以前那样遍历i会导致如下问题 /* 以 catsandog 为例的逻辑车祸现场 输入s catsandog, wordDict [cats, dog, sand, and, cat] start 0。i 从 0 开始。 匹配到 catsa 变成 4。进入递归 wordBreakback(s, ..., 4)。 在下一层递归中start 4此时面对的是 andog。 假设 and 在字典里。你的 i 会从 4 遍历到 6。 当 i 4 时匹配到 anda 变成 7。进入递归 wordBreakback(s, ..., 7)面对 og。 在 start 7 这一层没有任何单词能匹配 og。 高能预警 此时递归回溯到 start 4 这一层i 继续循环变成 5 如果字典里有 dog你的代码会尝试从 s[5]即字母 n或者从 s[6]即字母 d开始匹配。 由于 s[6] 开始正好是 dog你的代码会匹配成功并调用 wordBreakback(s, ..., 9)。 到达末尾返回 true*/提问Q1以catsandog为例如果你加了外层的i循环会发生什么样的逻辑车祸A匹配完cats后面对andog。此时字典里没有单词能匹配andog。但是外层循环会让i增加跳过an直接从字母d开始匹配。由于字典里有dog程序匹配成功并返回true完美忽视了被跳过的an