| 问题名称 | 状态定义 | 状态转移方程 | 核心思路 |
|---|---|---|---|
| 1. 最长上升子序列 (LIS) | dp[i] 表示以第 i 个元素结尾的最长上升子序列长度。 |
dp[i] = max(dp[i], dp[j] + 1) for j < i and a[j] < a[i] |
对于每个元素，检查之前所有比它小的元素，取最大值加1。 |
| 2. 最长公共子序列 (LCS) | dp[i][j] 表示字符串 A 前 i 个字符和 B 前 j 个字符的LCS长度。 |
if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) |
字符相等，长度加1；不等，则继承上方或左方的最大值。 |
| 3. 编辑距离 | dp[i][j] 表示将 A 的前 i 个字符转换为 B 的前 j 个字符所需的最少操作数。 |
if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1]else dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 |
分别对应删除、插入、替换操作，取三者最小值加1。 |
| 4. 最大子数组和 | dp[i] 表示以第 i 个元素结尾的最大子数组和。 |
dp[i] = max(nums[i], dp[i-1] + nums[i]) |
当前元素的值，要么自成一派，要么与前面连接起来的和更大。 |
| 5. 爬楼梯问题 | dp[i] 表示到达第 i 阶楼梯的方法数。 |
dp[i] = dp[i-1] + dp[i-2] |
到达当前台阶的方法数等于前两级台阶方法数之和。 |
| 6. 打家劫舍 | dp[i] 表示抢劫前 i 个房屋能获得的最大金额。 |
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) |
当前房屋的最大值是不抢当前（继承i-1）或抢当前（i-2的值加当前金额）的最大值。 |
| 7. 数字三角形 | dp[i][j] 表示从顶点走到第 i 行第 j 列的最大路径和。 |
dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j]) |
当前点的最大值来自上一行左上方或正上方的最大值加上当前点的值。 |
| 8. 最长公共子串 | dp[i][j] 表示以 A[i] 和 B[j] 结尾的公共子串的长度。 |
if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1else dp[i][j] = 0 |
字符相等则长度加1，否则中断归零。注意与LCS的区别。 |
| 9. 最长递增子序列个数 | count[i] 记录以 i 结尾的LIS的个数。 |
当更新 dp[i] 时，若 dp[j]+1 > dp[i]，重置计数；若 dp[j]+1 == dp[i]，累加计数。 |
在LIS的DP基础上，用另一个数组同步记录个数。 |
| 11. 找零钱问题 (最少硬币) | dp[i] 表示凑出金额 i 所需的最少硬币个数。 |
dp[i] = min(dp[i], dp[i - coin] + 1) for coin in coins and coin <= i |
对于金额 i，遍历所有小于等于 i 的硬币面值，选择使用该硬币后所需总硬币数最少的方案。是完全背包的应用。 |
| 12. 找零钱问题 (组合数) | dp[i][j] 表示使用前 i 种硬币凑出金额 j 的方法数。 |
dp[i][j] = dp[i-1][j] + dp[i][j - coin[i]] (当 j >= coin[i]) |
凑出金额 j 的方法数等于不使用第 i 种硬币的方法数，加上使用至少一枚第 i 种硬币的方法数。同样是完全背包思想。 |
| 13. 01背包问题 | dp[i][j] 表示前 i 件物品在背包容量为 j 时能获得的最大价值。 |
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) (当 j >= w[i]) |
每个物品只能选一次。决策是“放”或“不放”第 i 件物品。空间优化后内层循环需逆序遍历容量 j。 |
| 14. 完全背包问题 | dp[i][j] 表示前 i 种物品在背包容量为 j 时能获得的最大价值。 |
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]) (当 j >= w[i]) |
每种物品可选无限次。决策是“不放”第 i 种物品或“至少再放一个”第 i 种物品。空间优化后内层循环需正序遍历容量 j。 |
0 条评论
目前还没有评论...
