CSP-J 动态规划互动训练
用 CSP-J 常见模型练习动态规划:先定义状态,再找转移,最后按正确顺序填表。页面支持一步一步演示,适合学生课上跟着填、课后自己复盘。
动态规划的核心是把大问题拆成小问题,并把小问题答案存在表里,后面直接使用。
先用两个入门模型理解 DP 四步法
状态是什么
用 f[i]、dp[i][j] 表示一个小问题的答案。
从哪里来
当前答案通常由前面已经算好的状态转移过来。
初始值是什么
比如 f[0]=1、金字塔顶点、背包容量为 0。
按什么顺序填
保证计算当前格子时,依赖的格子已经算出来。
模型 1:爬楼梯
一维 DP题目场景
一次可以走 1 级或 2 级,走到第 n 级共有多少种方法?
f[i] = f[i-1] + f[i-2]
状态:f[i] 表示走到第 i 级的方法数。最后一步只可能来自第 i-1 级或第 i-2 级。
模型 2:金字塔最大路径和
二维/路径 DP题目场景
从金字塔顶端出发,每次只能走到下一层相邻的数,求最大路径和。
dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j])
状态:dp[i][j] 表示走到第 i 层第 j 个位置时,能获得的最大和。
子序列问题:CSP-J 常见的两类
最长上升子序列 LIS
在一个序列中选出若干个数,保持原来的相对顺序,并且数值严格上升,求最长长度。
f[i] = max(f[j] + 1), j < i 且 a[j] < a[i]
最长公共子序列 LCS
两个字符串中,保持相对顺序后都能出现的最长序列。注意它不要求连续。
相等看左上,不等看上方和左方
模型 3:最长上升子序列
一维子序列 DP例子
序列:3, 1, 2, 5, 4, 7, 6
状态:f[i] 表示“必须以第 i 个数结尾”的最长上升子序列长度。
转移时只看前面比它小的数。
模型 4:最长公共子序列
二维子序列 DP例子
字符串 A:ABCBDAB
字符串 B:BDCABA
状态:dp[i][j] 表示 A 的前 i 个字符与 B 的前 j 个字符的 LCS 长度。
背包问题:01、多重、完全
01 背包
每件物品最多选一次。当前物品只有“不选”和“选一次”两种选择。
dp[i][j] = max(不选, 选一次)
完全背包
每件物品可以选无限次。常见写法是一维数组容量从小到大枚举。
for j = w..V: dp[j] = max(dp[j], dp[j-w]+v)
多重背包
每件物品有固定数量。可以拆成多个 01 物品,或按数量枚举。
选 0, 1, ..., cnt 件
模型 5:01 背包动态表
每件最多一次题目场景
背包容量为 8,有 4 件物品,每件最多选一次,求最大价值。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
状态:dp[i][j] 表示只考虑前 i 件物品、容量为 j 时的最大价值。
模型 6:完全背包详细例子
每种物品无限选题目
背包容量为 6,有两种物品,每种都可以选任意多件。
A:重量 2,价值 3
B:重量 3,价值 4
dp[j] = max(dp[j], dp[j-w] + v)
完全背包的一维写法中,容量 j 要从小到大枚举,这样同一种物品可以在本轮被重复使用。
为什么容量从小到大
处理 A 时,先得到 dp[2]=3;继续算 dp[4] 时,可以用刚刚更新的 dp[2]+3=6,表示选两个 A。
再算 dp[6] 时,可以用 dp[4]+3=9,表示选三个 A。
| 处理进度 | 容量 0 | 容量 1 | 容量 2 | 容量 3 | 容量 4 | 容量 5 | 容量 6 | 说明 |
|---|---|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 什么都不选,价值都是 0。 |
| 处理 A | 0 | 0 | 3 | 3 | 6 | 6 | 9 | A 可以重复选,所以容量 6 可以选 3 个 A,价值 9。 |
| 再处理 B | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 容量 5 可选 A+B 得 7;容量 6 选 3 个 A 仍然最优。 |
模型 7:多重背包详细例子
每种物品有数量上限题目
背包容量仍然是 6,但物品数量有限。
A:重量 2,价值 3,最多 2 件
B:重量 3,价值 4,最多 1 件
枚举选 k 件:0 <= k <= cnt
它不像完全背包,不能无限选 A;也不像 01 背包,每种不一定只有 1 件。
和完全背包的区别
完全背包里容量 6 可以选 3 个 A,价值是 9。
多重背包里 A 最多 2 件,所以最多只能选 2 个 A,价值 6;再加 B 会超容量,所以最终答案不会是 9。
| 处理进度 | 容量 0 | 容量 1 | 容量 2 | 容量 3 | 容量 4 | 容量 5 | 容量 6 | 说明 |
|---|---|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 还没处理任何物品。 |
| 处理 A,最多 2 件 | 0 | 0 | 3 | 3 | 6 | 6 | 6 | 容量 6 也不能选 3 个 A,因为 A 只有 2 件。 |
| 再处理 B,最多 1 件 | 0 | 0 | 3 | 4 | 6 | 7 | 7 | 容量 5 或 6 最优都是 A+B,价值 7。 |