当前位置：首页 > JavaScript

js实现动态规划

2026-04-07 16:21:14JavaScript

动态规划的基本概念

动态规划（Dynamic Programming, DP）是一种通过将问题分解为子问题并存储子问题解来优化递归问题的算法设计方法。适用于具有重叠子问题和最优子结构性质的问题。

动态规划的步骤

问题分析
明确问题的状态转移方程和边界条件。例如，斐波那契数列的状态转移方程为 f(n) = f(n-1) + f(n-2)，边界条件为 f(0) = 0 和 f(1) = 1。

状态定义
使用数组或对象存储子问题的解，避免重复计算。例如，斐波那契数列可以用一个数组 dp 存储中间结果。

递推实现
通过循环从基础状态逐步推导到目标状态。例如，斐波那契数列的递推实现如下：

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];
}

常见动态规划问题示例

爬楼梯问题
问题描述：每次可以爬1或2阶楼梯，求爬到第n阶的方法数。
状态转移方程：dp[n] = dp[n-1] + dp[n-2]。
实现代码：

function climbStairs(n) {
    if (n <= 2) return n;
    let dp = [1, 2];
    for (let i = 3; i <= n; i++) {
        let current = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = current;
    }
    return dp[1];
}

背包问题
问题描述：给定物品重量和价值，在背包容量限制下最大化价值。
状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
实现代码：

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

优化空间复杂度

某些问题可以通过滚动数组或变量压缩空间。例如，斐波那契数列只需两个变量存储前两个状态：

js实现动态规划

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