场景

给定硬币种类为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