跳到主要内容

动态规划基本原理

动态规划（Dynamic Programming，简称 DP）是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题，并存储这些子问题的结果，避免重复计算，从而提高效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。

什么是动态规划？​

动态规划的核心思想是分而治之，但与分治法不同，动态规划会保存子问题的解，避免重复计算。它通常用于优化问题，例如最短路径、最长公共子序列、背包问题等。

备注

重叠子问题：问题可以被分解为多个相同的子问题，这些子问题会被多次计算。 最优子结构：问题的最优解可以通过子问题的最优解构造出来。

动态规划的基本步骤​

  1. 定义状态：明确问题的状态，通常用一个或多个变量表示。
  2. 确定状态转移方程：找到状态之间的关系，即如何从子问题的解推导出当前问题的解。
  3. 初始化：确定初始状态的值。
  4. 计算顺序：按照一定的顺序计算状态，通常是自底向上或自顶向下。
  5. 返回结果：根据计算出的状态值，返回最终结果。

示例：斐波那契数列​

斐波那契数列是一个经典的动态规划问题。定义如下：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) （n ≥ 2）

递归解法（非动态规划）​

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

这种解法的时间复杂度为 O(2^n)，因为存在大量重复计算。

动态规划解法​

通过存储子问题的结果，可以显著提高效率。

python
def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

这种解法的时间复杂度为 O(n)，空间复杂度为 O(n)。

输入与输出​

python
print(fibonacci_dp(10))  # 输出：55

实际案例：0-1 背包问题​

0-1 背包问题是动态规划的经典应用之一。问题描述如下：

给定一组物品，每个物品有一个重量和一个价值。在不超过背包最大承重的情况下，如何选择物品使得总价值最大？

状态定义​

  • dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。

状态转移方程​

  • 如果不选择第 i 个物品：dp[i][j] = dp[i-1][j]
  • 如果选择第 i 个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]

其中，w[i] 是第 i 个物品的重量，v[i] 是第 i 个物品的价值。

代码实现​

python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[n][capacity]

输入与输出​

python
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # 输出：7

总结​

动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。通过定义状态、确定状态转移方程、初始化和计算顺序，可以高效地解决许多复杂问题。

提示

练习：尝试用动态规划解决最长公共子序列（LCS）问题。

附加资源​