小楼春雨
返回首页
·5 min read·学习笔记

动态规划学习笔记：从递推到状态转移方程

#算法#动态规划#LeetCode

什么是动态规划

动态规划（Dynamic Programming, DP）的核心思想很简单：

将复杂问题拆分为子问题，存储子问题的解以避免重复计算。

它适用于具有两个关键性质的问题：

  1. 最优子结构 — 问题的最优解包含子问题的最优解
  2. 重叠子问题 — 递归求解时会反复遇到相同的子问题

从斐波那契开始

# 朴素递归：O(2^n) — 大量重复计算
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# 记忆化递归：O(n) — 存储已计算的值
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

# 动态规划：O(n) — 自底向上
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]

这就是动态规划的雏形：用空间换时间。

状态转移方程

动态规划的核心是找到状态转移方程——描述状态之间如何转移的数学关系。

框架

1. 定义状态：dp[i] 代表什么？
2. 推导方程：dp[i] 与 dp[i-1] 等的关系
3. 初始条件：dp[0] = ?, dp[1] = ?
4. 计算顺序：通常从左到右
5. 返回结果：dp[n]

经典例题

1. 爬楼梯（LeetCode 70）

每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种方法？

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

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2
    for i in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

2. 最长递增子序列（LeetCode 300）

找到无序数组中最长递增子序列的长度。

状态：dp[i] = 以 nums[i] 结尾的最长递增子序列长度
方程：dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
初始：dp[i] = 1（每个元素自身长度为1）

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

3. 0-1 背包问题

有 n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 W，求最大价值。

状态：dp[i][j] = 前 i 个物品，容量为 j 时的最大价值
方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
初始：dp[0][j] = 0

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]  # 不选第i个物品
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]] + values[i-1])
    return dp[n][W]

空间优化

很多 DP 问题可以优化空间复杂度。当 dp[i] 只依赖 dp[i-1] 时，可以用滚动数组：

# 原始：O(n) 空间
dp = [0] * (W + 1)

# 优化：一维数组，逆序遍历
for i in range(n):
    for j in range(W, weights[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

解题策略

| 类型 | 特征 | 典型题目 | |------|------|---------| | 一维 DP | 线性递推 | 爬楼梯、打家劫舍 | | 二维 DP | 矩阵/双序列 | 编辑距离、LCS | | 区间 DP | 合并区间 | 戳气球、矩阵链乘 | | 树形 DP | 树上递推 | 打家劫舍 III | | 状态压缩 DP | 位运算 | 旅行商问题 |

总结

动态规划的关键不在于写代码，而在于定义状态和推导转移方程。这两步想清楚了，代码水到渠成。

解 DP 题的秘诀：画图。把状态转移的过程画在纸上，规律自然浮现。

小楼春雨

@站长