vlambda博客
学习文章列表

算法 | 理解动态规划

本文将从一个例子出发，介绍暴力搜索是怎么一步一步很自然地进化到动态规划的，并以此角度来理解动态规划。

题目：零钱兑换。给定一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（表示总金额），计算并返回可以凑成总金额的最少硬币个数。如果没有任何一种硬币组合能组成总金额，就返回 -1。假设每种硬币的数量是无限的。

这道题之前用做过——“每次尽量找最大面额”，但是不对。代码如下：

var coinChange = function (coins, amount) {
    if (amount === 0) return 0; // 提前退出（省得排序）
    let ans = 0;
    // 依次遍历硬币，面值从大到小
    coins.sort((a, b) => b - a); // 原地排序：从大到小
    for (let x of coins) {
        if (amount === 0) break;
        if (x > amount) continue; // 面额太大，忽略
        // 贪心策略：在可选的硬币中，挑面值最大的，兑换到底
        ans += parseInt(amount / x);
        amount = amount % x;
    }
    return amount ? -1 : ans;
};

执行结果：解答错误
输入：[186,419,83,408] 6249

今天我们试试暴力搜索。思路是分治，即把“兑换总金额 amount” 的问题划分成 “先兑换 coins[i]，再兑换剩余的 amount - coins[i]” 这几个子问题。然后针对子问题，再次划分，直到剩余金额为 0。

比如 coins = [10,9,1]，amount = 18，方案如下：

上图就是搜索要遍历的整个状态空间，图中的每个结点都有个状态 [剩余金额, 已用硬币枚数]，起始点是 [18, 0]。蓝框里的数字就是“剩余金额”，而“已用硬币枚数”会因到达结点的路径的不同而不同，比如结点 8，从起点到它有三条路径：

  1. 直接兑换 10 块，此时它的状态是 [8, 1]
  2. 先兑换 9 块再兑换 1 块，此时状态是 [8, 2]
  3. 先兑换 1 块再兑换 9 块，此时状态是 [8, 2]

而到结点 0 的路径就更多了，我们在它的一系列状态 [0,x] 中选个最小的 x 便是该问题的答案。

代码实现如下，从 [amount,0] 到 [0,x] 的深度优先遍历：

var coinChange = function (coins, amount) {
    let ans = Infinity;
    // 深度优先遍历：当前金额amount，已用硬币枚数x 
    const dfs = function (amount, x) {
        if (amount === 0) {
            ans = Math.min(ans, x); // 到结点0了，挑个最小值
            return;
        }
        // 本层逻辑：N个分支
        for (let coin of coins) {
            if (coin <= amount) {
                dfs(amount - coin, x + 1); // 兑换剩余的，x+1
            }
        }
    }
    // 从 [amount, 0] 开始
    dfs(amount, 0);
    return ans === Infinity ? -1 : ans;
};

执行结果：超出时间限制
最后执行的输入：[1,2,5] 100

超时了，说明代码运行太慢了。

分析原因

继续以 coins = [10,9,1]，amount = 18 为例。

我们从 [18, 0] 出发，每次有 3 个分支，要么找 10 块、要么找 9 块、要么找 1 块，每多一层就会多出现 *3 条路径，也就是说状态空间是呈 3 的指数级增长的，所以搜索会慢一些。虽然慢，但它算出来的结果一定是对的（相比贪心而言），因为它会遍历整个状态空间，最终发现 [0, 2] 用两枚是最优的。

思考：如果能避免分支的累乘，是否就能让搜索变快一点？

优化思路

为了方便讨论，我们看个简单点的例子，coins = [9,1]，amount = 18。它的状态图如下：

算法 | 理解动态规划

为了进一步简化问题，我们先忽略图中灰色的边，这样一来，从 18 到 0 就分成了两大步：

  • 先从 18 到 9，有两个分支：A1（1 张 9 块）和 A2（9 张 1 块）
  • 再从 9 到 0，也有两个分支：B1（1 张 9 块）和 B2（9 张 1 块）

