当前位置：首页 > JavaScript

js实现动态规划

2026-03-15 22:58:21JavaScript

动态规划基础概念

动态规划（Dynamic Programming, DP）是一种通过将问题分解为子问题并存储子问题解来优化递归计算的算法思想。适用于具有重叠子问题和最优子结构性质的问题，如背包问题、最长公共子序列等。

动态规划实现步骤

问题分析 明确问题的状态定义、状态转移方程和边界条件。例如，斐波那契数列中状态定义为 dp[i] 表示第 i 项的值，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。

初始化DP表 根据问题规模创建数组或矩阵存储子问题解。通常需要初始化基础情况（如 dp[0] 和 dp[1]）。

const dp = new Array(n + 1).fill(0);
dp[0] = 0;
dp[1] = 1;

状态转移 通过循环填充DP表，根据状态转移方程计算后续状态。

for (let i = 2; i <= n; i++) {
  dp[i] = dp[i - 1] + dp[i - 2];
}

返回结果 最终解通常存储在DP表的特定位置（如 dp[n]）。

return dp[n];

经典问题示例：斐波那契数列

function fibonacci(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

优化空间复杂度

若当前状态仅依赖有限的前置状态，可压缩DP表至常数空间。例如斐波那契数列只需保存前两项：

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

复杂案例：0-1背包问题

给定物品重量 weights 和价值 values，背包容量 capacity，求最大价值。

js实现动态规划

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 w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          values[i - 1] + dp[i - 1][w - weights[i - 1]]
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][capacity];
}