【JavaScript 算法】动态规划：最优子结构与重叠子问题

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

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

/**
 * 计算斐波那契数列的第 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

/**
 * 解决背包问题，找到在不超过最大容量的情况下，能够获得的最大价值
 * @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