CSP-J 动态规划互动训练

用 CSP-J 常见模型练习动态规划:先定义状态,再找转移,最后按正确顺序填表。页面支持一步一步演示,适合学生课上跟着填、课后自己复盘。

DP 不是背公式

动态规划的核心是把大问题拆成小问题,并把小问题答案存在表里,后面直接使用。

先用两个入门模型理解 DP 四步法

1

状态是什么

用 f[i]、dp[i][j] 表示一个小问题的答案。

2

从哪里来

当前答案通常由前面已经算好的状态转移过来。

3

初始值是什么

比如 f[0]=1、金字塔顶点、背包容量为 0。

4

按什么顺序填

保证计算当前格子时,依赖的格子已经算出来。

模型 1:爬楼梯

一维 DP

题目场景

一次可以走 1 级或 2 级,走到第 n 级共有多少种方法?

f[i] = f[i-1] + f[i-2]

状态:f[i] 表示走到第 i 级的方法数。最后一步只可能来自第 i-1 级或第 i-2 级。

当前 i 0
当前转移 f[0]=1
答案 ?

为什么 f[0]=1

站在第 0 级表示还没开始,什么都不做也是一种“到达第 0 级”的方法,后面转移会用到它。

模型 2:金字塔最大路径和

二维/路径 DP

题目场景

从金字塔顶端出发,每次只能走到下一层相邻的数,求最大路径和。

dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j])

状态:dp[i][j] 表示走到第 i 层第 j 个位置时,能获得的最大和。

当前格子 (1,1)
本格数值 7
最大路径和 ?

从上往下填

当前格子的最大路径和,只需要知道上一层相邻格子的最大路径和。

子序列问题: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 个数结尾”的最长上升子序列长度。

转移时只看前面比它小的数。

当前 i 1
当前 a[i] 3
LIS 长度 ?

先从每个数自己开始

每个位置至少能形成长度为 1 的上升子序列。

模型 4:最长公共子序列

二维子序列 DP

例子

字符串 A:ABCBDAB

字符串 B:BDCABA

状态:dp[i][j] 表示 A 的前 i 个字符与 B 的前 j 个字符的 LCS 长度。

当前字符 A vs B
当前位置 (1,1)
LCS 长度 ?

从左上到右下填

如果两个字符相等,就让左上角答案加 1;否则取上方和左方的较大值。

背包问题: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 时的最大价值。

当前物品 0
当前容量 0
答案 ?

读表方法

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 说明
初始 0000000 什么都不选,价值都是 0。
处理 A 0033669 A 可以重复选,所以容量 6 可以选 3 个 A,价值 9。
再处理 B 0034679 容量 5 可选 A+B 得 7;容量 6 选 3 个 A 仍然最优。

完全背包结论

容量 6 的最优值是 9,方案是选 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 说明
初始 0000000 还没处理任何物品。
处理 A,最多 2 件 0033666 容量 6 也不能选 3 个 A,因为 A 只有 2 件。
再处理 B,最多 1 件 0034677 容量 5 或 6 最优都是 A+B,价值 7。

多重背包结论

容量 6 的最优值是 7,方案是选 1 个 A 和 1 个 B。关键点:每种物品有数量上限,不能把它当成完全背包。

自测练习:按分类巩固