JavaScript 算法之 动态规划

Question

背包问题

首先我们从背包问题开始。

一个背包可以装4kg的物品，现有物品音响（3000元|4kg）笔记本电脑（2000元|3kg）、吉他（1500元|1kg），那么我们怎么拿可以使物品价值最高？

1、 最简单的方法：罗列所有组合，选取符合条件的最高的那个。

物品是1个的时候，我们可以拿或不拿，即2种选择；物品3个的时候，我们有8种选择；物品n种时，我们有 2^n 种选择——时间复杂度 O(2^n)!

2、动态规划

动态规划的核心在于合并两个子问题的解来得到更大问题的解。

那么它的难度就在于怎么把大问题分解成子问题。

在这里的例子里，装入背包的物品价值取决于物品类型和背包容量两个因素，以这两个因素为维度，利用网格来得到问题的解（本质上是当容量更小、物品更少时更容易得到解）。

• 当只有一个物品时，随容量增加，很轻松可以得到容量对应的最大价值（这里作为第一行开始）。
• 当增加物品时（即下一行），那么每个格子的值将由上一行对应格子的值和当前物品价值来决定：
  • 增加物品，价值只可能增长，所以最小值是上一行对应格子的值；
  • 如果当前格子的容量可以放下当前物品，那么可能的最大值是当前物品的价值 + 上一行对应剩余容量格子的值。

1. 核心观点

动态规划并不难，通常是通过流程 递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法 一步步铺垫而来，动态规划的核心是化递归（自顶向下）为循环迭代（自底向上）。

如上面流程所示，在动态规划中，得到暴力解（即如何穷举所有可能性，也即得到“状态转移方程”）是最困难的一步。为什么说困难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不容易穷举完整。

2. 凑零钱Demo演示

假设有 k 种不同币值硬币，总金额为 n 时最少需要几枚硬币可以凑出这个金额？无法凑出则给 -1。
比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。

假设 n 总是可以被凑出来的，那么这个问题其实非常简单，我们只需要先从最大币值的硬币开始凑就可以了。然而这个假设并不总是成立，所以事实上我们需要穷举所有可能性——典型的可以采用动态规划方法来解决的问题。

下面我们按流程来解题：

1）暴力解（即状态转移方程）：

f(0) = 0;
f(n) = 1 + min{f(n - Ci)}  ( i 属于 [1, k], Ci 即对应的硬币币值)

其中，n 即总金额， i 为 1~k，即不同币值硬币个数，Ci 为对应硬币币值。

如上，可以理解为原问题的解可以通过子问题的最优解来得到，即 f(11) 是可以分解为：

• 硬币 1 元 和 f(10) 的最小硬币数
• 硬币 2 元 和 f(9) 的最小硬币数
• 硬币 5 元 和 f(6) 的最小硬币数

3种情形的最优解即为最终解，而f(10) / f(9) / f(6) 可以继续递归分解。

好了，给这个暴力解一个程序表达：

// 暴力递归
function assembleCoin(coins, amount) {
  if (amount === 0) {
    return 0;
  }

  let ans = Number.MAX_SAFE_INTEGER;
  for(let c of coins.values()) {
    // 剩余金额
    let value = amount - c;
    // 币值大于总金额，说明是无效的
    if (value < 0) continue;
    // 计算剩余金额可能的最少组合次数
    const sub = assembleCoin(coins, value);
    // 次数小于0，说明无效
    if (sub < 0) continue;

    // 该次组合有效，更新最少次数
    ans = Math.min(ans, 1 + sub);
  }

  return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}

2）带备忘录的递归

暴力解有太多的重复子问题（比如多个 f(5) 的求解）,如果重复子问题的求解结果被缓存了，那同一个子问题就只用计算一次了：

// 带备忘录的递归
function assembleCoinWithMemo(coins, amount) {
  const memo = {};
  return coinHelper(memo, coins, amount);
}

function coinHelper(memo, coins, amount) {
  if (amount === 0) {
    return 0;
  }

  if (memo[amount] !== undefined) {
    return memo[amount];
  }

  let ans = Number.MAX_SAFE_INTEGER;
  for (let c of coins.values()) {
    // 剩余金额
    let value = amount - c;
    // 币值大于总金额，说明是无效的
    if (value < 0) continue;
    // 计算剩余金额可能的最少组合次数
    const sub = coinHelper(memo, coins, value);
    // 次数-1，说明无效
    if (sub === -1) continue;

    // 该次组合有效，取最少次数
    ans = Math.min(ans, 1 + sub);
  }
  memo[amount] = ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
  return memo[amount];
}

3）动态规划：递归 --> 循环

动态规划其实和上面的备忘录法已经相当接近了，把备忘录换成 DP 表，从而自底向上求解替代自顶向下，就是动态规划：

// 动态规划
function assembleCoinDP(coins, amount) {
  // dp 表最多包含 amount + 1 种情况（包括0）
  const dp = Array(amount + 1).fill(amount + 1);
  // 最简单（自底向上的底）的情况：
  dp[0] = 0;
  // 从 1 开始填充 dp 表的过程即自底向上逐渐求解的过程
  for(let i = 1; i < dp.length; i++) {
    // 内层 for 循环求所有子问题 + 1（种硬币） 的最小值
    // 比如 i = 1，我们即求解：1元+dp[0]，2元+dp[-1]，5元+dp[-4] 等3种情况，
    // 其中后两种被 continue 直接过滤了，所以 dp[1] 很容易得到为 1；
    // 随着 i 增大，我们最终总可以得到所有的 d[i]，且必然 d[x]（x < i）是已经计算
    // 有结果的（保持 amount + 1的最大值即代表amount 为该值时无可用的硬币排布，返回 -1）
    for (let c of coins.values()) {
      if (i - c < 0) {
        continue;
      }
      dp[i] = Math.min(dp[i], 1 + dp[i - c]);
    }
  }
  return dp[amount] === amount + 1 ? -1 : dp[amount];
}

时间复杂度

最后顺便给一组实际测试时不同方式的用时：

// 1,2,5   -----------   13
4
normal: 2.667ms
4
memo: 0.166ms
4
dp: 0.171ms

// 1,2,5   -----------   27
6
normal: 35.627ms
6
memo: 0.185ms
6
dp: 0.183ms

// 1,2,5   -----------   39
9
normal: 18192.081ms
9
memo: 0.191ms
9
dp: 0.206ms

可以看到，相比带备忘录的递归和动态规划，暴力递归的用时太可怕了：

• 暴力递归时间复杂度：O(k*n^k)
• 备忘录：O(kn)
• 动态规划：O(kn)

如上，希望通过例子可以对动态规划更容易理解一些。