假设你有面值为 1, 2, 5 的硬币，你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1, 2, 5 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制约，是互相独立的。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。

所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

搞清楚上面这几个关键点，解法的伪码就可以写出来了：
1、暴力递归
写状态转移方程，是暴力解法了，以下代码的数学形式就是状态转移方程： 
const dp = (coins,amount) =>{
    if(amount === 0) return 0;
    if(amount < 0) return -1;
    let res = Number.MAX_VALUE;
    for(let coin of coins){
        // 计算子问题的结果
        let subProblem = dp(coins, amount - Number(coin));
        // 子问题无解则跳过
        if(subProblem === -1)continue;
        res = Math.min(res,subProblem + 1);// 在子问题中选择最优解，然后加一
        
    }
    return res === Number.MAX_VALUE ? -1 : res;
}
function minMoney( arr ,  aim ) {
   return dp(arr,aim)
}
子问题的结果为什么要加 1（subProblem + 1），而不是加硬币金额之类的？动态规划问题的关键是 dp 函数/数组的定义，你这个函数的返回值代表什么？你回过头去搞清楚这一点，然后就知道为什么要给子问题的返回值加 1 了。
需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看

子问题总数为递归树的节点个数，但算***进行剪枝，剪枝的时机和题目给定的具体硬币面额有关，所以可以想象，这棵树生长的并不规则，确切算出树上有多少节点是比较困难的。对于这种情况，我们一般的做法是按照最坏的情况估算一个时间复杂度的上界。

假设目标金额为 n，给定的硬币个数为 k，那么递归树最坏情况下高度为 n（全用面额为 1 的硬币），然后再假设这是一棵满 k 叉树，则节点的总数在 k^n 这个数量级。

接下来看每个子问题的复杂度，由于每次递归包含一个 for 循环，复杂度为 O(k)，相乘得到总时间复杂度为 O(k^n)，指数级别。

2、带备忘录的递归 
let memo = [];
const dp = (coins,amount) =>{
    if(amount === 0) return 0;
    if(amount < 0) return -1;
    // 查备忘录，防止重复计算
    if(memo[amount] !== -666)return memo[amount];
    let res = Number.MAX_VALUE;
    for(let coin of coins){
        // 计算子问题的结果
        let subProblem = dp(coins, amount - Number(coin));
        // 子问题无解则跳过
        if(subProblem === -1)continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res,subProblem + 1);     
    }
     // 把计算结果存入备忘录
    memo[amount] = res === Number.MAX_VALUE ? -1 : res;
    return memo[amount];
}
function minMoney( arr ,  aim ) {
    memo = Array(aim+1).fill(-666);
   return dp(arr,aim)
}
很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。
3、dp 数组的迭代解法----    dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。 
function minMoney( arr ,  aim ) {
    let dp = Array(aim+1).fill(aim+1);// 数组大小为 amount + 1，初始值也为 amount + 1
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for(let i=0;i <dp.length; i++){
        // 内层 for 循环在求所有选择的最小值
        for(let coin of arr){
            if(i - coin < 0){
                continue;
            }// 子问题无解，跳过
            dp[i] = Math.min(dp[i],1 + dp[i -Number(coin)])
        }
    }
   return (dp[aim] === aim +1) ? -1 : dp[aim];
}
function minMoney( arr ,  aim ) {
    let dp = new Array(aim + 1).fill(Infinity);// 初始化dp数组
    dp[0] = 0;// 面额0只需要0个硬币兑换
    for (let i = 1; i <= aim; i++) {// 循环面额
        for (let coin of arr) {// 循环硬币数组
            if (i - coin >= 0) {// 当面额大于硬币价值时
                // dp[i - coin]： 当前面额i减当前硬币价值所需要的最少硬币
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[aim] === Infinity ? -1 : dp[aim];
}
module.exports = {
    minMoney : minMoney
};

PS：为啥 dp 数组中的值都初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢？因为后面有 dp[i - coin] + 1，这就会导致整型溢出。