所以，从 18 到 0 就一共有 2*2=4 条路径，分别是：A1B1、A1B2 和 A2B1、A2B2。

现在我们考虑：从 9 到 0 的那两个分支，哪个更好？显然是 B1——1 张 9 块的，因为它用的硬币枚数更少。那么从 18 到 0 的这 2*2=4 条路径都有用吗？显然不是。因为只要我们到了 9，不论是从 A1 来还是从 A2 来，后面必然是从 9 到 0，而从 9 到 0 的那个 B2 分支完全没用，因为与 B1 相比它必然不够好。也就是说，搜索蛮力遍历的那 2*2=4 条路径，其中与 B2 相关的那两条路径是完全没用的。砍掉了 B2 之后，总路径数就变成了 2*1=2 条，这样就能避免分支的累乘。

那么，对于特定结点，如何砍掉不必要的分支而只留唯一的那一个呢？试想我们砍掉 B2 分支的逻辑——因为与 B1 相比它不够好，它用了更多的硬币枚数。

思考：对于每个结点，我们能否只要知道“兑换该金额所需要的最少硬币枚数”这个最优的兑换值就足够了呢？答案是肯定的。

从原始状态，到最优化目标

在原始的搜索中，状态是个二元组 [剩余金额，已用硬币枚数]，目标是状态 [0, x] 是否可达，是个 true 或者 false 的一个可行问题。我们可以将状态优化为 [剩余金额]，而对于每个状态只求它的 最少硬币枚数 这一最优化目标的值。现在，问题就从一个可行问题变成了一个“对于每种金额去求最少硬币枚数”的最优化问题，状态也从二元变成了一元。

我们来对比下新旧状态所对应的状态空间，如下：

虽然它们的分支分布看起来是一样的，但是在新状态下是不会遍历分支的所有组合的，因为它只取值最小的那一个。除了状态从二元的 [剩余金额，已用硬币枚数] 变成了一元 [剩余金额] 之外，状态的迁移（即图中的边）逻辑也是不同的，具体表现为：

  • 图左：原始的状态是 [剩余金额 amount，已用硬币枚数 x]，它的三条边分别代表了三个子问题，即 [amount-10, x+1]、 [amount-9, x+1]、 [amount-1, x+1]。
  • 图右：新状态是 [剩余金额]，最优化目标是 最少硬币枚数，它的三条边代表了状态 n 和它的三个子状态 n-10、 n-9、 n-1，且它们的最优化目标之间存在着递推关系 opt(n) = 1 + min(opt(n-10), opt(n-9), opt(n-1))。

opt, optimization, 最优化目标 ~ 题目求解的最优化问题

状态 + 最优化目标 + 最优化目标之间具有递推关系 = 最优子结构

最优子结构是一个整块。比如找 9 块有两个方案（B1 和 B2）、找 18 块有四个方案（A1B1、A1B2 和 A2B1、A2B2），但是我们就在这诸多方案中选一个最好的作为“找 9 块或者找 18 块”的一个代表，此时这些方案们一起就分别是个整块。

我们把很多种方案的这个大集合缩成了一个最优化目标——“最少硬币枚数”的这一个值。这样一来，状态空间就从一个很大的规模变成了一系列的最优化目标，再加上递推关系，便可以有顺序且不重复地求解原问题的最优解。这就是动态规划的思路。

  • 状态 9，最优化目标是 1
  • 状态 18，最优化目标是 2
  • 递推关系： opt(n) = 1 + min(opt(n-1), opt(n-9), opt(n-10))

动态规划的递推实现，代码如下：

