30 秒速览

  • 什么时候用：最值问题、计数问题、可行性问题，且具有最优子结构和重叠子问题
  • 核心思想：把大问题拆成小问题，存储中间结果避免重复计算
  • 五步法：定义状态 → 转移方程 → 初始化 → 遍历顺序 → 验证
  • 时间复杂度：状态数 × 每个状态的转移时间

一、直觉建立

爬楼梯问题

问题：你要爬到第 10 级楼梯，每次可以爬 1 级或 2 级，有多少种方法？

笨办法：一条路一条路地尝试，太慢了。

DP 思维：

到达第 1 级：1 种方法（爬 1 步）
到达第 2 级：2 种方法（1+1 或 2）
到达第 3 级：从第 2 级爬 1 步，或从第 1 级爬 2 步
         = 到第 2 级的方法数 + 到第 1 级的方法数 = 2 + 1 = 3

规律：dp[n] = dp[n-1] + dp[n-2]

DP 的本质

大问题 → 拆成小问题 → 先解决小问题，存起来 → 用小问题的答案推导大问题

为什么能避免重复计算？

以斐波那契为例，暴力递归 fib(5) 会计算 fib(3) 两次、fib(2) 三次。DP 把每个值算一次存起来，下次直接用。

DP 的三个核心概念

1. 最优子结构

大问题的最优解包含小问题的最优解。

2. 重叠子问题

同一个小问题会被反复用到，所以要存起来。

3. 状态转移

从一个状态到另一个状态的转换过程，用状态转移方程描述。

二、DP 五步法

第 1 步：定义状态

明确 dp[i] 代表什么。

例如：dp[i] = 爬到第 i 级楼梯的方法数

第 2 步：确定转移方程

找出当前状态与之前状态的关系。

例如：dp[i] = dp[i-1] + dp[i-2]

第 3 步：初始化

确定初始状态。

例如：dp[0] = 1（地面），dp[1] = 1

第 4 步：确定遍历顺序

从前往后还是从后往前？

例如：从 i=2 到 n，因为 dp[i] 依赖 dp[i-1] 和 dp[i-2]

第 5 步：举例验证

用小例子手动推演，检查边界。

三、典型例题

例题 1：LC 70. 爬楼梯

题目：每次可以爬 1 或 2 级，爬到第 n 级有多少种方法？

五步法

  1. 状态：dp[i] = 爬到第 i 级的方法数
  2. 转移：dp[i] = dp[i-1] + dp[i-2]
  3. 初始化：dp[0] = 1, dp[1] = 1
  4. 顺序：从 2 到 n
  5. 验证：n=3 时，dp[3] = dp[2] + dp[1] = 2 + 1 = 3 ✓

代码

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

空间优化

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1  # dp[i-2], dp[i-1]

    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr

    return prev1

复杂度：时间 O(n)，空间 O(1)

例题 2：LC 198. 打家劫舍

题目：一排房子，相邻的不能偷，求最大金额。

示例：

输入：nums = [2,7,9,3,1]
输出：12（偷 2 + 9 + 1 = 12）

五步法

  1. 状态：dp[i] = 偷前 i 个房子的最大金额
  2. 转移：
    • 偷第 i 个：dp[i-2] + nums[i]（不能偷 i-1）
    • 不偷第 i 个：dp[i-1]
    • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  3. 初始化：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  4. 顺序：从 2 到 n-1

代码

def rob(nums: list[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, n):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr

    return prev1

复杂度：时间 O(n)，空间 O(1)

例题 3：LC 62. 不同路径

题目：m×n 网格，从左上角到右下角，只能向右或向下，有多少种路径？

五步法

  1. 状态：dp[i][j] = 到达 (i,j) 的路径数
  2. 转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
  3. 初始化：第一行和第一列都是 1
  4. 顺序：从上到下，从左到右

代码

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

复杂度：时间 O(mn)，空间 O(mn)

例题 4：LC 64. 最小路径和

题目：m×n 网格，每个格子有数字，找从左上到右下的最小路径和。

五步法

  1. 状态：dp[i][j] = 到达 (i,j) 的最小路径和
  2. 转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
  3. 初始化：第一行和第一列累加
  4. 顺序：从上到下，从左到右

代码

def minPathSum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]

    # 初始化第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # 初始化第一列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    # 填充剩余格子
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1]

