const numOfCoin = (price, coins) => {
const dp = new Array(coins.length + 1).fill().map(_ => [])
for (let j = 0; j <= price; j += 1) {
dp[coins.length][j] = 0
}
for (let i = 0; i <= coins.length; i += 1) {
dp[i][0] = 1
}
for (let i = coins.length - 1; i >= 0; --i) {
for (let j = 1; j <= price; ++j) {
dp[i][j] = 0
if (coins[i] <= j) {
dp[i][j] = dp[i][j - coins[i]] + dp[i + 1][j]
} else {
dp[i][j] = dp[i + 1][j]
}
}
}
return dp[0][price]
}
console.log(numOfCoin(32, [1, 5, 11])) //15
console.log(numOfCoin(200, [1, 2, 5, 10, 20, 50, 100, 200])) // 73682
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…