var coinChange = function (coins, amount) {
    // 最优化目标：金额 i 最少需要 opt[i] 枚硬币
    let opt = (new Array(amount + 1)).fill(Infinity);
    opt[0] = 0; // 递推边界
    // 动态规划：从小到大，开始递推最优化目标
    for (let i = 1; i <= amount; i++) {
        // 最优化目标的递推公式：opt(n) = 1 + min(opt(n-coin))
        for (let coin of coins)
            if (i - coin >= 0) {
                opt[i] = Math.min(opt[i], 1 + opt[i - coin]);
            }
    }
    return opt[amount] === Infinity ? -1 : opt[amount];
};

执行结果：通过

代码通过了，时间复杂度是 O(amount*coins.length)。

动态规划其实就是对一般搜索的一个优化，它之所以比搜索快，就是因为它不是盲目地遍历所有方案，而是只遍历那一个最优解的方案，用于递推。

动态规划

Dynamic Programming，简称 DP

动态规划是一种对问题的整个状态空间去分阶段、有顺序、不重复、决策性遍历的算法。即按照递推公式（决策）从小到大（对状态分阶段）依次计算最优解（有顺序地求解），而且只算一次（不重复）。

结合具体代码，理解 “状态(阶段) + 最优化目标(顺序) + 递推公式(决策)” 这三要素。

动态规划的三个关键分别是重叠子问题（递推的基础）、最优子结构（本质/核心）和无后效性。无后效性是指问题的状态空间是一张有向无环图（即可以按照一定的顺序来遍历求解），无环是递推的必要条件，否则从小到大递推的时候就会出现循环依赖。

核心：最优子结构

总结

本文通过“零钱兑换”的例子，介绍了动态规划是怎么一步一步很自然地从搜索变过来的。动态规划其实就是对一般搜索的一个优化，它之所以比搜索快，就是因为它不是盲目地遍历所有方案，而是只遍历那一个最优解的方案，用于递推。

先考虑搜索也方便我们梳理问题的整个状态空间，进而有助于我们去提炼状态和最优子结构。最优子结构是动态规划的核心，只要能把递推公式写出来，工作也就完成了一大半。剩下的任务就是照着方程写几个循环来递推实现了，外层循环是状态，内存循环是对最优化目标的决策。

状态 + 最优化目标 + 最优化目标之间具有递推关系 = 最优子结构

eg. 最优子结构

  • “设 opt[i] 表示凑成金额 i 所需要的最少硬币数” 这句话就暗含了状态和最优化目标
    • 状态：金额 i
    • 最优化目标：最少硬币数 opt[i]
  • 状态转移方程： opt[i] = min { opt[i-coin] } + 1，即递推公式
    • 边界：opt[0] = 0, opt[i] = +Infinity
    • 目标：opt[amount]
  • 时间复杂度：O(amount*coins.length)

多实战，熟练运用以上思路分析问题

主要参考

https://u.geekbang.org/lesson/270?article=430105

附录

附1. 动态规划的递归实现（也称记忆化搜索）代码

var coinChange = function (coins, amount) {
    // 带记忆的搜索：总金额 i, 最少需要 cache[i] 个硬币数
    const cache = (new Array(amount + 1)).fill(-1);
    cache[0] = 0;
    // 兑换总金额 n
    const dfs = function (n) {
        if (n === 0) return 0;
        // 优先取缓存里的
        if (cache[n] !== -1) return cache[n];
        // 若缓存里没，再去递归计算
        let min = Infinity;
        for (let c of coins) {
            if (c <= n) {
                min = Math.min(min, 1 + dfs(n - c));
            }
        }
        cache[n] = min; // 即便值是 Infinity 也存，因为是“计算过的”
        return min;
    }

    let ans = dfs(amount);
    return ans === Infinity ? -1 : ans;
};

还是更推荐用递推来写动态规划，因为代码更短小更简洁，for 循环一目了然。所以就把递归实现的代码放在文末了，供参考。

推荐阅读

剑星 星刃 全支线任务汇总攻略-紧急信息 剑星 星刃 全支线任务汇总攻略-紧急信息
人生快乐法则：贪心算法 人生快乐法则：贪心算法

相关文章