动态规划算法精讲：从理论到实战

动态规划核心思想

什么是动态规划？

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

适用条件

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：子问题重复出现
3. 无后效性：一旦某个状态确定，就不受之后决策的影响

DP 三要素

1. 状态定义：如何描述子问题
2. 状态转移方程：子问题之间的关系
3. 初始条件和边界：最小子问题的解

经典问题解析

1. 斐波那契数列

递归解法（低效）

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

# 时间复杂度：O(2^n)
# 空间复杂度：O(n)（递归栈）
​

DP 解法（高效）

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]

# 时间复杂度：O(n)
# 空间复杂度：O(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

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

2. 爬楼梯问题

问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

# 空间优化版本
def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    
    return curr
​

3. 零钱兑换

问题描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

def coin_change(coins, amount):
    # dp[i] 表示凑成金额 i 所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# 示例
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出: 3 (5 + 5 + 1)
​

状态转移：

• 对于每个硬币面值 coin
• 对于金额 i 从 coin 到 amount
• dp[i] = min(dp[i], dp[i - coin] + 1)

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

问题描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。

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

# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))  # 输出: 4 ([2, 3, 7, 101])
​

优化版本（二分查找）：

import bisect

def length_of_lis_optimized(nums):
    tails = []
    
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    
    return len(tails)

# 时间复杂度：O(n log n)
​

5. 最长公共子序列（LCS）

问题描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的 LCS 长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

# 空间优化版本
def longest_common_subsequence_optimized(text1, text2):
    m, n = len(text1), len(text2)
    
    if m < n:
        text1, text2 = text2, text1
        m, n = n, m
    
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)
    
    return prev[n]
​

6. 背包问题

0-1 背包

def knapsack_01(weights, values, capacity):
    n = len(weights)
    
    # dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
    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],  # 不选第 i 个物品
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  # 选第 i 个物品
                )
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][capacity]

# 空间优化版本（一维数组）
def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        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):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        for w in range(weights[i], capacity + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]
​

DP 常见优化技巧

1. 状态压缩

棋盘 DP 示例：

# 使用位运算压缩状态
def solve_grid_dp(grid):
    n, m = len(grid), len(grid[0])
    
    # 用整数表示列的使用状态
    dp = {}
    
    def dfs(row, cols_mask, diag1_mask, diag2_mask):
        if row == n:
            return 0
        
        key = (row, cols_mask, diag1_mask, diag2_mask)
        if key in dp:
            return dp[key]
        
        max_count = 0
        for col in range(m):
            cols_bit = 1 << col
            diag1_bit = 1 << (row + col)
            diag2_bit = 1 << (row - col + m - 1)
            
            if not (cols_mask & cols_bit or diag1_mask & diag1_bit or diag2_mask & diag2_bit):
                count = 1 + dfs(row + 1, cols_mask | cols_bit, 
                               diag1_mask | diag1_bit, diag2_mask | diag2_bit)
                max_count = max(max_count, count)
        
        dp[key] = max_count
        return max_count
    
    return dfs(0, 0, 0, 0)
​

2. 单调队列优化

适用于滑动窗口最值问题：

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []
    
    dq = deque()  # 存储索引
    result = []
    
    for i, num in enumerate(nums):
        # 移除超出窗口的元素
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 移除比当前元素小的索引
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # 记录窗口最大值
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result
​

3. 斜率优化

适用于特定 DP 转移：

# 示例：优化 1D/1D DP
# dp[i] = min(dp[j] + cost(j + 1, i)) for j < i

# 当 cost 满足四边形不等式时，可以使用斜率优化
# 将时间复杂度从 O(n²) 降低到 O(n) 或 O(n log n)
​

实战技巧

1. 识别 DP 问题

特征：

• 求最优解（最大、最小）
• 求方案数
• 求可行性
• 有重叠子问题

2. DP 解题步骤

1. 定义状态：明确 dp 数组含义
2. 找出转移：列出状态转移方程
3. 确定顺序：决定遍历顺序
4. 初始边界：设置初始条件
5. 优化空间：考虑空间优化

3. 常见陷阱

• 边界条件：注意数组越界
• 初始化：正确的初始值
• 状态定义：避免冗余状态
• 整数溢出：大数问题使用模运算

练习题推荐

入门级

• 爬楼梯
• 使用最小花费爬楼梯
• 打家劫舍

中级

• 零钱兑换
• 完全平方数
• 最长递增子序列

高级

• 编辑距离
• 不同的子序列
• 最大正方形

总结

动态规划是算法设计的重要方法：

1. 核心思想：分解问题、存储结果、避免重复计算
2. 关键步骤：状态定义、转移方程、边界条件
3. 优化方向：空间优化、状态压缩、数据结构优化
4. 实践要点：多练习、总结模式、灵活应用

记住：DP 是一种思维方式，不仅仅是模板！