动态规划（DP）

把大问题拆成重叠子问题，用递推（或记忆化）避免重复计算。核心：定义状态、写转移方程、确定初值与顺序。

思路

1. 状态：dp[i] 或 dp[i][j] 表示什么（例如：到第 i 个时的最优解）。
2. 转移：dp[i] 由哪些更小的 dp[...] 推出来。
3. 初值：最小的那几项先填好。
4. 顺序：按依赖关系从小往大算（或记忆化递归）。

一维 DP：斐波那契

dp[i] = dp[i-1] + dp[i-2]，初值 dp[0]=0, dp[1]=1。

一维 DP：爬楼梯

一次爬 1 或 2 阶，到第 n 阶几种方案？dp[i] = dp[i-1] + dp[i-2]，本质同斐波那契。

二维 DP：路径/网格

从左上到右下，只能向右或向下，路径数或最小路径和。dp[i][j] 由 dp[i-1][j] 和 dp[i][j-1] 转移。

记忆化递归

不显式建表，用递归 + 缓存（如 @lru_cache 或字典）避免重复子问题，等价于 DP。

小结

• 状态：想清楚 dp[i] / dp[i][j] 表示什么。
• 转移：写清楚由哪些更小的状态推过来。
• 初值与顺序：先填边界，再按依赖顺序填表（或记忆化递归）。