动态规划（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]。
