动态规划（Dynamic Programming）

Abstract

动态规划（DP）是一种算法设计思想，通过将复杂问题拆解为重叠子问题，并利用最优子结构，逐步构建最终解。其核心在于保存并复用子问题的解，从而显著提升效率。动态规划被广泛应用于最优化、计数、决策等众多场景，是解决诸如背包、路径、子序列等类型问题的利器。

一句话总结：把一个大问题，拆成小问题，解决小问题并存好，最后合起来解决大问题。

核心思想

动态规划的核心在于避免重复计算。与暴力递归不同，DP 会将已经计算过的子问题结果保存下来，后续直接复用，从而将指数级时间复杂度降至多项式级。

何时考虑使用 DP？

当问题同时满足以下两个条件时，通常可以用 DP 来解决：

DP 有两种实现方式：自顶向下（Memoization） 和 自底向上（Tabulation）。

自顶向下：记忆化递归（Memoization）

从原始问题出发，递归地分解为子问题，并用缓存保存已计算的结果。
```
def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]
```
- 思路自然，与递归公式直接对应
- 只计算需要的子问题（懒计算）
- 递归深度过大时可能栈溢出
自底向上：递推表格（Tabulation）

从最小的子问题开始，逐步递推到目标问题，使用数组存储中间结果。
```
def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
```
- 无递归开销，不会栈溢出
- 计算所有子问题（即使部分不需要）
- 通常更容易进行空间优化

如何选择？

解决 DP 问题通常遵循以下步骤：

步骤	说明
1. 定义状态	明确 `dp[i]`（或 `dp[i][j]`）的含义
2. 推导转移方程	找出 `dp[i]` 与更小子问题之间的递推关系
3. 确定初始条件	最小子问题（base case）的值
4. 确定遍历顺序	确保计算 `dp[i]` 时所依赖的状态已经算好
5. 空间优化（可选）	若当前状态只依赖有限的前几个状态，可用滚动数组压缩空间

当 dp[i] 只依赖 dp[i-1]（或有限的前几项）时，无需保留完整数组：

# 斐波那契 O(1) 空间
prev, curr = 0, 1
for _ in range(2, n + 1):
    prev, curr = curr, prev + curr

部分 DP 的转移涉及区间求和，可借助前缀和将单次转移从 O(n) 降至 O(1)。

当转移方程形如 \( dp[i] = \min_{j \in [l, r]} dp[j] + cost(i) \) 时，可使用单调队列将每次转移优化至 O(1)。典型应用：滑动窗口最大值、跳跃游戏变种。

LIS 的 O(n log n) 解法即利用了二分查找来维护贪心的辅助数组。