动态规划

动态规划（Dynamic Programming，简称DP）是一种用于解决复杂问题的算法设计技术，通过将问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算，从而提高效率。动态规划常用于优化问题，如最短路径、背包问题、序列对齐等。

基本概念

动态规划的核心思想包括以下两点：

1. 重叠子问题：问题可以被分解为多个相似的子问题，这些子问题会被重复计算。
2. 最优子结构：问题的最优解可以通过子问题的最优解组合得到。

动态规划通常有两种实现方式：

• 自顶向下（记忆化搜索）：从原问题出发，递归地解决子问题，并使用表格（如数组或哈希表）存储已计算的子问题结果。
• 自底向上（迭代法）：从最小的子问题开始，逐步构建更大问题的解，通常使用表格填充法。

动态规划步骤

解决动态规划问题的一般步骤如下：

1. 定义状态：明确问题的子问题，并用变量表示状态。
2. 确定状态转移方程：描述如何从一个或多个子问题的解得到当前问题的解。
3. 初始化边界条件：确定最小子问题的解。
4. 计算顺序：确定填表的顺序（自底向上或自顶向下）。
5. 返回最终解：通常存储在表格的某个特定位置。

经典示例：斐波那契数列

斐波那契数列是动态规划的经典入门问题，定义为： $F(n)=\{\begin{array}{ll}0& \text{if }n=0,\\ 1& \text{if }n=1,\\ F(n-1)+F(n-2)& \text{if }n>1.\end{array}$

递归解法（低效）

直接递归会导致大量重复计算，时间复杂度为$O(2^n)$：

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

动态规划解法（高效）

使用动态规划存储中间结果，时间复杂度降为$O(n)$：

  
def fib(n):  
    if n <= 1:  
        return 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]

输入输出示例

输入：n = 5 输出：5（因为斐波那契数列为0, 1, 1, 2, 3, 5）

实际案例：背包问题

0-1背包问题是动态规划的典型应用：给定一组物品，每个物品有重量$w_i$和价值$v_i$，在背包容量限制$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}$

代码实现

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

输入输出示例

输入：W = 5, wt = [2, 3, 4], val = [3, 4, 5], n = 3 输出：7（选择物品1和物品2，总重量5，价值7）

动态规划优化

动态规划的空间复杂度通常可以优化。例如，斐波那契数列只需两个变量存储前两个状态：

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

背包问题可以优化为一维数组：

  
def knapsack(W, wt, val, n):  
    dp = [0] * (W + 1)  
    for i in range(n):  
        for j in range(W, wt[i] - 1, -1):  # 逆向遍历避免重复计算  
            dp[j] = max(dp[j], dp[j - wt[i]] + val[i])  
    return dp[W]

应用场景

动态规划广泛用于以下领域：

• 序列问题（最长公共子序列、编辑距离）
• 图问题（最短路径、Floyd-Warshall算法）
• 资源分配（背包问题、股票买卖问题）
• 字符串处理（正则表达式匹配）

总结

动态规划通过存储子问题的解避免重复计算，显著提高算法效率。掌握动态规划的关键在于：

1. 识别重叠子问题和最优子结构。
2. 设计正确的状态表示和转移方程。
3. 选择适当的实现方式（自顶向下或自底向上）。

通过练习经典问题（如斐波那契数列、背包问题）和实际案例，可以逐步掌握动态规划的核心思想与应用技巧。