动态规划入门：最优子结构与重叠子问题详解

动态规划入门：最优子结构与重叠子问题详解

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的有力工具。它通过将问题分解为更小的子问题，并记忆这些子问题的结果，从而避免重复计算，提高效率。动态规划的两个核心概念是最优子结构和重叠子问题。

一、最优子结构

最优子结构指的是一个问题的最优解可以由其子问题的最优解构造而成。换句话说，如果我们可以通过解决子问题来解决原问题，那么这个问题就具有最优子结构性质。

1.1 最优子结构的例子

例子1：最短路径问题

例子2：矩阵链乘法

在矩阵链乘法中，我们需要找到一种最有效的方式来计算多个矩阵的乘积。这个问题也具有最优子结构性质，因为计算矩阵链的最优乘积方式可以通过计算它的子链的最优乘积方式来得到。

1.2 如何识别最优子结构

识别一个问题是否具有最优子结构性质，通常需要以下步骤：

1. 分解问题：将原问题分解为子问题，确保子问题独立且易于解决。
2. 验证子问题：检查子问题的解是否可以组合成原问题的解。
3. 组合子问题：确认是否可以通过组合子问题的最优解来获得原问题的最优解。

二、重叠子问题

重叠子问题是指在解决一个问题的过程中，会多次遇到相同的子问题。如果这些子问题重复出现，我们可以使用记忆化技术（Memoization）或表格法（Tabulation）来存储它们的计算结果，从而避免重复计算。

2.1 重叠子问题的例子

例子1：斐波那契数列

斐波那契数列是重叠子问题的经典例子。在计算斐波那契数列的过程中，我们会多次计算相同的子问题。例如，计算F(5)时，我们需要计算F(4)和F(3)，而计算F(4)又需要计算F(3)和F(2)。这样会导致大量的重复计算。

例子2：最长公共子序列

在计算两个字符串的最长公共子序列（LCS）时，我们也会遇到重叠子问题。例如，在比较字符串“ABCBDAB”和“BDCABA”时，我们需要比较子序列“BCBDAB”和“DCABA”以及“ABCBDAB”和“DCABA”，这些子序列的比较会重复多次。

在这张图中，我们看到计算最长公共子序列时的一些重叠子问题。每一个节点代表一个子问题，例如”LCS1”表示求解字符串”ABCBDAB”和”BDCABA”的最长公共子序列，而”LCS2”表示求解”BCBDAB”和”DCABA”的最长公共子序列。因为这些子问题在多个计算路径中会重复出现，所以它们就是重叠子问题的例子。

2.2 解决重叠子问题的方法

1. 记忆化技术（Memoization）

记忆化技术是一种自顶向下的解决方法，通过递归计算子问题，并将计算结果存储在一个表中。每当需要计算一个子问题时，先检查表中是否已有结果，如果有则直接使用，否则计算并存储结果。

function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
console.log(fibonacci(10)); // 输出55

2. 表格法（Tabulation）

表格法是一种自底向上的解决方法，通过迭代计算所有子问题的解，并将这些解存储在一个表中。这样，每当需要计算一个子问题时，可以直接查表得到结果。

function fibonacci(n) {
  if (n <= 1) return n;
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}
console.log(fibonacci(10)); // 输出55

2.3 如何识别重叠子问题

识别一个问题是否具有重叠子问题性质，通常需要以下步骤：

1. 分解问题：将原问题分解为子问题。
2. 检测重复：检查是否存在重复计算的子问题。
3. 优化策略：选择合适的优化策略，如记忆化技术或表格法，来存储和复用子问题的计算结果。

通过理解最优子结构和重叠子问题的概念，我们可以更好地应用动态规划来解决实际问题。这两个核心概念帮助我们识别问题的结构特性，并选择合适的优化策略，从而提高算法的效率。

三、经典动态规划问题及其 JavaScript 实现

3.1 斐波那契数列

斐波那契数列是动态规划的经典问题之一。其递推公式为：

F(n) = F(n-1) + F(n-2)

基准条件为：

F(0) = 0, F(1) = 1

记忆化技术实现斐波那契数列

/**
 * 计算斐波那契数列的第 n 项
 * 使用记忆化技术来避免重复计算
 * @param {number} n - 斐波那契数列的第 n 项
 * @param {object} memo - 用于存储已经计算过的斐波那契数值
 * @returns {number} - 第 n 项的斐波那契数值
 */
function fibonacci(n, memo = {}) {
  // 基准条件：如果 n 小于等于 1，则返回 n
  if (n <= 1) return n;
  // 如果 memo 对象中已经存在第 n 项的结果，则直接返回
  if (memo[n]) return memo[n];
  // 否则，计算第 n 项的结果，并将其存储在 memo 对象中
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  // 返回第 n 项的结果
  return memo[n];
}
// 示例：计算斐波那契数列的第 10 项
console.log(fibonacci(10)); // 输出55

在上述代码中，我们使用了一个 memo 对象来存储已经计算过的斐波那契数值，这样在遇到重复子问题时可以直接返回结果，避免了重复计算。

3.2 背包问题

背包问题描述了这样一个场景：给定一组物品，每个物品有一定的重量和价值，在总重量不超过容量的情况下，如何选择物品使得总价值最大。

动态规划实现背包问题

/**
 * 解决背包问题，找到在不超过最大容量的情况下，能够获得的最大价值
 * @param {number[]} weights - 物品的重量数组
 * @param {number[]} values - 物品的价值数组
 * @param {number} capacity - 背包的最大容量
 * @returns {number} - 背包能够容纳的最大价值
 */
function knapsack(weights, values, capacity) {
  const n = weights.length;
  // 创建一个二维数组 dp，用于存储动态规划的结果
  // dp[i][w] 表示前 i 件物品在容量为 w 时能够获得的最大价值
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
  // 遍历每一件物品
  for (let i = 1; i <= n; i++) {
    // 遍历每一种可能的容量
    for (let w = 1; w <= capacity; w++) {
      // 如果当前物品的重量小于等于当前容量
      if (weights[i - 1] <= w) {
        // 选择当前物品，或者不选择当前物品，取最大值
        dp[i][w] = Math.max(
          dp[i - 1][w], // 不选择当前物品
          dp[i - 1][w - weights[i - 1]] + values[i - 1] // 选择当前物品
        );
      } else {
        // 如果当前物品的重量大于当前容量，则不能选择当前物品
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  // 返回最大价值
  return dp[n][capacity];
}
// 示例：背包问题
const weights = [1, 3, 4, 5]; // 物品的重量数组
const values = [1, 4, 5, 7]; // 物品的价值数组
const capacity = 7; // 背包的最大容量
console.log(knapsack(weights, values, capacity)); // 输出9

在上述代码中，我们使用一个二维数组 dp 来存储动态规划的结果。dp[i][w] 表示前 i 件物品在容量为 w 时能够获得的最大价值。通过遍历每一件物品和每一种可能的容量，我们可以找到在不超过最大容量的情况下，能够获得的最大价值。

四、总结

动态规划通过分解问题、存储子问题结果，解决了许多经典的计算问题。在实际应用中，识别问题是否具有最优子结构和重叠子问题的性质，并正确使用记忆化技术或表格法，可以显著提高算法的效率。

通过以上两个示例，相信大家对动态规划的基本思想和应用有了更深入的理解。在实际开发中，遇到复杂问题时，不妨考虑一下是否可以通过动态规划来解决。