You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Example 1:
Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.Example 3:
Input: amount = 10, coins = [10] Output: 1
Note:
You can assume that
- 0 <= amount <= 5000
- 1 <= coin <= 5000
- the number of coins is less than 500
- the answer is guaranteed to fit into signed 32-bit integer
零钱兑换II。题意是给你一些不同面值的硬币coins和一个amount，请你返回有多少种硬币组合可以满足amount。
思路依然是动态规划。dp[i]的定义是当amount = i的时候，到底有几种硬币组合。
以基本情况没有硬币开始组合数量。dp[0] = 1，然后其余等于 0。
遍历所有硬币面值
- 对于每个硬币，我们将从金额 0 遍历到 amount：
- 对于每个 x，计算组合数：dp[x] += dp[x - coin]。
- 返回 dp[amount]
时间O(n^2)
空间O(n)
Java实现
1 class Solution {
2 public int change(int amount, int[] coins) {
3 int[] dp = new int[amount + 1];
4 dp[0] = 1;
5 for (int coin : coins) {
6 for (int x = coin; x < amount + 1; x++) {
7 dp[x] += dp[x - coin];
8 }
9 }
10 return dp[amount];
11 }
12 }
相关题目