动态规划基础

什么是动态规划？

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

动态规划的核心思想：

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：递归求解时会重复计算相同的子问题
  3. 状态转移方程：建立子问题之间的关系

动态规划 vs 分治法：

  • 分治法：子问题相互独立，不重叠
  • 动态规划：子问题重叠，通过记忆化避免重复计算

动态规划 vs 贪心算法：

  • 贪心算法：每次选择局部最优，不保证全局最优
  • 动态规划：考虑所有可能的选择，保证全局最优

动态规划的适用场景

  1. 最优化问题：求最大值、最小值、最优方案
  2. 计数问题：求方案数、路径数
  3. 可行性问题：判断是否存在满足条件的方案
  4. 重叠子问题：递归求解时会有重复计算

动态规划的基本步骤

  1. 定义状态：dp[i] 或 dp[i][j] 表示什么
  2. 状态转移方程：如何从子问题的解得到当前问题的解
  3. 初始状态：边界条件的初始化
  4. 计算顺序：确保计算 dp[i] 时，需要的子问题已经求解
  5. 返回结果：dp[n] 或 dp[m][n] 等

一维动态规划

1. 斐波那契数列（Fibonacci）

问题描述： 求第 n 个斐波那契数。

递归解法（时间复杂度 O(2ⁿ)）：

1
2
3
4
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

动态规划解法（时间复杂度 O(n)）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def fibonacci_dp(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 空间优化版本（O(1) 空间）
def fibonacci_optimized(n):
    if n <= 1:
        return n
    
    prev2 = 0  # f(0)
    prev1 = 1  # f(1)
    
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    
    return prev1

2. 爬楼梯（Climbing Stairs）

问题描述： 每次可以爬 1 或 2 个台阶，求爬到第 n 阶有多少种方法。

状态定义： dp[i] 表示爬到第 i 阶的方法数

状态转移方程： dp[i] = dp[i-1] + dp[i-2]

初始状态： dp[0] = 1, dp[1] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def climb_stairs(n):
    if n <= 1:
        return 1
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 空间优化版本
def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    
    prev2 = 1
    prev1 = 1
    
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    
    return prev1

扩展：每次可以爬 1、2 或 3 个台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def climb_stairs_3(n):
    if n <= 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    
    return dp[n]

3. 最大子数组和（Maximum Subarray）

问题描述： 给定一个整数数组，找出连续子数组的最大和。

状态定义： dp[i] 表示以第 i 个元素结尾的最大子数组和

状态转移方程： dp[i] = max(nums[i], dp[i-1] + nums[i])

初始状态： dp[0] = nums[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def max_subarray(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    
    for i in range(1, n):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
    
    return max(dp)

# 空间优化版本（O(1) 空间）
def max_subarray_optimized(nums):
    if not nums:
        return 0
    
    max_sum = nums[0]
    curr_sum = nums[0]
    
    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)
    
    return max_sum

4. 打家劫舍（House Robber）

问题描述： 不能抢劫相邻的两间房屋，求能抢劫的最大金额。

状态定义： dp[i] 表示抢劫到第 i 间房屋时的最大金额

状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i])

初始状态： dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    
    return dp[n - 1]

# 空间优化版本
def rob_optimized(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    
    return prev1

5. 零钱兑换（Coin Change）

问题描述： 给定不同面额的硬币和总金额，求最少需要的硬币数。

状态定义： dp[i] 表示凑成金额 i 的最少硬币数

状态转移方程： dp[i] = min(dp[i], dp[i - coin] + 1) for coin in coins

初始状态： dp[0] = 0, dp[i] = float(‘inf’) for i > 0

1
2
3
4
5
6
7
8
9
10
11
12
13
def coin_change(coins, amount):
    if amount == 0:
        return 0
    
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

扩展：零钱兑换 II（求方案数）

1
2
3
4
5
6
7
8
9
def coin_change_2(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

6. 最长递增子序列（Longest Increasing Subsequence）

问题描述： 求数组中最长递增子序列的长度。

状态定义： dp[i] 表示以第 i 个元素结尾的最长递增子序列长度

状态转移方程： dp[i] = max(dp[j] + 1) for j in range(i) if nums[j] < nums[i]

初始状态： dp[i] = 1 for all i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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)

# 优化版本（O(n log n)）
def length_of_lis_optimized(nums):
    if not nums:
        return 0
    
    tails = []  # tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
    
    for num in nums:
        # 二分查找插入位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    
    return len(tails)

7. 解码方法（Decode Ways）

问题描述： 给定一个数字字符串，求解码方法数（1->A, 2->B, …, 26->Z）。

状态定义： dp[i] 表示前 i 个字符的解码方法数

状态转移方程：

  • 如果 s[i] != ‘0’: dp[i] += dp[i-1]
  • 如果 10 <= int(s[i-1:i+1]) <= 26: dp[i] += dp[i-2]

初始状态： dp[0] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def num_decodings(s):
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    
    for i in range(2, n + 1):
        # 单个字符
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        
        # 两个字符
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i - 2]
    
    return dp[n]

