动态规划

第 15 章 · 数据结构与算法

把子问题的答案存下来，避免重复计算。 上一章递归与分治里，斐波那契的朴素递归会重复计算大量相同的 F(k)，导致指数级时间。动态规划（Dynamic Programming，DP）的核心思想是：若子问题会重叠（同一子问题被多次用到），就只算一次并记下结果，下次直接用。实现方式有两种：记忆化搜索（自顶向下，在递归里加缓存）和递推填表（自底向上，按依赖顺序算）。本章讲重叠子问题与最优子结构、记忆化与递推、斐波那契与爬楼梯、最大子数组和与最长递增子序列，以及至少三道例题的 Python 代码（类型标注与注释）。

一、动态规划概述

适用 DP 的问题通常具备：重叠子问题（同一子问题在递归中多次出现）、最优子结构（当前最优可由子问题最优得到）、无后效性（当前状态一旦确定，后续决策不受之前如何到达该状态的影响）。与分治的区别：分治子问题不重叠，DP 子问题重叠，故需要「存结果」避免重复计算。

重叠子问题：fib(3) 在递归树中出现多次

二、两种实现方式

记忆化搜索（Memoization）：写递归时，在进入子问题前先查缓存（如字典或数组），若已算过则直接返回；否则递归算完再写入缓存。自顶向下，逻辑接近「递归定义」，易写。递推填表：确定状态与转移顺序后，从最小规模开始用循环填表（如 dp[0], dp[1], …），直到得到目标状态。自底向上，通常空间可优化（如斐波那契只需两个变量）。

斐波那契递推：dp[i]=dp[i-1]+dp[i-2]，按 i 从小到大填

三、斐波那契：从递归到 DP

F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。朴素递归 O(2^n)；记忆化后每个 n 只算一次，O(n)；递推同样 O(n) 时间、可压成 O(1) 空间。

from typing import Dict


