动态规划之零钱兑换

前言

算法的重要性不言而喻，算法不用过于深究语言的实现，它里面的思想才是精髓。

让我们进入leetcode 322题

问题

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

边界条件

做题之前，很多人都忽略了较为重要的边界条件，直接开干，但还是要看看边界条件比较好。 这里的边界条件是 :

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思考

硬币的面额是固定的，通过找到最佳的组合方式来凑出指定的金额。这个最佳的组合方式用（最少的硬币个数）来评判。像这种求最值的，一般都会想到用贪心，或者动态规划。

贪心的思路是从局部的最优解推导到全局的最优解，而动态规划则是通过状态转移来求出解。动态规划核心是状态转移。

动态规划可以由三部分组成：

1. dp数组表达含义的确定
2. 状态转移方程的建立
3. 初始状态的确定

这里可以自下而上的想，从给定的coins当中，可以知道硬币的所有面值，而dp[n]代表的就是总金额为n的最少组合硬币个数（如果组合不了，则返回-1）。

可以想到往前转移，总金额为n，是由conins当中的硬币组合而成，那么dp[n]可以是dp[n-coins[0]]或者dp[n-coins[1]]或者dp[n-coins[2]]等等，由前面的硬币组合所组成的总金额加上它本身得到。

举个例子,比如有coins = [1,2,5] 三种面额的硬币，要组成的总金额为11。 则有dp[11] = min(dp[11-1],dp[11-2],dp[11-5]) + 1(它本身也是一枚硬币)

这样不就实现了状态转移啰，前面的状态通过状态转移方程，可以变成后面的状态

再确定一下初始状态: dp[0] = 0

这样就可以开始写了

代码

function coinChange(coins: number[], amount: number): number {
    // 1. dp数组代表什么？
    // dp[n]代表 amount的时候，所需最少的硬币个数
    // 因为是取最小的值，所以用Infinity 可以避免出错，或者你也可以用amount+1之类的
    const dp:number[] = new Array(amount+1).fill(Infinity)
    // 2. 状态转移方程
    // dp[n] = Math.min(dp[n-coins[0]],dp[n-conins[1]]...) + 1 
    // 3. 初始状态
    dp[0] = 0 

    // 从总金额为1 开始，去给dp数组找状态
    for(let i = 1 ;i<=amount;i++){
        // 通过索引取硬币
        for(let j = 0;j<coins.length;j++){
            // 总金额必须 不小于 硬币的面值 才可以
            if(i >= coins[j]){
                // 注意：这里因为会逐个取到所有的硬币，因此可以用dp[i]来暂存
                // 就是两两互相比较取一次，再和下一个比，再取一次最小值，以此类推
            // Infinity(初始状态), dp[i-coins[1]]+1 ...dp[i-coins[length-1]]+1
                dp[i] = Math.min(dp[i] , dp[i-coins[j]]+1)
            }
           
        }
    } 
    return dp[amount] === Infinity ? -1 : dp[amount]
};

写在最后

欢迎大家在评论区多多交流鸭～