一、题目
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
点击查看原题
二、思路
1)动态规划
由于每种硬币是无限量的,所以每种硬币可能有k个,满足k*coins[i] <=amount
,如果使用暴力法进行求解,对于找零值为amount-k*coins[i]
的组合数量会反复求解,为了把这个子问题记录下来,使用二维数组dp[i][j]
代表前i
个硬币组成金额j
的组合数量,可以得到状态转移方程(第i
个硬币是coins[i-1]
):
如此,dp[coins.length][amount]
为所求解。
2)优化
由于dp[i][j]
的状态指依赖于i-1
的状态,可以进一步优化时间和空间。
考虑到coins[i]
可以使用多次,那么可以使用当前的状态,状态转移方程为:
其中的dp[j-coins[i]]
也包括了选了多个coins[i]
的组合数。
三、代码
1)动态规划
class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;
for (int i = 1; i < dp.length; i++) {
int coin = coins[i-1];
for (int j = 0; j <= amount; j++) {
dp[i][j] = dp[i-1][j];
int sumCoin = coin;
while (j >= sumCoin) {
dp[i][j] += dp[i-1][j-sumCoin];
sumCoin += coin;
}
}
}
return dp[coins.length][amount];
}
}
时间复杂度为O(amount````*coins.length)
,空间复杂度为O(amount``*coins.length)
2)优化
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}
时间复杂度为O(amount``*coins.length)
,空间复杂度为O(amount``)