动态规划

我们来系统且深入地剖析动态规划（Dynamic Programming, DP）。我会遵循第一性原理，从它最核心的思想出发，逐步构建起完整的知识体系，并最终用 JavaScript 代码来实践。

什么是动态规划？从本质说起

想象一下你每天上学，从家到学校有很多条路。第一天你随机走了一条，花了30分钟。第二天，你可能会想：“昨天那条路在某个路口好像堵车了，今天我走到那个路口时，换一条小巷试试看会不会更快？”

这个思考过程，就是动态规划的萌芽。你没有把“从家到学校”看成一个无法分割的整体，而是将一个大问题，拆解成了一系列更小的、相互关联的阶段性决策。你相信，在每个路口做出的“最优选择”（走哪条小路），最终会引导你找到全局的“最优解”（最快的路线）。

更重要的是，如果你发现从 A 路口到 B 路口最快需要5分钟，你会把这个“知识”记住。以后任何需要从 A 前往 B 的路线规划，你都会直接使用这个“5分钟”的结论，而不需要重新再走一遍、再计算一次。

把这个过程抽象出来，我们就得到了动态规划的两个核心特征：

1. 最优子结构 (Optimal Substructure)

   一个大问题的最优解，可以由其子问题的最优解有效地构造出来。就像“从家到学校的最快路线”，必然包含了“从家到某个中间路口的最快路线”。

2. 重叠子问题 (Overlapping Subproblems)

   在解决大问题的过程中，许多相同的子问题会被反复计算。就像计算斐波那契数列 fib(5) 需要计算 fib(4) 和 fib(3)，而计算 fib(4) 又需要计算 fib(3) 和 fib(2)，这里的 fib(3) 就是一个被重复计算的子问题。动态规划的威力，就体现在它能通过“记住”子问题的解来避免这种重复计算。

因此，动态规划的本质是：通过拆分问题、定义问题状态与状态之间的关系，并将小问题的解储存起来，自底向上地推导出大问题的解。 它是一种用空间换时间的思想。

---

解决动态规划问题的“四步法”

当你遇到一个问题，怀疑它可能用动态规划解决时，可以尝试遵循以下四个步骤。这套框架能帮助你理清思路，构建出正确的模型。

第一步：判断问题是否具有动态规划的特征

• 它是否能被拆分成子问题？

• 子问题的最优解能否推导出原问题的最优解？（最优子结构）

• 求解过程中是否存在重复的子问题计算？（重叠子问题）

• 常见题型：求最大/最小值、求可行性、求方案总数等。

第二步：定义状态 (State)

这是最核心也是最困难的一步。你需要定义一个数组（通常是 dp 数组），并明确 dp[i] 或 dp[i][j] 代表什么。这个定义必须是清晰、无歧义的，并且能够覆盖所有子问题。

• 例如，dp[i] 可以表示“爬到第 i 级台阶的总方法数”，或者“凑成金额 i 所需的最少硬币数”。

第三步：推导状态转移方程 (State Transition Equation)

这是算法的核心。你需要找到 dp[i] 和 dp[i-1], dp[i-2], ... 等历史状态之间的数学关系。这个方程描述了如何从一个或多个已知的子问题解，计算出当前问题的解。

• 例如，爬楼梯问题中，想到达第 i 级，要么从 i-1 级爬上来，要么从 i-2 级爬上来，所以 dp[i] = dp[i-1] + dp[i-2]。

第四步：确定初始状态 (Base Cases)

算法总需要一个起点。初始状态是 dp 数组中不需要通过状态转移方程就能直接确定的值。它们是推导的基石。

• 例如，dp[0] = 0 或 dp[1] = 1。

---

实现方式：记忆化搜索 vs. 递推

动态规划有两种经典的实现范式，它们思路不同，但殊途同归。

1. 自顶向下 (Top-Down) 与记忆化搜索 (Memoization)

   • 思路：从大问题出发，使用递归函数求解。如果一个子问题之前没算过，就计算它，并把结果存起来（例如存在一个 Map 或对象里）；如果算过了，就直接从存储中取出结果。

   • 优点：写法更符合直觉，接近人类的递归思考方式。只计算被真正需要的子问题。

   • 缺点：递归有函数调用开销，当递归深度过大时，可能导致栈溢出。

2. 自底向上 (Bottom-Up) 与递推/制表 (Tabulation)

   • 思路：不使用递归。根据我们定义的状态，创建一个 dp 数组（或表格），根据初始状态和状态转移方程，从 dp[0] 开始，按顺序一步步地计算出所有状态的值，直到我们需要的最终解。

   • 优点：没有递归开销，效率通常更高。代码是迭代式的（用循环），没有栈溢出风险。

   • 缺点：可能会计算一些最终答案并不需要的子问题。思考过程有时不如递归直观。

哪个更好？

在面试和算法竞赛中，自底向上的递推法（Tabulation）通常是更受青睐的选择。因为它避免了递归的潜在风险，并且在性能上往往略胜一筹。不过，当你面对一个新问题，用自顶向下的记忆化搜索来理清递归关系，再将其改写为递推形式，也是一个非常有效的策略。

---

代码实战：从简单到复杂

示例 1：斐波那契数列（DP入门经典）

问题：计算斐波那契数列的第 n 项。f(0)=0, f(1)=1, f(n) = f(n-1) + f(n-2)。

1. 朴素递归（反例）

首先看一个没有使用动态规划的递归，它会因为大量重复计算而非常低效。

JavaScript

function fib_naive(n) {
    if (n <= 1) {
        return n;
    }
    // 大量重复计算，例如 fib(5) 会多次计算 fib(3)
    return fib_naive(n - 1) + fib_naive(n - 2);
}
// console.log(fib_naive(45)); // 会花费很长时间

