动态规划算法 (Dynamic Programming)

1. 动态规划核心概览

动态规划（DP）并不是某种具体的代码模板，而是一种解决复杂问题的思维方式。它的核心在于将一个复杂的大问题分解为相互重叠的子问题，并通过保存已解决的子问题答案（状态记录），避免重复计算，从而将指数级的时间复杂度降为多项式级。

通俗理解： 那些不能杀死你的（子问题），会让你（的状态转移方程）更强大。记住你走过的路，不要在同一个坑里跌倒两次。

1.1 适用动态规划的两个必要条件

如果一个问题想用动态规划解决，它必须同时满足以下两个特征：

核心特征	详细说明	验证方法
1. 最优子结构	大问题的最优解，可以由其各个子问题的最优解推导出来。	如果你能在不考虑之前选择的情况下，仅仅根据最后一步推导出当前状态，就满足。
2. 重叠子问题	在拆解问题的过程中，相同的子问题会被反复计算多次。	画出递归树，如果发现有相同的节点（如斐波那契数列中的 fib(3) 被计算多次），就满足。

1.2 动态规划解题四步法 (核心秘籍)

无论题目多复杂，都可以按照这四个步骤去拆解：

1. 定义状态（State）： 定义一个数组（一维 dp[i] 或二维 dp[i][j]），并明确这个数组里的每一个元素代表什么业务含义。
2. 推导状态转移方程（Transition Equation）： 找出 dp[i] 是如何通过它前面的状态（如 dp[i-1]、dp[i-2]）计算出来的。这是最难也是最核心的一步。
3. 初始化（Initialization）： 确定 dp 数组的初始值（如 dp[0]、dp[1]），为状态转移提供起点。
4. 确定遍历顺序（Traversal Order）： 明确是应该从前向后遍历，还是从后向前，或是二维数组的特殊遍历方式。

2. 经典 DP 场景与 JavaScript 实现

2.1 爬楼梯问题 (Climbing Stairs)

题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• 1. 定义状态： dp[i] 表示爬到第 i 阶楼梯的方法总数。
• 2. 状态转移方程： 到达第 i 阶，要么是从 i-1 阶跨 1 步上来，要么是从 i-2 阶跨 2 步上来。所以 dp[i] = dp[i-1] + dp[i-2]。
• 3. 初始化： dp[1] = 1（爬1阶只有1种方法），dp[2] = 2（爬2阶有2种方法：1+1或2）。
• 4. 遍历顺序： 从前向后（i 从 3 开始）。

代码实现 (基础版 O(n) 空间)

/**
 * 爬楼梯 - 基础 DP
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
    if (n <= 2) return n;

    let dp = new Array(n + 1).fill(0); // 创建 dp 数组，长度 n+1 为了让索引与楼梯数对齐
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移
    }

    return dp[n];
}

代码实现 (空间压缩版 O(1) 空间)

由于 dp[i] 仅仅依赖于前面的两个状态，我们其实不需要维护一个长数组，只需要两个变量滚动记录即可。

/**
 * 爬楼梯 - 状态压缩 (推荐)
 */
function climbStairsOptimized(n) {
    if (n <= 2) return n;
    
    let prev2 = 1; // 相当于 dp[i-2]
    let prev1 = 2; // 相当于 dp[i-1]
    let current = 0; // 相当于 dp[i]

    for (let i = 3; i <= n; i++) {
        current = prev1 + prev2;
        // 滚动更新变量，为下一次循环做准备
        prev2 = prev1;
        prev1 = current;
    }
    
    return current;
}

2.2 最大子数组和 (Maximum Subarray)

题目描述： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子数组是 [4, -1, 2, 1]，和为 6。

• 1. 定义状态： dp[i] 表示以 nums[i] 结尾 的连续子数组的最大和。（注意：必须是以它结尾）
• 2. 状态转移方程： 对于 nums[i]，它有两个选择：要么加入前面的连续序列（dp[i-1] + nums[i]），要么自立门户从自己重新开始（nums[i]）。取两者的最大值：dp[i] = Math.max(dp[i-1] + nums[i], nums[i])。
• 3. 初始化： dp[0] = nums[0]。
• 4. 遍历顺序： 从前向后。

JavaScript 代码实现

