dp
2026-08-29 20:38:09
发布于：上海
6阅读
0回复
0点赞
综合22 线性DP 08.29
解题步骤
- 状态 = 描述【子问题】所需要的最少信息。一般来说，问题问什么，dp 状态就是什么。
- 最长上升子序列：dp[i] 表示第 i 项的最长上升子序列的值。
- 编辑距离：dp[i][j] 表示 A 数组的前 i 个字符变成 B 数组的前 j 个字符所需的最小操作次数。
确定状态的步骤： - 先确定题目在问什么 ⟹ dp数组最终要存储什么（方案数？最大值？最小值？）
- 再确定存储的内容跟什么有关，是哪些要素在影响这个？ ⟹ 这些要素就是下标（当前选了前几个物品？当前的背包容量？）
- 这些下标组合起来，就是状态 ⟹ ”从前 i 个中选，使和恰好为 j 的方案数“。
2.答案：好的状态设计能够快速确定答案的位置。
- dp[n] 表示第 n 项斐波那契数列的值。
- dp[n][m] 表示 A 前 n 个字符转化成 B 的前 m 个字符所需的最小操作次数。
3.状态转移方程：决策如何到达第 i 项
通用的做法：用表格列出某个样例的 dp 数组的所有值，寻找其中特殊的变化规律，用代码描述它。
- 最大值 / 最小值：max / min ，最小值一般需要初始化。
- 方案数：一般需要各项累加起来。
4.初始化：给不满足转移方程的特殊边界值，单独赋值。
- 斐波那契数列的第一项和第二项，dp[1] = dp[2] = 1
5.遍历顺序
- 01背包：内层循环逆序。完全背包：内存循环正序。
6.调试debug：把 dp 数组打印出来，手算小样例的数据是否匹配，不要只用眼睛逐行看代码。
这里空空如也
有帮助，赞一个