# 空间优化版本
def num_decodings_optimized(s):
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    prev2 = 1  # dp[0]
    prev1 = 1  # dp[1]
    
    for i in range(2, n + 1):
        curr = 0
        
        if s[i - 1] != '0':
            curr += prev1
        
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            curr += prev2
        
        prev2 = prev1
        prev1 = curr
    
    return prev1

二维动态规划

1. 不同路径（Unique Paths）

问题描述： 从左上角到右下角，只能向右或向下移动，求路径数。

状态定义： dp[i][j] 表示到达位置 (i, j) 的路径数

状态转移方程： dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始状态： dp[0][j] = 1, dp[i][0] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def unique_paths(m, n):
    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(n) 空间）
def unique_paths_optimized(m, n):
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    
    return dp[n - 1]

扩展：有障碍物的不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def unique_paths_with_obstacles(obstacle_grid):
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    
    if obstacle_grid[0][0] == 1 or obstacle_grid[m - 1][n - 1] == 1:
        return 0
    
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    
    # 初始化第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] if obstacle_grid[0][j] == 0 else 0
    
    # 初始化第一列
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] if obstacle_grid[i][0] == 0 else 0
    
    # 填充dp表
    for i in range(1, m):
        for j in range(1, n):
            if obstacle_grid[i][j] == 0:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    return dp[m - 1][n - 1]

2. 最小路径和（Minimum Path Sum）

问题描述： 从左上角到右下角，求路径上的数字和的最小值。

状态定义： dp[i][j] 表示到达位置 (i, j) 的最小路径和

状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

初始状态：

  • dp[0][0] = grid[0][0]
  • dp[0][j] = dp[0][j-1] + grid[0][j]
  • dp[i][0] = dp[i-1][0] + grid[i][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def min_path_sum(grid):
    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]
    
    # 填充dp表
    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(n) 空间）
def min_path_sum_optimized(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
    
    return dp[n - 1]

3. 最长公共子序列（Longest Common Subsequence）

问题描述： 求两个字符串的最长公共子序列的长度。

状态定义： dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度

状态转移方程：

  • 如果 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])

初始状态： dp[0][j] = 0, dp[i][0] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    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]

