动态规划

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解为更小子问题、并保存子问题结果以避免重复计算的算法思想。

它非常适合求解具有重叠子问题（overlapping subproblems）和最优子结构（optimal substructure）的问题。

一、核心思想

1. 划分子问题

   把原问题拆成若干个规模更小、结构相同的子问题。

2. 保存结果（记忆化）

   子问题的结果会被重复用到，因此用数组或哈希表保存，避免重复计算。

3. 状态转移

   找到子问题之间的递推关系（状态转移方程），逐步推导出原问题的最优解。

4. 自底向上或自顶向下

   • 自顶向下：递归 + 记忆化
   • 自底向上：迭代，从最小子问题开始，一步步推导更大规模的结果。

二、典型步骤

1. 定义状态：明确用什么变量表示“子问题”。
2. 写出状态转移方程：描述如何从已知状态得到新状态。
3. 初始化：确定最小子问题的解。
4. 确定计算顺序：通常是自底向上填表。

三、举例：斐波那契数列

问题：求第 n 个斐波那契数，公式为

F(n) = F(n-1) + F(n-2)，其中 F(0)=0, F(1)=1。

1. 普通递归（低效）

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

缺点：大量重复计算，时间复杂度 O(2^n)。

2. 动态规划（自底向上）

def fib_dp(n):
    if n <= 1:
        return n
    dp = [0]*(n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

• 状态定义：dp[i] 表示第 i 个斐波那契数
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
• 时间复杂度 O(n)，空间 O(n)，也可以优化到 O(1)。

四、实用例子：最短路径（经典背包）

问题：给定一个数组 coins 表示不同面值的硬币，以及一个总金额 amount，求凑成该金额所需的最少硬币数，如果无法凑成则返回 -1。

（这就是著名的零钱兑换问题）

动态规划解法

1. 状态：dp[i] 表示凑成金额 i 所需的最少硬币数。

2. 转移方程：

   dp[i] = min(dp[i - coin] + 1) for coin in coins if i - coin >= 0

3. 初始化：dp[0] = 0，其余为无穷大。

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print(coinChange([1, 2, 5], 11))  # 输出 3 (11 = 5 + 5 + 1)

总结

• 适用场景：最短路径、背包问题、最长子序列、编辑距离、股票买卖收益等。
• 关键点：
  1. 找到子问题
  2. 明确状态定义
  3. 写出状态转移方程
  4. 选择自顶向下或自底向上的求解方式

动态规划的本质是**“用空间换时间”**，通过存储中间结果，极大减少重复计算，从而高效求解复杂问题。