题目大意：给你一些硬币的面值，问使用这些硬币（无限多块）能够组成amount的方法有多少种。
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.
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
Example 1:
|
1 2 3 4 5 6 7 |
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+1 |
Example 2:
|
1 2 3 |
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. |
Example 3:
|
1 2 |
Input: amount = 10, coins = [10] Output: 1 |
Idea: DP
Transition 1:
Let us use dp[i][j] to denote the number of ways to sum up to amount j using first i kind of coins.
dp[i][j] = dp[i – 1][j – coin] + dp[i – 1][j – 2* coin] + …
Time complexity: O(n*amount^2) TLE
Space complexity: O(n*amount) -> O(amount)
Transition 2:
Let us use dp[i] to denote the number of ways to sum up to amount i.
dp[i + coin] += dp[i]
Time complexity: O(n*amount)
Space complexity: O(amount)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 4 ms class Solution { public: int change(int amount, vector<int>& coins) { vector<int> dp(amount + 1, 0); dp[0] = 1; for (const int coin : coins) for (int i = 0; i <= amount - coin; ++i) dp[i + coin] += dp[i]; return dp[amount]; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 7 ms class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) for (int i = 0; i <= amount - coin; ++i) dp[i + coin] += dp[i]; return dp[amount]; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
""" Author: Huahua Running time: 107 ms (beats 100%) """ class Solution(object): def change(self, amount, coins): dp = [1] + [0] * (amount); for coin in coins: for i in xrange(amount - coin + 1): if dp[i]: dp[i + coin] += dp[i] return dp[amount] |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment