关于硬币找零的问题?

淋着
  • 184
评论
阅读 321
1 个回答
✓ 已被采纳
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
撰写回答

登录后参与交流、获取后续更新提醒

宣传栏