当前位置：首页 > JavaScript

js实现动态规划

2026-02-02 22:32:44JavaScript

动态规划的基本概念

动态规划是一种将复杂问题分解为更小子问题的方法，通过存储子问题的解来避免重复计算。适用于具有重叠子问题和最优子结构性质的问题。

斐波那契数列示例

斐波那契数列是动态规划的经典案例。递归实现效率低，而动态规划可以显著提升性能。

function fibonacci(n) {
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

背包问题解决方案

背包问题要求在不超出背包容量的情况下选择物品以获得最大价值。

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= capacity; j++) {
      if (weights[i - 1] <= j) {
        dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][capacity];
}

最长公共子序列

查找两个序列共有的最长子序列长度。

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

优化空间复杂度

某些情况下可以优化空间使用，例如斐波那契数列只需保存前两个状态。

js实现动态规划

function fibonacciOptimized(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}