场景
给定硬币种类为1,5,11
求找零32共有多少种情况?
感觉应该是f(n) = f(n-1) + f(n-5) + f(n-11)
不知道这么用代码实现
原来这个题这么复杂
美团校招在线考试笔试题:钱币面值组合
给定硬币种类为1,5,11
求找零32共有多少种情况?
感觉应该是f(n) = f(n-1) + f(n-5) + f(n-11)
不知道这么用代码实现
原来这个题这么复杂
美团校招在线考试笔试题:钱币面值组合
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