动态规划基本原理

引言

动态规划（Dynamic Programming，简称DP）是一种用于解决复杂问题的算法设计范式，通过将问题分解为相互重叠的子问题并存储子问题的解（称为记忆化）来避免重复计算。它特别适用于具有最优子结构（即全局最优解包含局部最优解）和重叠子问题性质的问题。

动态规划的核心思想可以概括为：

• 分治：将原问题分解为相似的子问题
• 记忆化：存储子问题的解以避免重复计算
• 递推：利用已解决的子问题构建更大问题的解

基本概念

最优子结构

一个问题具有最优子结构性质，当且仅当问题的最优解包含其子问题的最优解。数学表达为：

$\text{OPT}(i,j)=f(\text{OPT}(i,k),\text{OPT}(k+1,j))$

其中$f$是某种组合函数。

重叠子问题

在递归求解过程中，相同的子问题会被多次计算。例如斐波那契数列的递归实现：

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

计算fib(5)时，fib(2)会被计算3次，这就是典型的重叠子问题。

状态与状态转移方程

动态规划的关键是定义：

• 状态：表示问题的子问题
• 状态转移方程：描述状态之间的关系

例如在斐波那契数列中：

• 状态：$dp[i]$表示第i个斐波那契数
• 状态转移：$dp[i]=dp[i-1]+dp[i-2]$

实现方法

自顶向下（记忆化递归）

在递归基础上添加缓存：

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

自底向上（迭代法）

从基础情况开始逐步构建解：

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

经典问题示例

0-1背包问题

问题描述：给定物品的重量$w$和价值$v$，以及背包容量$W$，求最大价值组合。

状态定义：

• $dp[i][j]$：考虑前i个物品，背包容量为j时的最大价值

状态转移方程： $dp[i][j]=\{\begin{array}{ll}dp[i-1][j],& \text{if }w[i]>j\\ \max (dp[i-1][j],dp[i-1][j-w[i]]+v[i]),& \text{otherwise}\end{array}$

Python实现：

def knapsack(W, wt, val, n):
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1])
    return dp[n][W]

最长公共子序列（LCS）

问题描述：给定两个字符串，找出它们的最长公共子序列长度。

状态定义：

• $dp[i][j]$：X[0..i-1]和Y[0..j-1]的LCS长度

状态转移方程： $dp[i][j]=\{\begin{array}{ll}0,& \text{if }i=0\text{ or }j=0\\ dp[i-1][j-1]+1,& \text{if }X[i-1]=Y[j-1]\\ \max (dp[i-1][j],dp[i][j-1]),& \text{otherwise}\end{array}$

Python实现：

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[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]

动态规划优化技术

空间优化

当状态转移只依赖有限的前置状态时，可以压缩DP表。例如斐波那契数列的空间优化：

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

状态压缩

使用位运算等技巧减少状态表示空间，常见于状压DP问题。

应用场景

动态规划广泛应用于：

• 路径规划（如Floyd-Warshall算法）
• 资源分配问题
• 生物信息学（如序列比对）
• 金融工程（如期权定价）
• 自然语言处理（如词对齐）

复杂度分析

动态规划的时间复杂度通常为： $O(\text{状态数量}\times \text{每个状态的转移成本})$

空间复杂度取决于DP表的存储方式，经过优化后通常可以降低一个维度。

常见误区

1. 混淆贪心算法：贪心算法每次做局部最优选择，不能保证全局最优 2. 错误的状态定义：状态应包含足够信息以推导后续状态 3. 忽略边界条件：DP表的初始状态需要仔细处理 4. 过度优化：在优化空间前应先保证正确性

练习建议

1. 从简单问题开始（斐波那契、爬楼梯） 2. 理解经典问题的状态转移方程 3. 尝试空间优化版本 4. 比较递归与迭代实现的差异

graph TD A[原问题] --> B[是否具有最优子结构?] B -->|是| C[定义状态表示] B -->|否| D[考虑其他算法] C --> E[建立状态转移方程] E --> F[确定初始条件] F --> G[选择实现方法: 自顶向下/自底向上] G --> H[考虑空间优化]

通过系统学习和大量练习，动态规划将成为解决复杂问题的有力工具。记住其核心：聪明的递归加记忆化存储。