动态规划算法精讲

动态规划是解决最优化问题的强大算法范式，通过将复杂问题分解为子问题来高效求解。

1. 核心思想

两个关键特征

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：子问题重复出现，可缓存结果避免重复计算

DP与分治的区别

• 分治：子问题独立（如归并排序）
• DP：子问题重叠（如斐波那契数列）

2. 解题四步法

步骤1：定义状态

# 爬楼梯问题
# 状态定义：dp[i] = 到达第i阶的方法数

# 背包问题
# 状态定义：dp[i][w] = 前i个物品，容量为w时的最大价值
​

步骤2：状态转移方程

# 爬楼梯
dp[i] = dp[i-1] + dp[i-2]  # 从i-1或i-2爬上来

# 01背包
if w < weight[i]:
    dp[i][w] = dp[i-1][w]  # 不选第i个物品
else:
    dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
​

步骤3：初始化

# 爬楼梯
dp[0] = 1  # 地面
dp[1] = 1  # 第1阶

# 背包
dp[0][w] = 0  # 没有物品
dp[i][0] = 0  # 容量为0
​

步骤4：计算顺序

# 从小到大
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
​

3. 经典问题

LIS（最长递增子序列）

def length_of_lis(nums):
    if not nums:
        return 0
    
    # dp[i] = 以nums[i]结尾的最长递增子序列长度
    dp = [1] * len(nums)
    
    for i in range(1, 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)
def length_of_lis_optimized(nums):
    tails = []
    for num in nums:
        # 找到第一个>=num的位置
        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)
​

LCS（最长公共子序列）

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # dp[i][j] = text1[:i]和text2[: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]
​

股票买卖

# 最多交易k次
def max_profit_k_transactions(prices, k):
    if not prices or k == 0:
        return 0
    
    # dp[i][j] = 第i天，最多j次交易的最大利润
    # 0 = 不持有，1 = 持有
    dp = [[[0] * 2 for _ in range(k+1)] for _ in range(len(prices))]
    
    # 初始化：持有状态为负无穷
    for j in range(k+1):
        dp[0][j][1] = -prices[0]
    
    for i in range(1, len(prices)):
        for j in range(1, k+1):
            # 不持有：max(之前不持有，今天卖出)
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
            
            # 持有：max(之前持有，今天买入)
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
    
    return dp[-1][k][0]
​

4. 空间优化

滚动数组

# 01背包空间优化
def knapsack_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 min_cost(costs):
    if not costs:
        return 0
    
    # 只需要前一个状态
    prev = costs[0][:]
    
    for i in range(1, len(costs)):
        curr = [0, 0, 0]
        for j in range(3):
            curr[j] = costs[i][j] + min(
                prev[(j+1)%3],
                prev[(j+2)%3]
            )
        prev = curr
    
    return min(prev)
​

5. 常见状态设计

区间DP

# 矩阵链乘法
def matrix_chain_multiply(dimensions):
    n = len(dimensions) - 1
    
    # dp[i][j] = 矩阵i到j的最小乘法次数
    dp = [[0] * n for _ in range(n)]
    
    # 区间长度从2到n
    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] + 
                    dimensions[i] * dimensions[k+1] * dimensions[j+1]
                )
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]
​

状态机DP

# 股票买卖（可持有、可交易、冷却）
def max_profit_with_cooldown(prices):
    if not prices:
        return 0
    
    n = len(prices)
    
    # hold: 持有股票
    # sold: 刚卖出（进入冷却）
    # rest: 空仓且不在冷却
    hold = [0] * n
    sold = [0] * n
    rest = [0] * n
    
    hold[0] = -prices[0]
    
    for i in range(1, n):
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])
    
    return max(sold[-1], rest[-1])
​

6. 解题技巧

判断DP问题

• 问题求最优解（最大、最小、最长）
• 问题可以分解为子问题
• 子问题存在重叠

状态定义原则

• 状态要能唯一确定
• 状态转移要明确
• 边界条件要清晰

优化技巧

1. 空间优化：观察是否只需要前几个状态
2. 预处理：提前计算需要的信息
3. 单调性：利用数据单调性优化（如单调队列优化DP）

通过系统练习，可以掌握动态规划的核心思想，解决各类最优化问题。