javascript算法-动态规则

动态规划（dynamic programming, DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。

用动态规划解决问题时，要遵循三个重要步骤：

(1) 定义子问题；

(2) 实现要反复执行来解决子问题的部分；

(3) 识别并求解出基线条件。

动态规划解决 最少硬币找零问题

最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可用的硬币面额d 1,…, dn及其数量，找出有多少种找零方法。最少硬币找零问题是给出要找零的钱数，以及可用的硬币面额d1,…, dn及其数量，找到所需的最少的硬币个数。

例如，美国有以下面额（硬币）:d1= 1, d2= 5, d3= 10, d4= 25。如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（1美分）。

如何将这个解答转化成算法？

下面来看看算法。

    function minCoinChange(coins, amount) {
      const cache = []; // {1}
      const makeChange = (value) => { // {2}
        if (! value) { // {3}
          return [];
        }
        if (cache[value]) { // {4}
          return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) { // {5}
          const coin = coins[i];
          newAmount = value - coin; // {6}
          if (newAmount >= 0) {
            newMin = makeChange(newAmount); // {7}
          }
          if (
            newAmount >= 0 && // {8}
            (newMin.length < min.length -1 || ! min.length) && // {9}
            (newMin.length || ! newAmount) // {10}
          ) {
            min = [coin].concat(newMin); // {11}
            console.log('new Min ' + min + ' for ' + amount);
          }
        }
        return (cache[value] = min); // {12}
      };
      return makeChange(amount); // {13}
    }

minCoinChange参数接收coins参数（行{1}），该参数代表问题中的面额。对美国的硬币系统而言，它是[1, 5, 10, 25]。我们可以随心所欲地传递任何面额。此外，为了更加高效且不重复计算值，我们使用了cache（行{1}——这个技巧称为记忆化）。

接下来是minCoinChange函数中的makeChange方法（行{2}），它也是一个递归函数，用来解决问题。makeChange函数在行{13}被调用，amount作为参数传入。由于makeChange是一个内部函数，它也能访问到cache变量。

现在我们来看算法的主要逻辑。首先，若amount不为正（< 0），就返回空数组（行{3}）；方法执行结束后，会返回一个数组，包含用来找零的各个面额的硬币数量（最少硬币数）。接着，检查cache缓存。若结果已缓存（行{4}），则直接返回结果；否则，执行算法。

为了进一步帮助我们，我们基于coins参数（面额）解决问题。因此，对每个面额（行{5}），我们都计算newAmount（行{6}）的值，它的值会一直减小，直到能找零的最小钱数（别忘了本算法对所有的x < amount都会计算makeChange结果）。若newAmount是合理的值（正值），我们也会计算它的找零结果（行{7}）。

最后，我们判断newAmount是否有效，minValue（最少硬币数）是否是最优解，与此同时minValue和newAmount是否是合理的值（行{10}）。若以上判断都成立，意味着有一个比之前更优的答案（行{11}——以5美分为例，可以给5便士或者1个5美分镍币，1个5美分镍币是最优解）。最后，返回最终结果（行{12}）。

测试一下这个算法。

    console.log(minCoinChange([1, 5, 10, 25], 36));

要知道，如果我们检查cache变量，会发现它存储了从1到36美分的所有结果。以上代码的结果是[1, 10, 25]。