DP是算法面试最让人发怵的主题。有一套通用框架比背50道题更实用。
第一步：判断有无重叠子问题+最优子结构。题目能表达成"几个小版本的最优"就适合DP。
第二步：定义状态。哪些变量能完整描述一个子问题？通常最难的一步。
第三步：写转移方程。dp[i]怎么从更小的状态得到？用递推表达。
第四步：定边界+迭代顺序。先算小的、被依赖的状态。
第五步：优化。滚动数组（O(n²)空间→O(n)）、降维、剪枝。先对再优化。
我有固定流水线。先问：第i步选/不选能不能递归成同形状子问题？能就是DP。然后定状态——背包是(物品下标, 剩余容量)；编辑距离是(i, j)指向两字符串。写转移强迫我说清"这一步在做什么选择、怎么降到更小状态"。边界从转移自然浮现——递归到底的地方就是。我先写自顶向下+记忆化，跟递归思路1:1对；需要空间优化滚动数组时再改自底向上。大多数"不会DP"的焦虑来自跳过第二步——状态干净了转移几乎是自动的。
手画小输入的递归树——重叠一目了然"这是DP"。
一句话说不清状态，就换一种状态定义。
即答侠归纳了12类DP原型（背包、LIS、区间、树DP）——快速识别题目骨架。
自顶向下思路自然、稀疏状态下更省。自底向上无递归开销、能做空间优化。
能贪心求最优时、无重叠子问题纯递归/分治就够时。