题目链接：https://leetcode-cn.com/problems/coin-change/
思路：这个题目可以转换为「爬楼梯」的模式。
- dp方程法
- dp[i]：表示凑齐总金额为i所用的最少零钱数
- dp转移方程式：dp[i] = min(dp[i-1], dp[i-2], dp[i-5]) + 1 (注：此题coins=[1, 2, 5])
- 初始化: dp[0] = 0;
代码：
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
// 初始化一个长度为amount+1长度的数组，并且把每个元素设为足够大的数。
let dp = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER)
// dp初始化
dp[0] = 0;
for(let i = 1; i <= amount; i++) {
for(let j = 0; j < coins.length; j++) {
if(coins[j] <= i) {
// 取类似「思路」中「min(dp[i-1], dp[i-2], dp[i-5]) + 1」的结果
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
}
}
}
// 最后如果dp[i]中元素相对初始化没有变的话，则表明没有凑成总额为i的组合
return dp[amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[amount];
};
