给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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];
}
};