day15: 322. 零錢兌換（中等）
考點：動態(tài)規(guī)劃
思路：也是所謂的填表格，但是要找好填表格的角度安皱。
日常思維：循環(huán)所有數(shù)組踪宠，用目標元素除以當前元素的值存為結(jié)果，如果整除則存入褪测，如果沒有整除則查看余數(shù)中的值是否存在于當前數(shù)組中，存在則返回商+余數(shù)的硬幣個數(shù)，每次求最小值涵卵。
動態(tài)規(guī)劃：可以將其劃分成當總數(shù)為[1,amount]時，用[1,2,5]硬幣分別需要多少個可以將其填滿荒叼，將求得的結(jié)果緩存轿偎。
參考leecode
image.png
var coinChange = function (coins, amount) {
//amount為0直接返回
if (amount == 0) return 0;
//沒有零錢
if (coins.length == 0) return -1;
let dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
//計算使用icon找零i需要多少個硬幣
for (let i = 0; i <= amount; i++) {
for (let icon of coins) {
//i-icon<0說明不夠找，還用初始化的值被廓。否則說明夠找
if (i - icon >= 0) {
dp[i] = Math.min(dp[i], dp[i - icon] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};
console.log(coinChange([1, 2, 5], 11));
