动态规划

1. 基本概念

核心定义：动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为重叠子问题来求解最优化问题的算法策略。
核心思想：“记住过去，指导未来”。
- 与其每次都重新计算相同的问题，不如把结果存起来（备忘录），下次直接查表。
- 利用状态转移方程，从小规模问题的解推导出大规模问题的解。
三大要素：
- 最优子结构：大问题的最优解包含子问题的最优解（比如：去终点的最短路径，一定经过去中途某点的最短路径）。
- 重叠子问题：在递归求解时，相同的子问题被反复计算（这是使用DP的前提）。
- 状态转移方程：描述状态之间如何转化的数学公式（如 $dp[i] = dp[i-1] + dp[i-2]$ ）。

2. 费曼理解

用最简单的语言解释给“小白”听：

想象你在爬楼梯，每次只能爬 1 级或 2 级。你想知道爬到第 10 级有多少种方法。

普通递归（傻算）：
你站在第 10 级，想：“我要么从第 9 级上来，要么从第 8 级上来”。于是你跑去算第 9 级，算第 9 级时又跑去算第 8 级……结果你发现，第 8 级被你算了两次！ 随着楼层越高，重复计算量会爆炸式增长。

动态规划（聪明人）：
你随身带了一个小本本（备忘录/DP数组）。

算出第 1 级有 1 种方法，记下来。

算出第 2 级有 2 种方法，记下来。

算第 3 级时，直接翻看小本本： $第3级 = 第2级 + 第1级$ 。

一步步推到第 10 级。每个台阶只算一次，绝不吃回头草。

3. 内部实现：核心解题四步

动态规划通常有两种实现方式：自顶向下（记忆化搜索） 和 自底向上（迭代递推）。这里以最经典的自底向上为例。

步骤序号	步骤名称	核心操作描述	关键问题
Step 1	定义状态	定义 `dp[i]` 或 `dp[i][j]` 的含义。	“这个数组里的数字代表什么？” (例如：爬到第 i 阶的方法数)
Step 2	推导方程	找出状态之间的数学关系。	“现在的状态怎么由过去的状态推出来？” (例如： $dp[i] = dp[i-1] + dp[i-2]$ )
Step 3	初始化	确定最开始的几个值（基准情况）。	“起步数据是多少？” (例如： $dp[0]=0, dp[1]=1$ )
Step 4	确定顺序	决定遍历的方向（从小到大）。	“先算谁，后算谁？” (确保计算 $dp[i]$ 时， $dp[i-1]$ 已经算好了)

4. 代码模板：爬楼梯 (LeetCode 70)

class Solution:
    def climbStairs(self, n: int) -> int:
        # Step 1: 定义状态
        # dp[i] 表示爬到第 i 阶楼梯的方法数
        if n <= 1: return n
        
        # Step 3: 初始化 (基准情况)
        # 爬到第 1 阶只有 1 种方法，第 2 阶有 2 种
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        
        # Step 4: 确定顺序 & Step 2: 推导方程
        # 从第 3 阶开始，一步步推导到第 n 阶
        for i in range(3, n + 1):
            # 状态转移方程：当前阶数 = 前一阶 + 前两阶
            dp[i] = dp[i-1] + dp[i-2]
            
        return dp[n]

5. 复杂度分析

指标	复杂度	说明
时间复杂度	$O(N)$	相比递归的 $O(2^N)$ ，DP 将每个子问题只计算一次，效率极大提升。
空间复杂度	$O(N)$	需要一个数组来存储所有状态。
进阶优化	$O(1)$	滚动数组：因为 $dp[i]$ 只依赖前两个数，所以不需要存整个数组，只用两个变量 `a, b` 即可。