从零吃透「动态规划」

一、什么是动态规划

动态规划（Dynamic Programming）把一个大问题分解成互相重叠的子问题，并 记录已解决的子问题结果，避免重复计算。

核心思想：最优子结构 + 重叠子问题，借助状态转移方程递推求解。

二、三步法

1. 1定义状态：用一个数组 dp，明确 dp[i] 表示什么含义。
2. 2写转移方程：当前状态由哪些前序状态推导而来。
3. 3确定边界：初始化 dp[0]、dp[1] 等基础值。

三、经典例题

1. 爬楼梯

每次可爬 1 或 2 阶，爬到 n 阶有几种方法。

状态 dp[i] = dp[i-1] + dp[i-2]，边界 dp[1]=1, dp[2]=2。这就是斐波那契。

2. 最长递增子序列

状态 dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。转移时需要遍历前面所有更小的元素。

3. 0-1 背包

在容量限制下选物品使价值最大。状态是"前 i 件物品 + 容量 j"，即二维 dp。

四、总结建议

• 先从一维 DP 入手，再上二维与空间优化（滚动数组）。
• 画"状态转移表"最直观，别只在脑子里想。
• DP 靠量变到质变，建议配合大厂算法面试 100 题一起刷。