dp动态规划
2026-08-29 20:33:48
发布于：上海
26阅读
0回复
0点赞
动态规划
解题步骤
1.状态 = 描述【子问题】所需要的最少信息。一般来说，问题问什么，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数组打印出来，手算小样例的数据是否匹配，不要只用眼睛逐行看代码。
[USACO04NOV] Apple Catching G（填空）
求：能接住最多的苹果数。
<===与移动次数，掉落时间有关。（DP就是个枚举，分析题目问题有关的变量，枚举相关变量）
<===需要知道第T分钟，一共移动了多少次
<===用dp[i][j]表示第i分钟移动了j次所获得的最大苹果数。
<===能怎么移动，能怎么做决策？即，每分钟动/不动。
有帮助，赞一个