每日一算--零钱兑换

2,082

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例

输入: amount = 10, coins = [10]
输出: 1

日常找规律

瞬间想不到的话,就来分析找规律:

输入: amount = 5, coins = [1, 2, 5]

  • 有1、2、5三种类型的硬币,选择第一枚硬币的时候有两种方式,选择1元或者不选择1元。
  • 选择1元amount = 4; 不选择1元 amount = 5 依次对每种类型的硬币就像这样选择,直到amount为0的选择,就是其中之一的解。

得出动态方程

dp(amount) = dp(i,amount-coins[i]) + dp(i++,amount)
边界条件:
amount-coins[i] < 0     为无法凑出整数amount
amount = 0              找到符合的组合
i >= len(coins)         所有硬币类型都试过了

实现方式

递归选择实现

  • 时间复杂度 O(2^n)
function change(coins, i, amount) {
  // 无法凑整
  if (amount < 0) {
    return 0
  }
  // 符合结果的组合
  if (amount == 0) {
    return 1
  }
  // 所有硬币类型都试过了
  if (i >= coins.length) {
    return 0
  }
  // 选择当前硬币 + 不选择当前硬币
  return change(coins, i, amount-coins[i]) + change(coins, i+1, amount)
}

优化递归实现

  • 时间复杂度 O(m * n) 解法一中,会造成大量的重复计算,因此我们通过缓存结果来提高性能。通过解法一,我们知道整个组合数就是:
  • 对每种硬币类型只有选和不选两种结果 选择后 amount = amount -(选择的硬币面额)

function change(coins, amount) {
  const dp = new Array(amount + 1)
  for (let i = 0; i < dp.length; i++) {
    if ( i === 0 ) {
      dp[i] = 1
    } else {
      dp[i] = 0
    }
  } 
  for ( let i = 0; i < coins.length; i++) {
    for ( let j = 1; j <= amount; j++) {
        if ( coins[i] <= j) {
            dp[j] = dp[j] + dp[j- coins[i]]

        }
    }
  }
  return dp[amount]
}

总结