/**
 * 最大子数组和
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
    if (nums.length === 0) return 0;

    let dp = new Array(nums.length);
    dp[0] = nums[0];
    let maxSum = dp[0]; // 记录全局最大值

    for (let i = 1; i < nums.length; i++) {
        // 如果前面的和大于 0，就加上；否则直接另起炉灶取自己
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        
        // 随时更新全局最大值
        maxSum = Math.max(maxSum, dp[i]);
    }

    return maxSum;
}

// 同样可以进行状态压缩，将空间复杂度降为 O(1)：
function maxSubArrayOptimized(nums) {
    let currentMax = nums[0];
    let globalMax = nums[0];
    for (let i = 1; i < nums.length; i++) {
        currentMax = Math.max(nums[i], currentMax + nums[i]);
        globalMax = Math.max(globalMax, currentMax);
    }
    return globalMax;
}

2.3 零钱兑换 (Coin Change) - 二维 DP 经典题

题目描述： 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。

• 1. 定义状态： dp[i] 表示凑成金额 i 所需的最少硬币数。
• 2. 状态转移方程： 凑成金额 i 的最少硬币数，等于【凑成金额 i - coin 的最少硬币数 + 1】（遍历所有硬币面值找最小值）。即：dp[i] = Math.min(dp[i], dp[i - coin] + 1)。
• 3. 初始化： dp[0] = 0（凑0元不需要硬币）。其他索引初始化为一个不可能的极大值（如 Infinity 或 amount + 1），以便在求 Math.min 时被覆盖。
• 4. 遍历顺序： 外层遍历金额（从 1 到 amount），内层遍历硬币面值。

JavaScript 代码实现

/**
 * 零钱兑换 (完全背包问题变种)
 * @param {number[]} coins 硬币面值数组
 * @param {number} amount 目标金额
 * @return {number}
 */
function coinChange(coins, amount) {
    // 初始化 dp 数组，默认值为 amount + 1 (相当于无穷大)
    let dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0; // 凑 0 元需要 0 个硬币

    // 外层遍历所有金额状态
    for (let i = 1; i <= amount; i++) {
        // 内层遍历每种硬币
        for (let coin of coins) {
            // 如果当前硬币面值小于等于要凑的金额
            if (i >= coin) {
                // 状态转移：取当前记录的最少硬币数，和 (减去该硬币面值后的最少硬币数 + 1) 的较小值
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 还是初始值，说明凑不出来，返回 -1
    return dp[amount] === amount + 1 ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // 输出: 3 (11 = 5 + 5 + 1)

3. 常见问题深度剖析 (FAQ)

常见疑惑	深度解析	应对策略
1. 怎么区分一道题该用贪心算法还是动态规划？	贪心算法只顾眼前利益，每次选择当前看起来最优的，一旦选定就不后悔（不记录状态）。而动态规划眼光长远，它会考虑之前所有的状态，综合评估得出全局最优解。如果题目说“每种选择会影响未来的结果”，或者发现贪心找出的解不是最优的（如零钱兑换题，面值为 [1, 3, 4]，凑 6 元，贪心会选 4+1+1，而 DP 会选最优的 3+3），就必须用 DP。	先尝试用贪心思路走一遍，如果能找到反例证明贪心失效，立刻转向考虑 DP。
2. 总是找不出“状态转移方程”怎么办？	状态转移方程是 DP 的灵魂，找不出来是因为没有看透“前后状态的联系”。	回退法： 假设你已经到达了最终状态 n，问自己：“我是怎么来到这里的？” 通常只有几种明确的方式可以来到这一步。把这几种方式转化为数学公式即可。
3. DP 与 记忆化递归（自顶向下）有什么区别？	本质是一样的，都在避免重复计算。记忆化递归是“从结果往前推，推到哪算到哪”，遇到算过的直接用。**DP（自底向上）**是“从最初始的 dp[0] 稳扎稳打一步步算到最终结果”。	在 JavaScript 中，由于递归有爆栈（Stack Overflow）的风险，处理大规模数据时，强烈推荐将记忆化递归重构为迭代形式的 DP。
4. 什么是状态压缩？必须写吗？	如果你发现当前状态 dp[i] 仅仅依赖于 dp[i-1] 或 dp[i-2]，那么前面计算过的一大串数据其实都没用了，就可以不用数组，只用几个变量来存储前置状态，将空间复杂度从 O(n) 降为 O(1)，这就是状态压缩。	在面试中，先写出使用数组的 O(n) 版本保证正确性，然后作为加分项向面试官展示你可以优化为 O(1)。