给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10] 输出: 1
注意:
你可以假设:
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
动态规划。
完全背包问题。
class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin] return dp[-1]
class Solution { public int change(int amount, int[] coins) { int m = coins.length; int[][] dp = new int[m + 1][amount + 1]; dp[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int j = 0; j <= amount; ++j) { for (int k = 0; k * coins[i - 1] <= j; ++k) { dp[i][j] += dp[i - 1][j - coins[i - 1] * k]; } } } return dp[m][amount]; } }
下面对 k 这层循环进行优化:
由于:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - v] + dp[i - 1][j - 2v] + ... + dp[i - 1][j - kv]dp[i][j - v] = dp[i - 1][j - v] + dp[i - 1][j - 2v] + ... + dp[i - 1][j - kv]
因此 dp[i][j] = dp[i - 1][j] + dp[i][j - v]。
class Solution { public int change(int amount, int[] coins) { int m = coins.length; int[][] dp = new int[m + 1][amount + 1]; dp[0][0] = 1; for (int i = 1; i <= m; ++i) { int v = coins[i - 1]; for (int j = 0; j <= amount; ++j) { dp[i][j] = dp[i - 1][j]; if (j >= v) { dp[i][j] += dp[i][j - v]; } } } return dp[m][amount]; } }
空间优化:
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { // 顺序遍历,0-1背包问题是倒序遍历 for (int j = coin; j <= amount; j++) { dp[j] += dp[j - coin]; } } return dp[amount]; } }
function change(amount: number, coins: number[]): number { let dp = new Array(amount + 1).fill(0); dp[0] = 1; for (let coin of coins) { for (let i = coin; i <= amount; ++i) { dp[i] += dp[i - coin]; } } return dp.pop(); }
func change(amount int, coins []int) int { dp := make([]int, amount+1) dp[0] = 1 for _, coin := range coins { for j := coin; j <= amount; j++ { dp[j] += dp[j-coin] } } return dp[amount] }
class Solution { public: int change(int amount, vector<int>& coins) { vector<int> dp(amount + 1); dp[0] = 1; for (auto coin : coins) { for (int j = coin; j <= amount; ++j) { dp[j] += dp[j - coin]; } } return dp[amount]; } };