背包总结
从以下几个方面来理解背包问题
- 遍历顺序： 明确是先遍历物品，还是先遍历背包。
- DP 维度： 区分使用一维数组和二维数组时的情况。
- 遍历方向： 明确在一维 DP 数组中，背包容量是正向遍历还是反向遍历。
- 复杂度： 在每种情况下都给出明确的时间和空间复杂度。
- 题目描述： 对每个题目进行简短描述
- DP转化思想： 说明如何将问题转化为背包问题
一、 01背包问题及应用 (细化)
| 题目/应用 | 所属类型 | DP数组维度 | 物品遍历顺序 | 背包遍历顺序 | 核心思想/DP状态 | 状态转移方程 (C++代码) | 题目描述 | DP转化思想 |
|---|---|---|---|---|---|---|---|---|
| 46. 携带研究材料 | 01背包 | 一维 dp[j] | 先物品 (for i from 1 to N) | 后背包 (逆序) (for j from V down to w[i]) | dp[j] 表示容量为j时能获得的最大价值。逆序遍历保证每个物品只被选择一次。 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); | 给定物品重量和价值，求不超过容量限制的最大价值 | 每个物品选或不选，价值最大化 |
| 416. 分割等和子集 | 01背包 | 一维 dp[j] | 先物品 (for num in nums) | 后背包 (逆序) (for j from target down to num) | dp[j] 表示容量为j是否可达。 | dp[j] = dp[j] || dp[j-num]; | 判断数组是否能分成两个和相等的子集 | 背包容量为sum/2，物品重量和价值均为nums[i] |
| 474. 一和零 | 二维费用01背包 | 二维 dp[j0][j1] | 先物品 (for s in strs) | 后背包 (逆序) (for j0 from m down to c0, for j1 from n down to c1) | dp[j0][j1] 表示用j0个0和j1个1能组成的最大字符串数。 | dp[j0][j1] = max(dp[j0][j1], dp[j0-c0][j1-c1]+1); | 给定二进制字符串数组，求最多m个0和n个1的最大子集 | 二维背包问题，两个容量限制 |
| 494. 目标和 | 01背包 | 一维 dp[j] | 先物品 (for num in nums) | 后背包 (逆序) (for j from target down to num) | dp[j] 表示和为j的方案数。 | dp[j] += dp[j-num]; | 给数组元素添加+/-号使表达式结果等于target | 正子集和负子集的和差为target |
| 1049. 最后一块石头的重量 II | 01背包 | 一维 dp[j] | 先物品 (for w in stones) | 后背包 (逆序) (for j from target down to w) | dp[j]表示容量为j时能达到的最大重量。 | dp[j] = max(dp[j], dp[j-w] + w); | 石头两两相撞，求最后剩余最小重量 | 分成两堆石头使重量差最小 |
二、 完全背包问题及应用 (细化)
| 题目/应用 | 所属类型 | DP数组维度 | 物品遍历顺序 | 背包遍历顺序 | 核心思想/DP状态 | 状态转移方程 (C++代码) | 题目描述 | DP转化思想 |
|---|---|---|---|---|---|---|---|---|
| 52. 携带研究材料 | 完全背包 | 一维 dp[j] | 先物品 (for i from 1 to N) | 后背包 (顺序) (for j from w[i] to V) | dp[j] 表示容量为j时能获得的最大价值。顺序遍历保证物品可以被重复选择。 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); | 物品可以无限取用，求最大价值 | 完全背包问题，物品可重复选择 |
| 70. 爬楼梯 | 完全背包 | 一维 dp[j] | 先物品 (for step in [1,2]) | 后背包 (顺序) (for j from 1 to n) | dp[j] 表示爬到j级台阶的方案数。 | dp[j] += dp[j-step]; | 每次可以爬1或2阶，求到n阶的方法数 | 台阶数为背包容量，步数为物品 |
| 322. 零钱兑换 | 完全背包 | 一维 dp[j] | 先物品 (for c in coins) | 后背包 (顺序) (for j from c to amount) | dp[j] 表示凑成金额j所需的最少硬币数。 | dp[j] = min(dp[j], dp[j-c] + 1); | 用最少数量的硬币凑成指定金额 | 硬币无限使用，求最小数量 |
| 279. 完全平方数 | 完全背包 | 一维 dp[j] | 先物品 (for i from 1 to sqrt(n)) | 后背包 (顺序) (for j from i*i to n) | dp[j] 表示和为j的完全平方数的最少数量。 | dp[j] = min(dp[j], dp[j-i*i] + 1); | 求最少完全平方数使其和等于n | 平方数可重复使用，求最小数量 |
| 518. 零钱兑换 II | 完全背包 | 一维 dp[j] | 先物品 (for c in coins) | 后背包 (顺序) (for j from c to amount) | dp[j] 表示凑成金额j的组合数。 | dp[j] += dp[j-c]; | 计算可以凑成总金额的硬币组合数 | 完全背包求组合数 |
| 377. 组合总和 IV | 完全背包 | 一维 dp[j] | 先背包 (for j from 1 to target) | 后物品 (for c in nums) | dp[j] 表示凑成金额j的排列数。 | dp[j] += dp[j-c]; | 计算可以凑成总金额的排列数 | 完全背包求排列数(顺序不同视为不同组合) |
三、 多重背包问题及应用 (细化)
| 题目/应用 | 所属类型 | DP数组维度 | 物品遍历顺序 | 背包遍历顺序 | 核心思想/DP状态 | 状态转移方程 (C++代码) | 题目描述 | DP转化思想 |
|---|---|---|---|---|---|---|---|---|
| 56. 携带矿石 | 多重背包 | 一维 dp[j] | 先物品 (for i from 1 to N) | 后背包 (逆序) (for j from V down to w) | 通过二进制拆分将物品转换为01背包问题，然后应用01背包解法。 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); | 每种物品有数量限制，求最大价值 | 多重背包转换为01背包 |
四、 其他动态规划问题 (非背包)
| 题目/应用 | 所属类型 | DP数组维度 | 遍历顺序 | 核心思想/DP状态 | 状态转移方程 (C++代码) |
|---|---|---|---|---|---|
| 300. 最长上升子序列 | 子序列DP | 一维 dp[i] | 先数组 (for i from 0 to N-1) | dp[i] 表示以nums[i]结尾的最长上升子序列的长度。 | `dp[i] = 1 + max({dp[j] |
| 1143. 最长公共子序列 | 字符串DP | 二维 dp[i][j] | 先text1 (for i from 1 to L1)后 text2 (for j from 1 to L2) | dp[i][j] 表示text1前i个字符和text2前j个字符的最长公共子序列长度。 | if(t1[i-1]==t2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); |
| 72. 编辑距离 | 字符串DP | 二维 dp[i][j] | 先word1 (for i from 1 to L1)后 word2 (for j from 1 to L2) | dp[i][j] 表示word1前i个字符和word2前j个字符的编辑距离。 | if(w1[i-1]==w2[j-1]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}); |
| 121. 买卖股票的最佳时机 | 股票DP | 一维 (不需DP数组) | 先数组 (for price in prices) | 维护min_price和max_profit两个变量。 | max_profit = max(max_profit, price - min_price);min_price = min(min_price, price); |
| 139. 单词拆分 | 字符串DP | 一维 dp[i] | 先背包 (for i from 1 to s.size()) | 后物品 (for word in wordDict) | dp[i] 表示s前i个字符能否被wordDict中的单词拆分。 |