找零问题与动态规划-白红宇

今天岩岩抛出了一道 code war 上的题目，大意如下：

一个函数接收两个参数，第一个参数是数字，第二个参数是数字数组，求数组里的数字加起来等于第一个参数的所有情况，可以无限次使用数组里的数字。譬如 5, [1, 2, 5]，总共有

1 + 1 + 1 + 1 + 1 = 5

1 + 1 + 1 + 2 = 5

1 + 2 + 2 = 5

5 = 5

这样 4 种情况，所以返回 4。第一个参数为 0 的时候，返回 1。

后来我发现在 leet code 也有类似的题，是个找零问题，就是不同面值的硬币组合成一个数有多少种情况。还挺有意思的，我就做了一下，用了递归：

const change = function (sum, arr) {    const nums = arr.sort((a, b) => a - b);    return add(sum, nums);};const add = function (sum, nums) {    const min = nums[0];    if (sum === 0 || sum === min) return 1;    let res = 0;    if (nums.includes(sum)) res += 1;    for (let i = 0; i < nums.length; i++) {        const last = sum - nums[i];        if (last >= nums[i]) res += add(last, nums.slice(i));    }    return res;}复制代码

在 code war 上是成功提交了，但在 leet code 上却超时了，性能太差了。然后岩岩在 code war 的答案里看到了这样一段代码：

const countChange = (m, c) => {  const a = [1].concat(Array(m).fill(0));  for (let i = 0, l = c.length; i < l; i++)     for (let x = c[i], j = x; j <= m; j++)       a[j] += a[j - x];  return a[m];}复制代码

看得我俩十分懵逼，苦思半天还是懵逼。于是我上网搜到了相同解法的 C++ 版本:

using namespace std;class Solution {
    public:    int change(int amount, vector
    
     & coins)     {        vector
     
       dp(amount + 1, 0);        dp[0] = 1;        for (int coin : coins)         {            for (int i = coin; i <= amount; ++i)             {                dp[i] += dp[i - coin];            }        }        return dp[amount];    }};复制代码

说是用的动态规划（知道了这点很关键），虽然没具体解释，但这个版本的命名比上面那个 JS 版本实在是好懂太多了，dp 就是 dynamic programming 嘛，所以已经可以勉强推导他的思路：

dp 是一个长为 amount + 1 的表，依次用来记录组合成 0、1、2、3、、、amount 各有多少种情况，dp[0] 初始为 1，其他都初始为 0。

接下来循环硬币值，记录从当前硬币值到 amount 的所有组合情况。状态转移方程为：dp[i] += dp[i - coin]。什么意思呢？假设我们求 [1, 2, 5] 这三个面值组成 5 的情况，现在我先拿出一个 2，那我是不是只要再有一个 3 就可以得到 5 了，那我只要计算有多少种组合成 3 的情况就好了，即当 coin = 2 的时候，dp[5]~new~ = dp[5]~old~ + dp[3]，以此类推。

for (int coin : coins) {    for (int i = coin; i <= amount; ++i)     {        dp[i] += dp[i - coin];    }}复制代码

以上这段代码的意思就是先计算我拿出 1 的时候，组合成 12345 的情况数，再计算当我拿出 2 的时候，组合成 2345 的情况数（加上拿出 1 时候的情况数），再计算拿出 5 的时候，组合成 5 的情况数（加上拿出 1 和拿出 2 时候的情况数），最后得出的 dp[5] 就是我们想要的结果。你可能会问我们要的是 dp[5]，中间的 dp[1]dp[2]...dp[4] 有什么用，其实这就是动态规划的精髓，会把子问题的解记录（缓存）下来，因为这些子问题会在计算过程中多次用到，就不需要每次都计算了。

上述解法的大体思路其实和下面这个朴素递归是相似的，都是把问题分解为子问题进行求解，动态规划强就强在会缓存子问题的解避免重复计算从而提高效率。

const countChange = function(money, coins) {  if (money < 0 || coins.length === 0)    return 0  else if (money === 0)    return 1  else    return countChange(money - coins[0], coins) + countChange(money, coins.slice(1))}复制代码

以后当你碰到一个问题，它可以分解为多个子问题，并且子问题有重叠时，就用动态规划吧。

啊，我真是太菜了……一个动态规划的题搞了半天……