动态规划 (Dynamic Programming)

dynamic programmingDPLeetCodealgorithminterview

动态规划 (Dynamic Programming)

动态规划是一种通过将复杂问题分解为子问题，并存储子问题的解来避免重复计算的算法设计方法。

基础概念

核心要素

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：同一个子问题在递归过程中被重复计算
  3. 状态转移：从已知状态推导新状态的过程

常见类型

  1. 线性DP：状态与前几个状态有关
dp[i] = f(dp[i-1], dp[i-2], ...)
  1. 区间DP：状态与区间两端有关
dp[i][j] = f(dp[i+1][j], dp[i][j-1], ...)
  1. 背包DP：状态与容量和选择有关
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

解题步骤

  1. 定义状态：明确dp数组含义
  2. 状态转移：写出状态转移方程
  3. 初始化：设置初始状态
  4. 遍历顺序：确定计算顺序
  5. 返回结果：获取最终答案

经典问题

1. 爬楼梯（线性DP）

LeetCode 70 - Climbing Stairs

状态转移过程:

n = 5的所有可能:
1,1,1,1,1
1,1,1,2
1,1,2,1
1,2,1,1
2,1,1,1
1,2,2
2,1,2
2,2,1

dp[i] = dp[i-1] + dp[i-2]

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
dp[5] = 8
def climbStairs(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]

2. 零钱兑换（完全背包）

LeetCode 322 - Coin Change

状态转移过程:

coins = [1,2,5], amount = 11

dp[i]: 凑成金额i所需的最少硬币数

dp[0] = 0
dp[1] = 1    (1)
dp[2] = 1    (2)
dp[3] = 2    (1+2)
dp[4] = 2    (2+2)
dp[5] = 1    (5)
dp[6] = 2    (5+1)
...
dp[11] = 3   (5+5+1)
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
            
    return dp[amount] if dp[amount] != float('inf') else -1

3. 最长回文子串（区间DP）

LeetCode 5 - Longest Palindromic Substring

状态转移过程:

s = "babad"

dp[i][j]: s[i:j+1]是否为回文串

  b a b a d
b T F T F F
a   T F T F
b     T F F
a       T F
d         T

最长回文子串: "bab" 或 "aba"
def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    # 单个字符都是回文
    for i in range(n):
        dp[i][i] = True
    
    # 检查长度为2及以上的子串
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if length == 2:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
            
            if dp[i][j] and length > max_len:
                start = i
                max_len = length
    
    return s[start:start + max_len]

4. 编辑距离（双序列DP）

LeetCode 72 - Edit Distance

状态转移过程:

word1 = "horse", word2 = "ros"

dp[i][j]: word1前i个字符转换到word2前j个字符需要的最少操作数

    ∅ r o s
∅   0 1 2 3
h   1 1 2 3
o   2 2 1 2
r   3 2 2 2
s   4 3 3 2
e   5 4 4 3

操作过程:
1. horse -> rorse (替换'h'为'r')
2. rorse -> rose (删除'r')
3. rose -> ros (删除'e')
def minDistance(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] = min(
                    dp[i-1][j] + 1,    # 删除
                    dp[i][j-1] + 1,    # 插入
                    dp[i-1][j-1] + 1   # 替换
                )
    
    return dp[m][n]

常见DP类型

1. 线性DP

  • 斐波那契数列
  • 最大子数组和
  • 打家劫舍

2. 区间DP

  • 最长回文子串
  • 戳气球
  • 矩阵链乘法

3. 背包问题

  • 0-1背包
  • 完全背包
  • 多重背包

4. 状态压缩DP

  • 旅行商问题
  • 集合覆盖
  • 状态游戏

5. 树形DP

  • 树的最大独立集
  • 树的最小支配集
  • 树的最小顶点覆盖

优化技巧

  1. 状态压缩：使用位运算表示状态
  2. 空间优化：使用滚动数组
  3. 记忆化搜索：自顶向下的DP
  4. 单调队列/栈优化
  5. 斜率优化

相关题目