动态规划算法在 JavaScript 中的应用

在编程和算法设计中，动态规划（Dynamic Programming, DP）是一种强大的技术，用于解决复杂的优化问题。本文将详细介绍动态规划的基本概念、核心思想，并通过一个具体的例子来展示如何在 JavaScript 中实现动态规划。同时，我们还将对比动态规划与其他常见算法（如分治法）的不同之处。

什么是动态规划？

动态规划是一种通过把原问题分解为相互重叠的子问题来求解复杂问题的方法。它通常用于优化问题，通过存储子问题的解来避免重复计算，从而提高算法的效率。

动态规划的核心思想

1. 重叠子问题：子问题之间不是独立的，而是相互重叠的。这意味着某些子问题会被多次计算。
2. 最优子结构：问题的最优解可以由其子问题的最优解组合而成。
3. 状态转移：通过一个状态转移方程来描述子问题之间的关系。
4. 存储子问题的解：使用一个表（通常是数组或哈希表）来存储子问题的解，以便后续直接使用。

动态规划的应用场景

动态规划广泛应用于各种优化问题，例如背包问题、最长公共子序列、斐波那契数列等。本文将以一个经典的房屋盗窃问题（House Robber）为例，展示如何在 JavaScript 中实现动态规划。

房屋盗窃问题

假设你是一个专业的强盗，计划抢劫沿街的房屋。每个房屋都存放有一定数量的现金，但相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被强盗闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

动态规划解决方案

1. 定义状态：
   • dp[i] 表示到第 i 个房屋为止，可以抢到的最大金额。
2. 初始化：
   • dp[0] = nums[0]：只有一个房屋时，最大金额就是该房屋的金额。
   • dp[1] = max(nums[0], nums[1])：有两个房屋时，最大金额是这两个房屋中金额较大的那个。
3. 状态转移方程：
   • 对于第i 个房屋，有两种选择：
     • 不抢劫第 i 个房屋，最大金额是 dp[i - 1]。
     • 抢劫第 i 个房屋，最大金额是 dp[i - 2] + nums[i]。
   • 因此，dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。
4. 返回结果：
   • 最终结果是 dp[len - 1]，即最后一个房屋为止的最大金额。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var max = function (a, b) {
    return a > b ? a : b;
}

var rob = function (nums) {
    // dp[i] 代表到 i 下标元素为止，可以取到的最大值
    let len = nums.length;
    let dp = new Array(len);

    // 边界条件处理
    if (len === 0) return 0;
    if (len === 1) return nums[0];

    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (let i = 2; i < len; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }

    return dp[len - 1];
};

// 测试用例
console.log(rob([1, 2, 3, 1])); // 输出: 4
console.log(rob([2, 7, 9, 3, 1])); // 输出: 12
console.log(rob([0])); // 输出: 0
console.log(rob([1])); // 输出: 1
console.log(rob([])); // 输出: 0

逻辑验证

1. 基础案例：
   • 当 nums 为空时，返回 0。
   • 当 nums 只有一个元素时，返回该元素的值。
   • 当 nums 有两个元素时，返回这两个元素中较大的那个。
2. 状态转移方程的正确性：
   • dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])：
     • dp[i - 2] + nums[i] 表示抢劫第 i 个房屋，此时不能抢劫第 i - 1 个房屋，最大金额是 dp[i - 2] 加上 nums[i]。
     • dp[i - 1] 表示不抢劫第 i 个房屋，最大金额是 dp[i - 1]。
     • 选择这两者中的较大值作为 dp[i] 的值。
3. 递归关系的验证：
   • 通过递归关系，我们可以逐步计算出每个 dp[i] 的值，最终得到 dp[len - 1]，即最大金额。

示例验证

假设 nums = [2, 7, 9, 3, 1]，我们手动计算一下 dp 数组的值：

• dp[0] = nums[0] = 2
• dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7
• dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 9, 7) = max(11, 7) = 11
• dp[3] = max(dp[1] + nums[3], dp[2]) = max(7 + 3, 11) = max(10, 11) = 11
• dp[4] = max(dp[2] + nums[4], dp[3]) = max(11 + 1, 11) = max(12, 11) = 12

最终结果是 dp[4] = 12，这是正确的最大金额。

动态规划 vs 分治法

分治法

分治法（Divide and Conquer）是一种将问题分解为若干个规模较小的相同子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解的方法。

主要特点

1. 独立子问题：子问题之间是独立的，互不影响。
2. 递归：通常使用递归来解决子问题。
3. 合并：将子问题的解合并成原问题的解。

应用场景

• 经典问题：快速排序、归并排序、二分查找、大整数乘法等。
• 分解问题：适用于可以自然分解为独立子问题的情况。

动态规划 vs 分治法

1. 子问题的性质：
   • 动态规划：子问题之间重叠，需要存储子问题的解以避免重复计算。
   • 分治法：子问题之间独立，不需要存储子问题的解。
2. 解题过程：
   • 动态规划：通常从底向上（自底向上）解决问题，逐步构建最终解。
   • 分治法：通常从顶向下（自顶向下）解决问题，递归地分解问题，再合并子问题的解。
3. 存储需求：
   • 动态规划：需要额外的空间来存储子问题的解。
   • 分治法：通常不需要额外的空间来存储子问题的解，但递归调用栈会占用一定的空间。
4. 适用问题：
   • 动态规划：适用于具有最优子结构和重叠子问题的问题，通常用于优化问题。
   • 分治法：适用于可以自然分解为独立子问题的问题，通常用于排序、查找等问题。

示例对比

动态规划示例：斐波那契数列

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

分治法示例：快速排序

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left - 1;
    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

总结

通过动态规划，可以将问题分解为子问题，并通过状态转移方程逐步求解，最终得到了全局最优解。这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，可以通过进一步优化将空间复杂度降低到 O(1)。