2. 记忆化搜索 (Top-Down)

JavaScript

function fib_memo(n, memo = {}) {
    // 如果已经在缓存中，直接返回
    if (n in memo) {
        return memo[n];
    }
    // Base Case
    if (n <= 1) {
        return n;
    }
    // 计算、存入缓存、然后返回
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

console.log(`记忆化搜索: fib(10) = ${fib_memo(10)}`); // 记忆化搜索: fib(10) = 55

在这里，memo 对象就像我们的大脑记忆，避免了做无用功。

3. 递推 (Bottom-Up)

JavaScript

function fib_tab(n) {
    if (n <= 1) {
        return n;
    }
    // 1. 定义状态: dp[i] 代表斐波那契数列第 i 项的值
    const dp = new Array(n + 1);

    // 2. 确定初始状态
    dp[0] = 0;
    dp[1] = 1;

    // 3. 状态转移方程: dp[i] = dp[i-1] + dp[i-2]
    // 从下往上计算
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}
console.log(`递推法: fib(10) = ${fib_tab(10)}`); // 递推法: fib(10) = 55

空间优化

我们注意到，计算 dp[i] 其实只需要 dp[i-1] 和 dp[i-2] 这两个状态。没必要保存整个数组。

JavaScript

function fib_optimized(n) {
    if (n <= 1) {
        return n;
    }
    let prev2 = 0; // 代表 dp[i-2]
    let prev1 = 1; // 代表 dp[i-1]
    let current;

    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}
console.log(`空间优化: fib(10) = ${fib_optimized(10)}`); // 空间优化: fib(10) = 55

---

示例 2：零钱兑换（更典型、更复杂的DP问题）

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

我们来套用“四步法”：

第一步：判断问题特征

• 求最值（最少个数）。

• 凑成 amount 的最优解，依赖于凑成 amount - coin 的最优解。例如，凑11元的最优解，可能是凑10元最优解+1个1元硬币，或凑9元最优解+1个2元硬币，或凑6元最优解+1个5元硬币中的最小值。这符合最优子结构。

• 在计算过程中，凑齐某个金额（如5元）的方法，会被多次用到。这符合重叠子问题。

• 结论：这是一个典型的动态规划问题。

第二步：定义状态

• 我们创建一个数组 dp，dp[i] 的含义是：凑成金额 i 所需要的最少硬币数量。我们的目标就是求 dp[amount]。

第三步：推导状态转移方程

• 对于任意金额 i，我们要如何得到 dp[i] 呢？

• 我们可以尝试使用每一枚硬币 coin。如果我们决定使用一枚面值为 coin 的硬币，那么问题就变成了：凑成金额 i - coin 需要多少硬币？答案是 dp[i - coin]。

• 所以，如果我们使用这枚硬币 coin，总硬币数就是 1 + dp[i - coin]。

• 我们需要遍历所有可用的硬币 c in coins，找出能使 1 + dp[i - c] 最小的那个值。

• 因此，状态转移方程是：dp[i]=min_cintextcoins,igec1+dp[i−c]

第四步：确定初始状态

• dp[0] = 0：凑成金额 0 需要 0 个硬币。这是最基础的解。

• 对于其他 dp[i]（当 i > 0 时），我们可以将它们初始化为一个“不可能”的大数，比如 Infinity。这表示这些金额初始时是无法凑成的。在后续计算中，如果 dp[i] 能被更新，它就会变成一个有限的数；如果循环结束后它仍然是 Infinity，就说明这个金额无法凑成。

代码实现 (Bottom-Up)

JavaScript

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
    // 1. 定义状态: dp[i] 表示凑成金额 i 所需的最少硬币数
    // 初始化为一个大数，表示“不可达”
    const dp = new Array(amount + 1).fill(Infinity);

    // 2. 初始状态
    dp[0] = 0;

    // 3. 状态转移: 从金额 1 遍历到 amount
    for (let i = 1; i <= amount; i++) {
        // 对于每个金额 i，尝试使用每一种硬币
        for (const coin of coins) {
            // 如果当前金额 i 可以由 coin 凑成
            if (i - coin >= 0) {
                // dp[i-coin] 必须是一个可达状态（不是Infinity）
                if (dp[i - coin] !== Infinity) {
                    // 状态转移方程
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
    }
    
    // 4. 返回结果
    // 如果 dp[amount] 还是初始的 Infinity，说明无解
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// 测试
const coins = [1, 2, 5];
const amount = 11;
console.log(`零钱兑换: 凑成${amount}元最少需要 ${coinChange(coins, amount)} 个硬币。`); // 输出 3 (5+5+1)

const coins2 = [2];
const amount2 = 3;
console.log(`零钱兑换: 凑成${amount2}元最少需要 ${coinChange(coins2, amount2)} 个硬币。`); // 输出 -1

总结

动态规划并非某种具体的算法，而是一种解决问题的思想范式。它的强大之处在于能将指数级复杂度的暴力搜索问题，优化到多项式复杂度。

掌握它的关键在于：

1. 识别模式：通过练习，培养出对“最优子结构”和“重叠子问题”的嗅觉。

2. 精确定义：花最多的时间去思考dp[i]的准确含义。定义对了，问题就解决了一半。

3. 推导关系：找到状态之间的递推关系，这是连接子问题和原问题的桥梁。

4. 实践出真知：动态规划的技巧和模式非常多（如背包问题、最长公共子序列、区间DP等），只有通过大量练习，才能真正内化这种思想，并灵活运用于未知问题。