# 空间优化版本（O(min(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)
    
    for i in range(1, m + 1):
        curr = [0] * (n + 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
    
    return prev[n]

4. 最长公共子串（Longest Common Substring）

问题描述： 求两个字符串的最长公共子串的长度。

状态定义： dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串长度

状态转移方程：

  • 如果 text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
  • 否则: dp[i][j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
def longest_common_substring(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    
    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
                max_len = max(max_len, dp[i][j])
    
    return max_len

5. 编辑距离（Edit Distance）

问题描述： 将 word1 转换为 word2 的最少操作次数（插入、删除、替换）。

状态定义： dp[i][j] 表示 word1[0:i] 转换为 word2[0:j] 的最少操作数

状态转移方程：

  • 如果 word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
  • 否则: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    • dp[i-1][j]: 删除
    • dp[i][j-1]: 插入
    • dp[i-1][j-1]: 替换

初始状态：

  • dp[0][j] = j（插入 j 个字符）
  • dp[i][0] = i（删除 i 个字符）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def min_distance(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
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充dp表
    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] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )
    
    return dp[m][n]

# 空间优化版本
def min_distance_optimized(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))
    
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    
    return prev[n]

6. 最大正方形（Maximal Square）

问题描述： 在 0-1 矩阵中，求只包含 1 的最大正方形的面积。

状态定义： dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长

状态转移方程：

  • 如果 matrix[i][j] == ‘1’:
    • dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  • 否则: dp[i][j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def maximal_square(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_side = max(max_side, dp[i][j])
    
    return max_side * max_side

# 空间优化版本
def maximal_square_optimized(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    prev = [0] * n
    max_side = 0
    
    for i in range(m):
        curr = [0] * n
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    curr[j] = 1
                else:
                    curr[j] = min(prev[j], curr[j - 1], prev[j - 1]) + 1
                max_side = max(max_side, curr[j])
        prev = curr
    
    return max_side * max_side

7. 正则表达式匹配（Regular Expression Matching）

问题描述： 判断字符串是否匹配正则表达式（支持 ‘.’ 和 ‘*’）。

状态定义： dp[i][j] 表示 s[0:i] 是否匹配 p[0:j]

状态转移方程：

  • 如果 p[j-1] == ‘*’:
    • dp[i][j] = dp[i][j-2]（* 匹配 0 次）
    • 或 dp[i-1][j] if s[i-1] == p[j-2] or p[j-2] == ‘.’（* 匹配多次）
  • 否则:
    • dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == ‘.’)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # 空字符串匹配空模式
    dp[0][0] = True
    
    # 处理 a*b*c* 这样的模式匹配空字符串
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # * 匹配 0 次
                dp[i][j] = dp[i][j - 2]
                # * 匹配 1 次或多次
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            else:
                # 普通字符或 .
                if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
    
    return dp[m][n]

背包问题

1. 0-1 背包问题（0-1 Knapsack）

问题描述： 有 n 个物品，每个物品有重量和价值，在容量为 W 的背包中能装入的最大价值。

状态定义： dp[i][w] 表示前 i 个物品在容量为 w 时的最大价值

状态转移方程：

  • 如果 weights[i-1] <= w:
    • dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
  • 否则: dp[i][w] = dp[i-1][w]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def knapsack_01(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(1, 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):
    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]

2. 完全背包问题（Unbounded Knapsack）

问题描述： 每个物品可以无限次使用，求最大价值。

状态定义： dp[w] 表示容量为 w 时的最大价值

状态转移方程： dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

1
2
3
4
5
6
7
8
9
10
def knapsack_unbounded(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

3. 多重背包问题（Multiple Knapsack）

问题描述： 每个物品有数量限制，求最大价值。

方法： 转换为 0-1 背包问题，或使用二进制优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def knapsack_multiple(weights, values, counts, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 二进制优化
        k = 1
        while k < counts[i]:
            weight = weights[i] * k
            value = values[i] * k
            for w in range(capacity, weight - 1, -1):
                dp[w] = max(dp[w], dp[w - weight] + value)
            counts[i] -= k
            k *= 2
        
        # 剩余部分
        if counts[i] > 0:
            weight = weights[i] * counts[i]
            value = values[i] * counts[i]
            for w in range(capacity, weight - 1, -1):
                dp[w] = max(dp[w], dp[w - weight] + value)
    
    return dp[capacity]

区间动态规划

1. 最长回文子串（Longest Palindromic Substring）

问题描述： 求字符串的最长回文子串。

状态定义： dp[i][j] 表示 s[i:j+1] 是否为回文串

状态转移方程：

  • 如果 s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): dp[i][j] = True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def longest_palindrome(s):
    if not s:
        return ""
    
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    
    # 单个字符都是回文
    for i in range(n):
        dp[i][i] = True
    
    # 检查长度为 2 的子串
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # 检查长度 >= 3 的子串
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_len = length
    
    return s[start:start + max_len]

# 中心扩展法（O(1) 空间）
def longest_palindrome_center(s):
    if not s:
        return ""
    
    start = 0
    max_len = 1
    
    for i in range(len(s)):
        # 奇数长度
        len1 = expand_around_center(s, i, i)
        # 偶数长度
        len2 = expand_around_center(s, i, i + 1)
        
        length = max(len1, len2)
        if length > max_len:
            max_len = length
            start = i - (length - 1) // 2
    
    return s[start:start + max_len]

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

2. 最长回文子序列（Longest Palindromic Subsequence）

问题描述： 求字符串的最长回文子序列的长度。

状态定义： dp[i][j] 表示 s[i:j+1] 的最长回文子序列长度

状态转移方程：

  • 如果 s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  • 否则: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 单个字符的回文长度为 1
    for i in range(n):
        dp[i][i] = 1
    
    # 从长度为 2 开始
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    return dp[0][n - 1]

# 空间优化版本
def longest_palindrome_subseq_optimized(s):
    n = len(s)
    prev = [0] * n
    
    for i in range(n - 1, -1, -1):
        curr = [0] * n
        curr[i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                curr[j] = prev[j - 1] + 2
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    
    return prev[n - 1]

3. 矩阵链乘法（Matrix Chain Multiplication）

问题描述： 给定矩阵链，求最少的乘法次数。

状态定义： dp[i][j] 表示计算矩阵 A[i]…A[j] 的最少乘法次数

状态转移方程：

  • dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]) for k in [i, j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def matrix_chain_order(p):
    n = len(p) - 1  # 矩阵个数
    dp = [[0] * n for _ in range(n)]
    
    # length 是矩阵链的长度
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n - 1]

树形动态规划

1. 打家劫舍 III（House Robber III）

问题描述： 二叉树中，不能抢劫相邻的节点，求最大金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob_tree(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (不抢劫当前节点, 抢劫当前节点)
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # 不抢劫当前节点：可以抢劫或不抢劫子节点
        not_rob = max(left) + max(right)
        
        # 抢劫当前节点：不能抢劫子节点
        rob = node.val + left[0] + right[0]
        
        return (not_rob, rob)
    
    return max(dfs(root))

2. 二叉树中的最大路径和

问题描述： 求二叉树中任意节点到任意节点的路径的最大和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def max_path_sum(root):
    max_sum = float('-inf')
    
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        
        # 左右子树的最大贡献值（如果为负则舍弃）
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        
        # 经过当前节点的最大路径和
        path_sum = node.val + left + right
        max_sum = max(max_sum, path_sum)
        
        # 返回当前节点的最大贡献值
        return node.val + max(left, right)
    
    dfs(root)
    return max_sum

状态压缩动态规划

1. 旅行商问题（TSP）

问题描述： 访问所有城市一次且回到起点，求最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def tsp(dist):
    n = len(dist)
    # dp[mask][i] 表示访问了 mask 中的城市，当前在城市 i 的最短路径
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # 初始化：从任意城市开始
    for i in range(n):
        dp[1 << i][i] = 0
    
    # 枚举所有状态
    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if not (mask & (1 << j)):
                        new_mask = mask | (1 << j)
                        dp[new_mask][j] = min(
                            dp[new_mask][j],
                            dp[mask][i] + dist[i][j]
                        )
    
    # 返回访问所有城市后回到起点 0 的最短路径
    final_mask = (1 << n) - 1
    min_cost = float('inf')
    for i in range(1, n):
        min_cost = min(min_cost, dp[final_mask][i] + dist[i][0])
    
    return min_cost

常见面试题

1. 买卖股票的最佳时机系列

买卖股票的最佳时机（一次交易）

1
2
3
4
5
6
7
8
9
10
11
12
def max_profit_1(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

买卖股票的最佳时机 II（无限次交易）

1
2
3
4
5
6
def max_profit_2(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

买卖股票的最佳时机 III（最多两次交易）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def max_profit_3(prices):
    if not prices:
        return 0
    
    # dp[i][k][0] 表示第 i 天，最多 k 次交易，不持有股票的最大利润
    # dp[i][k][1] 表示第 i 天，最多 k 次交易，持有股票的最大利润
    
    n = len(prices)
    dp = [[[0] * 2 for _ in range(3)] for _ in range(n)]
    
    # 初始化
    for k in range(3):
        dp[0][k][0] = 0
        dp[0][k][1] = -prices[0]
    
    for i in range(1, n):
        for k in range(1, 3):
            # 不持有：前一天不持有 或 前一天持有今天卖出
            dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
            # 持有：前一天持有 或 前一天不持有今天买入
            dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    
    return dp[n - 1][2][0]

买卖股票的最佳时机 IV（最多 k 次交易）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def max_profit_4(k, prices):
    if not prices or k == 0:
        return 0
    
    n = len(prices)
    
    # 如果 k >= n//2，相当于无限次交易
    if k >= n // 2:
        return max_profit_2(prices)
    
    # dp[i][j][0] 表示第 i 天，最多 j 次交易，不持有股票
    # dp[i][j][1] 表示第 i 天，最多 j 次交易，持有股票
    dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]
    
    # 初始化
    for j in range(k + 1):
        dp[0][j][0] = 0
        dp[0][j][1] = -prices[0]
    
    for i in range(1, n):
        for j in range(1, k + 1):
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
    
    return dp[n - 1][k][0]

2. 单词拆分（Word Break）

问题描述： 判断字符串是否可以由字典中的单词组成。

1
2
3
4
5
6
7
8
9
10
11
12
13
def word_break(s, word_dict):
    word_set = set(word_dict)
    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]

3. 分割回文串（Palindrome Partitioning）

问题描述： 将字符串分割成回文子串，求最少的分割次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def min_cut(s):
    n = len(s)
    
    # 预处理：判断是否是回文
    is_palindrome = [[False] * n for _ in range(n)]
    for i in range(n):
        is_palindrome[i][i] = True
        if i < n - 1 and s[i] == s[i + 1]:
            is_palindrome[i][i + 1] = True
    
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and is_palindrome[i + 1][j - 1]:
                is_palindrome[i][j] = True
    
    # dp[i] 表示 s[0:i] 的最少分割次数
    dp = [0] * (n + 1)
    
    for i in range(1, n + 1):
        if is_palindrome[0][i - 1]:
            dp[i] = 0
        else:
            dp[i] = i - 1
            for j in range(i):
                if is_palindrome[j][i - 1]:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n]

4. 不同路径 III（Unique Paths III）

问题描述： 在网格中从起点到终点，经过所有非障碍格子一次，求路径数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def unique_paths_3(grid):
    m, n = len(grid), len(grid[0])
    start = None
    empty = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                start = (i, j)
            elif grid[i][j] == 0:
                empty += 1
    
    def dfs(x, y, remaining):
        if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == -1:
            return 0
        
        if grid[x][y] == 2:
            return 1 if remaining == 0 else 0
        
        grid[x][y] = -1  # 标记为已访问
        paths = (
            dfs(x + 1, y, remaining - 1) +
            dfs(x - 1, y, remaining - 1) +
            dfs(x, y + 1, remaining - 1) +
            dfs(x, y - 1, remaining - 1)
        )
        grid[x][y] = 0  # 回溯
        
        return paths
    
    return dfs(start[0], start[1], empty + 1)

5. 戳气球（Burst Balloons）

问题描述： 戳破气球，获得 coins[left] * coins[i] * coins[right] 的分数，求最大分数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def max_coins(nums):
    # 添加边界气球
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    # dp[i][j] 表示戳破 (i, j) 区间内所有气球的最大分数
    dp = [[0] * n for _ in range(n)]
    
    # length 是区间长度
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i + 1, j):
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                )
    
    return dp[0][n - 1]

动态规划优化技巧

1. 空间优化

一维 DP 优化为 O(1)：

1
2
3
4
5
6
# 优化前：O(n) 空间
dp = [0] * (n + 1)

# 优化后：O(1) 空间
prev2 = 0
prev1 = 1

二维 DP 优化为 O(n)：

1
2
3
4
5
6
7
8
9
# 优化前：O(m * n) 空间
dp = [[0] * n for _ in range(m)]

# 优化后：O(n) 空间
prev = [0] * n
for i in range(m):
    curr = [0] * n
    # 计算 curr
    prev = curr

2. 状态压缩

使用位运算压缩状态：

1
2
3
4
5
6
7
8
9
10
11
12
# 表示集合 {0, 2, 3}
mask = (1 << 0) | (1 << 2) | (1 << 3)

# 判断元素 i 是否在集合中
if mask & (1 << i):
    pass

# 添加元素 i 到集合
mask |= (1 << i)

# 从集合中删除元素 i
mask &= ~(1 << i)

3. 滚动数组

交替使用两个数组：

1
2
3
4
5
6
7
8
9
10
11
dp0 = [0] * n
dp1 = [0] * n

for i in range(m):
    for j in range(n):
        if i % 2 == 0:
            # 使用 dp0 计算 dp1
            dp1[j] = ...
        else:
            # 使用 dp1 计算 dp0
            dp0[j] = ...

总结

核心要点：

  1. 动态规划的特点：

    • 最优子结构
    • 重叠子问题
    • 状态转移方程

  2. DP 类型：

    • 一维 DP：线性问题
    • 二维 DP：矩阵、字符串问题
    • 背包问题：0-1、完全、多重背包
    • 区间 DP：回文、矩阵链乘法
    • 树形 DP：二叉树问题
    • 状态压缩 DP：TSP 等

  3. 优化技巧：

    • 空间优化（降维）
    • 状态压缩（位运算）
    • 滚动数组

面试重点：

  • 经典的 DP 问题（爬楼梯、打家劫舍、最长子序列）
  • 背包问题的变体
  • 字符串相关的 DP（编辑距离、LCS）
  • 二维 DP 问题（路径问题）
  • DP 的空间优化

解题步骤：

  1. 定义状态：dp[i] 或 dp[i][j] 表示什么
  2. 状态转移方程：如何从子问题得到当前问题
  3. 初始状态：边界条件
  4. 计算顺序：确保子问题已求解
  5. 返回结果：最终的答案

实际应用：

在实际项目中：

  • 路径规划：最短路径、路径计数
  • 资源分配：背包问题、任务调度
  • 字符串处理：编辑距离、匹配问题
  • 优化问题：最大收益、最小成本

参考资料：

  • 《算法导论》（Introduction to Algorithms）
  • 《动态规划算法设计与优化》（Dynamic Programming）
  • LeetCode 动态规划专题
  • 《算法竞赛进阶指南》