动态规划

DP 的本质是拆解问题、存储中间结果避免重复计算。掌握五步法：定义状态、转移方程、初始化、遍历顺序、举例验证。

区间 DP 按「区间长度」递增遍历，回文 DP 按「中心」向外扩展。典型：最长回文子串、回文子串计数。

子序列问题的核心是 dp[i][j] 表示以 s1[i] 和 s2[j] 结尾的状态。掌握 LIS、LCS、编辑距离三大经典。

状态机 DP 用于处理有多种状态转换的问题。股票系列是经典：持有/不持有状态之间转换。

背包问题是 DP 的经典应用。核心是状态定义：dp[i][j] = 考虑前 i 个物品，容量 j 时的最大价值。