复杂度：时间 O(mn)，空间 O(mn)

例题 5：LC 152. 乘积最大子数组

题目：给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。

示例：

输入：nums = [2,3,-2,4]
输出：6（子数组 [2,3] 的乘积）

思路

因为有负数，需要同时维护最大值和最小值（负负得正）。

def maxProduct(nums: list[int]) -> int:
    max_dp = min_dp = result = nums[0]

    for i in range(1, len(nums)):
        # 同时更新最大和最小
        if nums[i] < 0:
            max_dp, min_dp = min_dp, max_dp

        max_dp = max(nums[i], max_dp * nums[i])
        min_dp = min(nums[i], min_dp * nums[i])

        result = max(result, max_dp)

    return result

复杂度：时间 O(n)，空间 O(1)

例题 6：LC 139. 单词拆分

题目：给你一个字符串 s 和一个字符串列表 wordDict，判断 s 是否可以被拆分成 wordDict 中的单词。

五步法

  1. 状态：dp[i] = s[0:i] 能否被拆分
  2. 转移：dp[i] = dp[j] and s[j:i] in wordDict（任一 j 满足即可）
  3. 初始化：dp[0] = True（空字符串可拆分）
  4. 顺序：从 1 到 n

代码

def wordBreak(s: str, wordDict: list[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

复杂度：时间 O(n²)，空间 O(n)

例题 7：LC 322. 零钱兑换

题目：给你一个整数数组 coins 和一个整数 amount，计算凑成 amount 所需的最少硬币数。

五步法

  1. 状态：dp[i] = 凑成金额 i 的最少硬币数
  2. 转移：dp[i] = min(dp[i - coin] + 1) 对所有 coin ≤ i
  3. 初始化：dp[0] = 0，其他为 ∞
  4. 顺序：从 1 到 amount

代码

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

复杂度：时间 O(amount × n)，空间 O(amount)

四、DP 适用条件判断

判断一个题能否用 DP

  1. 是否是求最值、计数、可行性？
  2. 是否有最优子结构？（大问题的最优解能由小问题的最优解组成）
  3. 是否有重叠子问题？（同一子问题被多次计算）

DP vs 其他方法

问题类型适用方法
有序数组找目标二分
连续子数组，无负数滑动窗口
最值/计数，有重叠子问题DP
求所有可能方案回溯

五、常见错误与陷阱

错误 1：状态定义不清

# 模糊
dp[i] = 某种最优解

# 清晰
dp[i] = 考虑前 i 个元素，且必须选第 i 个元素时的最大和

错误 2：转移方程推导错误

# 打家劫舍
# 错误：dp[i] = dp[i-1] + nums[i]  ← 相邻的可以同时偷？

# 正确：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

错误 3：初始化错误

# 爬楼梯
# 错误：dp[0] = 0, dp[1] = 1  ← dp[2] = dp[1] + dp[0] = 1，但实际是 2

# 正确：dp[0] = 1, dp[1] = 1  ← dp[0] 表示地面，1 种方法

错误 4：遍历顺序错误

# 如果 dp[i] 依赖 dp[i-1] 和 dp[i-2]
# 正确：从 2 到 n
for i in range(2, n + 1):
    ...

# 错误：从 n 到 2（依赖的还没算）

六、复盘清单

触发信号

  • 求最值（最大/最小）
  • 计数（多少种方法）
  • 可行性（能否达成）
  • 具有重叠子问题
  • 具有最优子结构

五步法检查

  • 状态定义清晰
  • 转移方程正确
  • 初始化正确
  • 遍历顺序正确
  • 用小例子验证

边界条件

  • n = 0 或 n = 1
  • 所有元素相同
  • 所有元素为负

七、题目清单

基础题

题号题目难度考点
70爬楼梯Easy线性 DP
746使用最小花费爬楼梯Easy线性 DP
198打家劫舍Medium线性 DP
62不同路径Medium网格 DP
64最小路径和Medium网格 DP

进阶题

题号题目难度考点
152乘积最大子数组Medium维护最大最小
139单词拆分Medium子串匹配
322零钱兑换Medium完全背包
300最长递增子序列MediumLIS
1143最长公共子序列MediumLCS