算法——结合实际例子理解动态规划

一、动态规划（Dynamic Programming, DP）核心思想

动态规划是一种通过将复杂问题分解为重叠子问题，并利用子问题的解构建原问题解的算法思想。其核心在于 “存储中间结果避免重复计算”，适用于具有 最优子结构（问题的最优解包含子问题的最优解）和 重叠子问题（子问题重复出现）的场景。

二、常用实际应用例子

1. 斐波那契数列（经典重叠子问题）

问题：计算斐波那契数 ( F(n) = F(n-1) + F(n-2) )，( F(0)=0, F(1)=1 )。

• 暴力递归：时间复杂度 ( O(2^n) )，大量重复计算（如 ( F(3) ) 被计算多次）。
• 动态规划：
  • 自底向上：用数组存储 ( F(0) ) 到 ( F(n) )，逐个计算，时间复杂度 ( O(n) )，空间复杂度 ( O(n) )。
  • 空间优化：只需存储前两个数，空间复杂度降为 ( O(1) )。
    状态转移方程：( dp[i] = dp[i-1] + dp[i-2] )。
    代码：

2. 背包问题（最优子结构）

（1）0-1背包问题

问题：有 ( n ) 个物品，重量 ( w_i )，价值 ( v_i )，背包容量 ( W )，每个物品只能选或不选，求最大价值。

• 状态定义：( dp[i][j] ) 表示前 ( i ) 个物品，容量 ( j ) 时的最大价值。
• 状态转移：
  • 不选第 ( i ) 个物品：( dp[i][j] = dp[i-1][j] )
  • 选第 ( i ) 个物品（若 ( j geq w_i )）：( dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) )
• 时间复杂度：( O(nW) )，空间复杂度 ( O(nW) )（可优化为 ( O(W) )，滚动数组）。

（2）完全背包问题

区别：物品可无限选，状态转移时允许重复选第 ( i ) 个物品，即 ( dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i) )（内层循环正序遍历）。

3. 最短路径（多阶段决策）

** Floyd-Warshall算法**：

• 问题：求所有点对之间的最短路径。
• 动态规划：
  • 状态 ( dp[k][i][j] ) 表示经过前 ( k ) 个中间节点时，( i ) 到 ( j ) 的最短路径。
  • 状态转移：( dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]) )。
• 优势：可处理负权边，时间复杂度 ( O(n^3) )。

三、动态规划 vs 其他算法

举例对比：

• 背包问题：贪心无法解决0-1背包（需全局权衡），动态规划可求最优解。
• 最短路径：Dijkstra算法（贪心）适用于非负权图，Floyd-Warshall（动态规划）适用于任意权图。

四、动态规划程序优化技巧

1. 空间优化（滚动数组）

• 场景：当状态转移仅依赖于前一层或前几层数据时，可用一维数组替代二维数组。
  • 例：0-1背包的二维状态 ( dp[i][j] ) 可优化为一维 ( dp[j] )，内层循环逆序遍历（避免重复使用当前物品）。

  # 优化前（二维）
  dp = [[0]*(W+1) for _ in range(n+1)]
  for i in range(1, n+1):
      for j in range(1, W+1):
          if j >= w[i]:
              dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
          else:
              dp[i][j] = dp[i-1][j]
  
  # 优化后（一维）
  dp = [0]*(W+1)
  for i in range(n):
      for j in range(W, w[i]-1, -1):  # 逆序遍历避免重复选同一物品
          dp[j] = max(dp[j], dp[j-w[i]] + v[i])
  

2. 状态转移方程简化

• 合并条件：避免冗余判断，如将 ( j < w_i ) 的情况合并到状态转移中（默认不选）。
• 利用数学性质：如完全背包内层循环正序遍历，可重复选物品。

3. 记忆化搜索（自顶向下）

• 用递归+缓存（如Python的lru_cache）存储子问题解，适合子问题结构复杂但计算顺序不固定的场景（如“最长公共子序列”）。

  from functools import lru_cache
  
  @lru_cache(maxsize=None)
  def lcs(i, j):
      if i == 0 or j == 0:
          return 0
      if s1[i-1] == s2[j-1]:
          return lcs(i-1, j-1) + 1
      else:
          return max(lcs(i-1, j), lcs(i, j-1))
  

4. 减少状态维度

• 例：矩阵链乘法中，状态 ( dp[i][j] ) 表示计算第 ( i ) 到第 ( j ) 个矩阵的最小乘法次数，无需额外维度。

五、总结

动态规划的核心是 “以空间换时间”，通过存储子问题解避免重复计算，适用于具有最优子结构和重叠子问题的场景。与贪心、分治等算法的区别在于对“子问题依赖关系”的处理：动态规划显式利用重叠子问题，而贪心依赖局部最优，分治处理独立子问题。
优化关键：分析状态转移的依赖关系，通过滚动数组、记忆化等手段减少空间和时间开销，同时确保状态定义准确反映问题的最优子结构。