动态规划（DP）是算法领域的"时间管理大师"——它用空间换时间，将指数级问题降维成多项式求解。本文用真实案例拆解DP核心思想，附模板代码和面试高频题解。

---

一、DP的三大核心特征

1. 重叠子问题（避免重复计算）

# 斐波那契数列的暴力递归 vs DP
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # 存在大量重复计算（如fib(3)被调用5次）

# DP解法（时间复杂度O(n)）
dp = [0, 1]
for i in range(2, n+1):
    dp.append(dp[i-1] + dp[i-2])

2. 最优子结构（全局最优包含局部最优）

• 反例：求最长路径（局部最优无法保证全局最优）
• 正例：背包问题（当前物品选/不选依赖子问题最优解）

3. 无后效性（未来不影响过去）

• 状态一旦确定，后续决策不受之前路径影响
• 如：网格路径数（到达(i,j)的路径数只与左/上状态有关）

---

二、四步破题法（手撕DP秘籍）

1. 定义状态（设计DP数组含义）

• 一维：硬币问题 dp[i] 表示凑金额i的最少硬币数
• 二维：编辑距离 dp[i][j] 表示word1前i个转成word2前j个的最小操作

2. 状态转移方程（核心逻辑）

# 经典例题：爬楼梯（LeetCode 70）
# dp[i] = dp[i-1] + dp[i-2]   # 到达i阶的方案数

# 最长递增子序列（LeetCode 300）
for j in range(i):
    if nums[j] < nums[i]:
        dp[i] = max(dp[i], dp[j] + 1)

3. 初始化（边界条件）

• 爬楼梯：dp[0]=1, dp[1]=1
• 01背包：dp[0][j]=0（容量为0时价值0）

4. 确定遍历顺序（避免状态覆盖）

• 背包问题：物品外层循环，容量内层倒序（防止重复放入）
• 回文子串：从中心向两边扩散（如dp[i][j]依赖dp[i+1][j-1]）

---

三、五大经典模型详解

1. 线性DP（单序列）

问题	状态定义	转移方程
最大子数组和	dp[i]以i结尾的最大和	dp[i]=max(nums[i], dp[i-1]+nums[i])
最长上升子序列(LIS)	dp[i]以i结尾的LIS长度	dp[i]=max(dp[j])+1 (j<i且nums[j]<nums[i])

2. 区间DP（枚举分割点）

# 戳气球（LeetCode 312）
for k in range(i, j+1):  # k是最后戳破的气球
    dp[i][j] = max(dp[i][j], 
                   dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j])

3. 背包DP（选/不选决策）

# 01背包模板（物品数n，背包容量C）
dp = [0]*(C+1)
for i in range(n):
    for j in range(C, weight[i]-1, -1):  # 必须倒序！
        dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

4. 树形DP（后序遍历）

# 打家劫舍III（LeetCode 337）
def dfs(root):
    if not root: return [0, 0]  # [偷当前, 不偷当前]
    left = dfs(root.left)
    right = dfs(root.right)
    rob = root.val + left[1] + right[1]  # 偷当前则子节点不能偷
    not_rob = max(left) + max(right)     # 不偷当前则子节点随意
    return [rob, not_rob]

5. 状态机DP（多状态切换）

# 买卖股票最佳时机（含冷冻期，LeetCode 309）
dp0 = 0            # 不持有股票（非冷冻）
dp1 = -prices[0]   # 持有股票
dp2 = 0            # 不持有股票（冷冻期）

for i in range(1, n):
    new_dp0 = max(dp0, dp2)        # 前一天不持有或已过冷冻期
    new_dp1 = max(dp1, dp0 - prices[i])  # 继续持有或今日买入
    new_dp2 = dp1 + prices[i]      # 今日卖出进入冷冻期
    dp0, dp1, dp2 = new_dp0, new_dp1, new_dp2

---

四、三大优化技巧（击败90%竞争者）

1. 滚动数组（降维打击）

# 斐波那契空间优化（O(n) → O(1)）
a, b = 0, 1
for _ in range(n):
    a, b = b, a+b

2. 斜率优化（单调队列）

# 最大滑动窗口（LeetCode 239）
from collections import deque
q = deque()
for i in range(n):
    while q and nums[q[-1]] <= nums[i]:
        q.pop()  # 维护单调递减队列
    q.append(i)
    if q[0] == i - k:  # 移除超出窗口的元素
        q.popleft()

3. 四边形不等式（区间DP优化）

• 满足 w[i][j] + w[i'][j'] <= w[i][j'] + w[i'][j] (i<=i'<=j<=j')
• 则最优分割点 s[i][j] 满足 s[i][j-1] <= s[i][j] <= s[i+1][j]

---

五、高频面试真题实战

1. 正则表达式匹配（LeetCode 10）

# dp[i][j]: s前i个和p前j个是否匹配
if p[j-1] == '*':
    dp[i][j] = dp[i][j-2]  # 匹配0次
    or (s[i-1]==p[j-2] or p[j-2]=='.') and dp[i-1][j]  # 匹配多次

2. 最长有效括号（LeetCode 32）

dp = [0]*n  # dp[i]表示以i结尾的最长有效括号
if s[i]==')':
    if s[i-1]=='(':  # ...() 情况
        dp[i] = dp[i-2] + 2  
    else:             # ...)) 情况
        if i-dp[i-1]-1 >=0 and s[i-dp[i-1]-1]=='(':
            dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]

---

六、动态规划思维导图

graph TD
    A[问题类型] --> B[最优化问题/计数问题]
    A --> C[可行性问题]
    B --> D[背包/股票/打家劫舍]
    C --> E[正则匹配/通配符]
    
    F[状态设计] --> G[一维：序列问题]
    F --> H[二维：矩阵/双序列]
    F --> I[三维：复杂状态]
    
    J[优化技巧] --> K[滚动数组]
    J --> L[状态压缩]
    J --> M[单调队列]

避坑指南：

1. 先写递归再改DP（理清决策树）
2. 打印DP表调试（二维问题画表格）
3. 警惕状态覆盖（01背包倒序遍历）
4. 注意负数索引（Python用tuple代替）

动态规划的本质是优雅地避免重复劳动。掌握其核心思想后，你会惊讶地发现：从最短路径到自然语言处理，从游戏AI到量化交易，DP的身影无处不在。正如算法大师Dijkstra所说：“动态规划不是一种算法，而是一种思维方式。”