DP 8.29
2026-08-29 20:25:00
发布于：上海
解题步骤：
1、状态=描述【子问题】所需要的最少信息。一般来书评，问题问什么，dp状态就是什么。
最长上升子序列：dp[i]表示第i项的最长上升子序列的值。
编辑距离：d[i][j]表示A数组的前i个字符变成B数组的前j个字符所需要的最小操作次数。
确定状态步骤：
先确定题目在问什么->dp数组最终要储存什么（方案数？最大值？最小值？）
再确定存储的内容跟什么有关系，是哪些要素在影响这个？->这些要素就是下标（当前选了几个物品？当前背包容量？）
这些下标组合起来，就是状态->“从前i个中选，使恰好为j的方案数”。
2、答案：好的状态设计能够快速确定答案的位置。
dp[n]表示第n项斐波那契数列的值。
dp[n][m]表示A前n个字符转化成B的前n个字符所需要的最小操作次数。
3、状态转移方程：决策如何达到第i项
通用的做法：用表格列出某个样例的dp数组的所有值，寻找其中特殊的变化规律，用代码代替它。
最大值/最小值：max/min，最小值一般需要初始化。
方案数：一般需要各项累加起来。
4、初始化：给不满足转移方程的特殊边界，单独赋值。
斐波那契数列的第一项和第二项，dp[1]=dp[2]=1
5、遍历顺序
01背包：内层循环逆用。完全背包：内层循环正序。
6、调试bug：把dp数组打印出来，手算样例的数据是否匹配，不要只用眼逐行看代码。
U145095.[USACO04NOV] Apple Catching G
求：能接住最多的苹果？
<-与移动次数，掉落时间有关。（DP就是个mei'jvmeijv，分析题目问题有关的变量，枚举相关变量）
<-需要知道T分钟，一共移动了多少次
<-用dp[i][j]表示第i分钟，移动了j次所获得的最大苹果数。
<-能怎么移动，能怎么决策？即，每分钟动/不动。
这里空空如也
有帮助，赞一个