动态规划（DP）深度解析

一、动态规划的本质与核心思想

1.1 什么是动态规划

动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题解以避免重复计算的优化技术。其核心特征包括：

• 最优子结构：问题的最优解包含子问题的最优解
• 重叠子问题：不同决策路径会重复遇到相同子问题
• 状态转移方程：定义问题状态间的递推关系

1.2 与其它算法的对比

方法	时间复杂度	适用场景	空间复杂度
暴力搜索	O(2^n)	小规模问题	O(n)
记忆化搜索	O(n*m)	树形结构问题	O(n*m)
动态规划	O(n*m)	序列决策问题	O(m)~O(n*m)
贪心算法	O(n)	具有贪心选择性质的问题	O(1)

---

二、动态规划的四大解题步骤

2.1 问题分解流程

1. 定义状态：明确dp数组的维度和含义
   （示例：dp[i][j]表示前i个物品在容量j时的最大价值）
2. 建立方程：找出状态转移关系
   （示例：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]))
3. 确定边界：初始化基础情况
   （示例：dp[0][...] = 0, dp[...][0] = 0）
4. 计算顺序：确定填表方向
   （示例：双重循环先遍历物品后遍历容量）

2.2 经典问题解析：最长公共子序列（LCS）

def longest_common_subsequence(text1: str, text2: str) -> int:
    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]

---

三、动态规划的六大优化技巧

3.1 状态压缩策略

# 01背包问题的空间优化
def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for j in range(capacity, weights[i]-1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

3.2 常见优化方法对比

优化技术	适用场景	优化效果
滚动数组	状态仅依赖前一行/列	空间降维
斜率优化	决策单调性问题	时间O(n²)→O(n)
四边形不等式	区间类问题	剪枝优化
状态机模型	复杂状态转移	简化逻辑
预处理前缀和	频繁区间查询	加速计算
记忆化搜索	树形结构问题	简化实现

---

四: 字符串匹配问题

# 正则表达式匹配（含'.'和'*'）
def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False]*(n+1) for _ in range(m+1)]
    dp[0][0] = True
    
    for j in range(1, 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] == '*':
                dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
            else:
                dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
    
    return dp[m][n]

---

五、动态规划的进阶训练

5.1 树形DP实战

# 二叉树最大路径和
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = -inf
        
        def dfs(node):
            if not node: return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            self.max_sum = max(self.max_sum, left + right + node.val)
            return max(left, right) + node.val
        
        dfs(root)
        return self.max_sum

5.2 状态压缩DP

# 旅行商问题（TSP）
def tsp(dist):
    n = len(dist)
    memo = [[inf]*(1<<n) for _ in range(n)]
    memo[0][1] = 0  # 从城市0出发
    
    for mask in range(1, 1<<n):
        for u in range(n):
            if not (mask & (1<<u)): continue
            for v in range(n):
                if mask & (1<<v)): continue
                memo[v][mask|(1<<v)] = min(
                    memo[v][mask|(1<<v)],
                    memo[u][mask] + dist[u][v]
                )
    
    return min(memo[u][(1<<n)-1] + dist[u][0] for u in range(n))