def fib_memo(n: int, memo: Dict[int, int] | None = None) -> int:
    """记忆化搜索：先查 memo，无则递归并存入。"""
    if memo is None:
        memo = {}
    if n <= 0:
        return 0
    if n == 1:
        return 1
    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: int) -> int:
    """递推：dp[i]=dp[i-1]+dp[i-2]，只保留最近两个变量。"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

四、爬楼梯与最大子数组和

爬楼梯：一次可爬 1 或 2 阶，到第 n 阶的方案数。dp[i]=到达第 i 阶的方案数，dp[i]=dp[i-1]+dp[i-2]，与斐波那契同构。最大子数组和：dp[i]=以 nums[i] 结尾的最大子数组和，dp[i]=max(nums[i], dp[i-1]+nums[i])，答案为 max(dp)。可省掉数组，只保留「以当前结尾的最大和」与「全局最大」两个变量，O(n) 时间 O(1) 空间。

最大子数组和：维护「以当前结尾的最大和」cur 与「全局最大」best

from typing import List


def climb_stairs(n: int) -> int:
    """爬楼梯：dp[i]=dp[i-1]+dp[i-2]，dp[0]=1, dp[1]=1。"""
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


def max_subarray_sum(nums: List[int]) -> int:
    """最大子数组和：dp[i]=以 i 结尾的最大和，dp[i]=max(nums[i], dp[i-1]+nums[i])。"""
    if not nums:
        return 0
    cur = nums[0]
    best = cur
    for i in range(1, len(nums)):
        cur = max(nums[i], cur + nums[i])
        best = max(best, cur)
    return best

五、最长递增子序列（LIS）

求数组中最长严格递增子序列的长度（子序列不要求连续）。状态：dp[i]=以 nums[i] 结尾的 LIS 长度。转移：dp[i]=1+max{dp[j] : j<i 且 nums[j]<nums[i]}，若不存在 j 则 dp[i]=1。答案 max(dp)。时间 O(n²)。更优的有 O(n log n) 的二分+贪心写法（维护「长度为 k 的递增子序列的最小末尾」），可作为扩展。

from typing import List


def length_of_lis(nums: List[int]) -> int:
    """
    最长递增子序列：dp[i]=以 nums[i] 结尾的 LIS 长度。
    dp[i] = 1 + max{ dp[j] : j



  六、小结
  DP 针对重叠子问题，用记忆化或递推避免重复计算。先定义状态、再写转移方程与边界、确定计算顺序。下一章讲贪心算法。

  七、例题
  以下例题使用 Python 3 类型标注与注释。

  
    例题 1：最小路径和
    题目描述：m×n 网格，从左上到右下只能向右或向下走，路径上数字和为路径和。求最小路径和。
    思路：dp[i][j]=从 (0,0) 到 (i,j) 的最小路径和；dp[i][j]=grid[i][j]+min(dp[i-1][j], dp[i][j-1])，边界为第一行第一列累加。
    from typing import List


def min_path_sum(grid: List[List[int]]) -> int:
    """dp[i][j]=到(i,j)的最小路径和；可原地用 grid 或新开二维表，也可压成一维（按行扫）。"""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp: List[int] = [0] * cols
    dp[0] = grid[0][0]
    for j in range(1, cols):
        dp[j] = dp[j - 1] + grid[0][j]
    for i in range(1, rows):
        dp[0] += grid[i][0]
        for j in range(1, cols):
            dp[j] = grid[i][j] + min(dp[j - 1], dp[j])
    return dp[cols - 1]
    讲解：每行只依赖上一行，用一维数组滚动即可。时间 O(m×n)，空间 O(n)。
  

  
    例题 2：打家劫舍
    题目描述：一排房屋，nums[i] 为第 i 家的金额，不能连续偷相邻两家。求能偷到的最大金额。
    思路：dp[i]=偷到第 i 家（含）为止的最大金额；dp[i]=max(dp[i-1], dp[i-2]+nums[i])，即不偷 i 或偷 i。
    from typing import List


def rob(nums: List[int]) -> int:
    """dp[i]=考虑前 i 家的最大金额；偷 i 则不能偷 i-1，不偷 i 则等于 dp[i-1]。"""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    a, b = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        a, b = b, max(b, a + nums[i])
    return b
    讲解：只依赖前两项，用两个变量滚动。时间 O(n)，空间 O(1)。
  

  
    例题 3：零钱兑换
    题目描述：不同面额硬币 coins，凑成金额 amount 所需的最少硬币数；若无法凑成返回 -1。
    思路：dp[w]=凑成金额 w 的最少硬币数。dp[w]=min{dp[w-c]+1 : c in coins 且 w≥c}，dp[0]=0，无法凑成的保持 inf。
    from typing import List


def coin_change(coins: List[int], amount: int) -> int:
    """dp[w]=凑成 w 的最少硬币数；dp[0]=0，dp[w]=min(dp[w-c]+1) for c in coins。"""
    INF = 10**9
    dp: List[int] = [INF] * (amount + 1)
    dp[0] = 0
    for w in range(1, amount + 1):
        for c in coins:
            if w >= c:
                dp[w] = min(dp[w], dp[w - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]
    讲解：按金额从小到大填表，保证算 dp[w] 时 dp[w-c] 已算好。时间 O(amount×len(coins))，空间 O(amount)。
  

  
    例题 4：最长公共子序列（LCS）
    题目描述：两个字符串 text1、text2，求最长公共子序列（不要求连续）的长度。
    思路：dp[i][j]=text1[0:i] 与 text2[0:j] 的 LCS 长度。若 text1[i-1]==text2[j-1] 则 dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。
    from typing import List


def longest_common_subsequence(text1: str, text2: str) -> int:
    """dp[i][j]=text1[:i] 与 text2[:j] 的 LCS 长度；可压成两行或一行（需保留上一行）。"""
    m, n = len(text1), len(text2)
    dp: List[int] = [0] * (n + 1)
    for i in range(1, m + 1):
        prev = 0
        for j in range(1, n + 1):
            tmp = dp[j]
            if text1[i - 1] == text2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = tmp
    return dp[n]
    讲解：按行递推，dp[j] 用到了上一行的 dp[j-1] 和「上一行同列的旧值」，用 prev 保存。时间 O(m×n)，空间 O(n)。
  

  
    ← 上一章：递归与分治
    目录
    下一章：贪心算法 →