十一节前练习了使用动态规划、回溯、贪心等算法实现找零问题：
动态规划、回溯、贪心算法解找零问题（最小张数付款问题）（Javascript实现）_yangxinxiang84的专栏-CSDN博客
是实现出来了，也没有问题，但是总感觉使用动态规划实现的时候状态转移部分有点奇怪，有点复杂，理解上有一些困难。遂向大神川哥请教，大神就是大神，咔咔咔一会给我发了一个Java版本过来，当看到川哥的实现的代码的时候，我以为他理解错了（怀疑实现错了），因为代码确实太精炼了，居然没有用除法，没有用取模。。。
当我将代码翻译成JS版本，测试了很多个场景后，发现都没问题，大神就是大神。这是我目前看到过的所有找零需求实现中最精炼的一个版本：
2，需求和实现：我们有n种不同面值的硬币，需要支付n元（整数），最少需要多少个硬币？
比如具体的：我们有 3 种不同面值的硬币，11 元、5 元、1 元，我们要支付 15 元（整数），最少需要 多少个硬币？假设每种硬币都有无数个，想用多少用多少，哈哈。
最少要3 个硬币（3 个 5 元的硬币）。
直接上代码：
function coin2Change(coins = [11, 5, 1], amount = 15) {
// 最大值假设就是要求和的数量加上1，这个一定是最大的，再多的硬币也就是1分的全部构成
const max = amount +1;
// 初始化dp数组，初始化到大小为金额大小再加1，因为dp的第一个元素是0
const dp = new Array(amount +1)
dp.fill(max)
dp[0] = 0;
// 外层循环就是构建F(0)到F(i)的过程
for(let i = 1; i<=amount; i++){
// 内层循环是遍历整个零钱数组的过程：当前需要凑的钱数 i 都尝试一下所有可用面值的硬币
for(const coin of coins) {
// 只有当前的零钱比当前的总额 i 小，才有可能被加上，超过了直接下一个
if(coin <= i){
// 当前 F(i)的局部最优解，一定是当前 F(i) 和F(i - 当前面值) + 1里面比较小的一个
dp[i] = Math.min(dp[i], dp[i-coin] + 1)
}
}
}
// 有可能凑不足需要的钱，返回 -1
return dp[amount] > amount ? -1 : dp[amount] ;
}
// 测试
const amount = 21
const coins = [11, 5, 1]
const rst = coin2Change(coins, amount);
console.log(`call coin2Change end, rst = ${rst}`);
3，难点分析
这个需求，代码很短，注释也比较详尽，但是精炼的代码有时候理解上去更困难，需要理解这种实现背后的方法、思想。我前后花了一天多的时间，算是理解了，这个算法的难点是理解状态转移方程：
F(i) = min( F(i), F(i-Cj) + 1 ); j=0->n-1; n=可用硬币面值类型数
动态规划就是数学的归纳演绎，确实比较抽象！这里的思路是：假设在计算F(需要找零的钱)之前，我们已经计算出F(0) 到F(需要找零的钱-1)的值。dp就是F哈，代表的是状态：
用一维数组dp[]来记录状态，dp[] 中每个元素默认是一个很大的数（比要找零的钱大即可，也就是这代码中的const max = amount +1;），dp[0] = 0，也就是找0块钱的时候，需要0个硬币，dp[需要找零的钱] 含义是凑足“需要找零的钱”所需要的最小硬币数。
dp[需要找零的钱] = min（ dp[需要找零的钱] ， dp[需要找零的钱 - 当前使用硬币的面值] + 1），从1单位（元）开始，逐一计算到当前面值，每一个需要找零的钱数都去尝试使用每一种可用的硬币，取最小值。F(i-Cj) + 1指的是 ： 当前需要找零的钱所需硬币数，等于“前”一个需要找的钱硬币数F(i-Cj) （“前”一个指的事：需要找零的钱减去当前硬币面值）加上1，加1是因为使用了1次该面值的硬币了。
附上川哥原稿：
4，动态规划递归版实现理解了上面的思路之后，使用递归的方案来实现就比较简单了，撸一遍代码：
（我理解的就是递归，但有点把它叫做递归版动态规划）
function coin2ChangeR(coins, amount){
// 再包装一下，主要是处理不满足条件的场景。同时做备忘录缓存
const cache = new Map();
// 递归动态规划实现找零
function change(coins, amount){
if(amount === 0){
return 0;
}
// 备忘录缓存优化
if(cache.get(amount)){
return cache.get(amount);
}
const counts =[];
// 对当前的amount, 每一个都尝试使用一下所有面值币种硬币，然后取最小值
for(const coin of coins){
if(coin <= amount) {
const count = change(coins, amount - coin) +1;
counts.push(count)
}
}
const minCount = Math.min(...counts);
cache.set(amount, minCount)
return minCount
}
const totalMin = change(coins, amount)
return totalMin > amount ? -1 : totalMin
}
// 测试一下
const amount = 10
const coins = [11, 6, 3]
const rstR = coin2ChangeR(coins, amount);
console.log(`coin2ChangeR :: call end, rstR = ${rstR}`);
