动态规划题型：怎么识别、怎么讲、怎么练
动态规划一旦不再靠背公式，而是改成“为了让剩余问题保持同构，我必须记住什么状态”，思路就会清晰很多。
覆盖题量
200+
推荐起手
状态要能用一句话准确说清楚。
高频误区
状态定义含糊，转移就会越写越乱。
什么时候该想到这个模式
下手前的检查清单
真正适合面试表达的解题步骤
先用自然语言命名状态。
列出哪些决策会转移到这个状态。
base case 必须和状态定义完全一致。
选一个能保证依赖已就绪的遍历顺序。
最后再考虑空间压缩和常数优化。
常见变体
线性 DP
下一步答案依赖前缀或前几个位置。
序列 DP
由两个序列或匹配关系共同定义状态。
决策型 DP
每一步都要在取、舍、合并、拆分之间做决策。
模板预览
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
入门建立直觉
#121 Best Time to Buy and Sell Stock
一次买卖股票可获得的最大利润。
对于今天来说，历史上真正有用的信息只有“到昨天为止的最低价格”。
入门建立直觉
#5 Longest Palindromic Substring
求字符串中的最长回文子串。
一个子串是回文，当且仅当两端字符相等，且内部子串也回文；长度较短时直接由 base case 处理。
变体补齐关键状态
#53 Maximum Subarray
求和最大的连续子数组。
每个位置只需要知道“以这里结尾的最佳子数组”，并不需要保留所有历史区间。
变体补齐关键状态
#62 Unique Paths
计算从左上到右下的不同路径数。
机器人走到某个格子，只可能来自两个前驱格子之一。
高频难点压强练习
#91 Decode Ways
统计数字字符串的解码方式数量。
转移完全取决于最后一位和最后两位是否都能形成合法字母。
高频难点压强练习
#152 Maximum Product Subarray
求乘积最大的连续子数组。
当前这个负数可能会把之前的最小值直接翻成新的最大值。
高频坑点
状态定义含糊，转移就会越写越乱。
base case 和状态定义根本对不上。
转移漏掉一种选择，或把两条路径重复计算。
还没证明正确就先做空间压缩。
练习顺序建议
先做爬楼梯、打家劫舍这种线性 DP。
再做最长公共子序列这类序列 DP。
然后进入零钱兑换、解码方法这类决策型问题。
最后再补区间 DP 或更复杂的状态设计。