🧮 动态规划 (Dynamic Programming)

难度 / Difficulty: 困难 (Hard)
分类 / Category: 算法思想 (Algorithm Paradigm)
时间复杂度 / Time Complexity: O(n) ~ O(n²)
空间复杂度 / Space Complexity: O(n) 或 O(1)

📖 算法简介 / Introduction

动态规划（DP）是一种将复杂问题分解为更小子问题，并通过存储子问题结果避免重复计算的算法思想。核心条件：最优子结构 + 重叠子问题。

Dynamic Programming is an algorithm paradigm that decomposes complex problems into subproblems and stores their results to avoid redundant computation. Core conditions: Optimal Substructure + Overlapping Subproblems.

💡 算法原理 / Principle

核心思想

1. 最优子结构：一个问题的最优解可以由其子问题的最优解构造
2. 重叠子问题：子问题会被重复计算（不像分治法每个子问题只算一次）
3. 状态转移：通过已知的子问题解推导出更大的问题解

两种实现方式

• 自顶向下（记忆化递归）：递归 + 缓存，避免重复计算
• 自底向上（Tabulation）：从小问题开始，逐步计算到大问题

经典步骤

1. 定义状态 — dp[i] 或 dp[i][j] 表示什么
2. 状态转移方程 — 如何从子问题推导当前问题
3. 初始化 — 最小子问题的值
4. 填表顺序 — 如何依次计算

📝 代码实现 / Implementation

斐波那契数列（基础版）

# 记忆化递归
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# 空间优化版本（自底向上）
def fib_dp(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

最长公共子序列（LCS）

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

✨ 示例 / Example

斐波那契：F(10) = 55

F(0)=0, F(1)=1
F(2)=F(1)+F(0)=1
F(3)=F(2)+F(1)=2
F(4)=F(3)+F(2)=3
F(5)=F(4)+F(3)=5
F(6)=F(5)+F(4)=8
F(7)=F(6)+F(5)=13
F(8)=F(7)+F(6)=21
F(9)=F(8)+F(7)=34
F(10)=F(9)+F(8)=55

爬楼梯问题（经典 DP）

问题：爬n阶楼梯，每步可爬1或2阶，有多少种爬法？

状态：dp[i] = 爬到第i阶的方法数
转移：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[1]=1, dp[2]=2

dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

🎯 适用场景 / Scenarios

• 最优路径问题 — 最短路径、最大收益
• 资源分配 — 背包问题、切割问题
• 字符串处理 — 编辑距离、最长公共子序列
• 计数问题 — 爬楼梯、硬币找零

Optimal path problems, Resource allocation (knapsack), String processing (edit distance, LCS), Counting problems (climbing stairs, coin change).

⚠️ 学习要点 / Key Points

1. 不是所有问题都用 DP — 必须满足最优子结构和重叠子问题
2. 状态定义最重要 — 状态定义错误，后面的推导全错
3. 画表理解 — 2D DP 问题建议先画表理解填表顺序
4. 空间优化 — 有些问题可以从 O(n²) 优化到 O(n) 或 O(1)