# 518. Coin Change 2

• Time: $O(|\texttt{coins}| \cdot \texttt{amount})$
• Space: $O(\texttt{amount})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public: int change(int amount, vector& coins) { vector 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]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 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]; } } 
 1 2 3 4 5 6 7 8 9 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]