LeetCode Solutions
518. Coin Change II
Time: $O(|\texttt{coins}| \cdot \texttt{amount})$
Space: $O(\texttt{amount})$
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (const int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
return dp[amount];
}
};
|
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (final int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
return dp[amount];
}
}
|
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
|