动态规划

什么是动态规划

动态规划（Dynamic Programming，DP）是一种将复杂问题分解为子问题，并存储子问题解以避免重复计算的算法思想。

核心条件：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：子问题会被多次计算

DP 入门：斐波那契数列

暴力递归（指数级）

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)
# 时间复杂度：O(2^n)，存在大量重复计算

记忆化递归（自顶向下）

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
# 时间复杂度：O(n)，空间：O(n)

动态规划（自底向上）

def fib_dp(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]

# 空间优化：只需要前两个值
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

DP 问题的解题步骤

1. 确定 dp 数组及其含义
2. 确定递推公式
3. 确定初始值
4. 确定遍历顺序
5. 举例验证

经典问题

1. 爬楼梯

def climb_stairs(n):
    """
    每次可以爬 1 或 2 个台阶，问爬到第 n 阶有多少种方法
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 测试
print(climb_stairs(5))  # 8

2. 不同路径（机器人路径）

def unique_paths(m, n):
    """
    机器人从左上角到右下角，只能向右或向下走
    """
    dp = [[0] * n for _ in range(m)]
    
    # 初始化第一行和第一列
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    # 填充其他格子
    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]

# 空间优化：一维数组
def unique_paths_optimized(m, n):
    dp = [1] * n
    
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    
    return dp[n-1]

# 有障碍物的情况
def unique_paths_with_obstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

3. 最大子数组和

def max_subarray(nums):
    """
    找到连续子数组的最大和
    经典 DP 问题
    """
    if not nums:
        return 0
    
    # dp[i] 表示以第 i 个元素结尾的最大子数组和
    dp = nums[0]
    max_sum = dp
    
    for i in range(1, len(nums)):
        dp = max(nums[i], dp + nums[i])
        max_sum = max(max_sum, dp)
    
    return max_sum

# 测试
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6 ([4, -1, 2, 1])

# 返回具体子数组
def max_subarray_with_indices(nums):
    start = end = 0
    max_sum = float('-inf')
    current_sum = 0
    current_start = 0
    
    for i, num in enumerate(nums):
        if current_sum + num < num:
            current_sum = num
            current_start = i
        else:
            current_sum += num
        
        if current_sum > max_sum:
            max_sum = current_sum
            start = current_start
            end = i
    
    return max_sum, nums[start:end+1]

4. 买卖股票的最佳时机

def max_profit(prices):
    """
    最多只能买一股，求最大利润
    只能先买后卖
    """
    if not prices:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    
    return max_profit

# 多次买卖（冷冻期）
def max_profit_with_cooldown(prices):
    """
    卖出后有一天冷冻期，不能第二天买入
    """
    if not prices:
        return 0
    
    n = len(prices)
    dp = [[0] * 3 for _ in range(n)]
    # dp[i][0]: 持有股票
    # dp[i][1]: 不持有股票，处于冷冻期
    # dp[i][2]: 不持有股票，不在冷冻期
    
    dp[0][0] = -prices[0]
    
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
        dp[i][1] = dp[i-1][0] + prices[i]
        dp[i][2] = max(dp[i-1][1], dp[i-1][2])
    
    return max(dp[n-1][1], dp[n-1][2])

5. 最长递增子序列（LIS）

def length_of_lis(nums):
    """
    找到最长递增子序列的长度
    """
    if not nums:
        return 0
    
    # dp[i] 表示以第 i 个元素结尾的 LIS 长度
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 二分优化：O(n log n)
import bisect

def length_of_lis_binary(nums):
    """
    使用二分查找优化
    tails[i] 表示长度为 i+1 的递增子序列的最小尾部值
    """
    if not nums:
        return 0
    
    tails = []
    
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

# 测试
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2, 3, 7, 101])

6. 背包问题

0-1 背包

def knapsack_01(weights, values, capacity):
    """
    0-1 背包问题
    weights: 物品重量列表
    values: 物品价值列表
    capacity: 背包容量
    
    每个物品只能选一次
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# 空间优化：一维数组（倒序遍历）
def knapsack_01_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

完全背包

def knapsack_complete(weights, values, capacity):
    """
    完全背包问题
    每个物品可以选无限次
    """
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# 零钱兑换 II：有多少种凑法
def change(amount, coins):
    """
    有多少种方式可以凑成 amount
    """
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    
    return dp[amount]

# 最小路径和
def min_path_sum(grid):
    """
    从左上角到右下角的最小路径和
    只能向右或向下走
    """
    m, n = len(grid), len(grid[0])
    
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            elif i == 0:
                grid[i][j] += grid[i][j-1]
            elif j == 0:
                grid[i][j] += grid[i-1][j]
            else:
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    
    return grid[m-1][n-1]

7. 打家劫舍

def rob(nums):
    """
    不能偷相邻的两家，最大偷窃金额
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    prev2 = 0
    prev1 = nums[0]
    
    for i in range(1, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    
    return prev1

# 打家劫舍 II（环形）
def rob_circle(nums):
    """
    房子围成一圈，不能偷相邻两家
    分类讨论：偷第一家和偷第二家
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    def rob_linear(nums):
        prev2, prev1 = 0, nums[0]
        for num in nums[1:]:
            curr = max(prev1, prev2 + num)
            prev2, prev1 = prev1, curr
        return prev1
    
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

8. 编辑距离

def min_distance(word1, word2):
    """
    将 word1 转换成 word2 的最少操作数
    操作：插入、删除、替换
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    for i in range(m + 1):
        dp[i][0] = i  # 删除 i 个字符
    for j in range(n + 1):
        dp[0][j] = j  # 插入 j 个字符
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # 删除
                    dp[i][j-1] + 1,    # 插入
                    dp[i-1][j-1] + 1   # 替换
                )
    
    return dp[m][n]

# 测试
print(min_distance("horse", "ros"))   # 3 (horse->rorse->rose->ros)

DP 总结

问题	状态定义	递推公式
爬楼梯	dp[i] 到达第 i 阶	dp[i] = dp[i-1] + dp[i-2]
最大子数组和	dp[i] 以 i 结尾的最大和	dp[i] = max(nums[i], dp[i-1] + nums[i])
0-1 背包	dp[i][w] 前 i 个物品容量 w	dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)
LIS	dp[i] 以 i 结尾的 LIS 长度	dp[i] = max(dp[j] + 1), j < i
打家劫舍	dp[i] 到第 i 家的最大收益	dp[i] = max(dp[i-1], dp[i-2] + nums[i])
编辑距离	dp[i][j] 前 i/j 个字符	分类讨论

[[返回算法首页|algorithm/index]]