# 322. Coin Change

## Approach 1: Combinations

• Time: $O(|\texttt{coins}||\texttt{amount}|)$
• Space: $O(|\texttt{amount}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int coinChange(vector& coins, int amount) { // dp[i] := fewest # of coins to make up i vector dp(amount + 1, amount + 1); dp[0] = 0; for (const int coin : coins) for (int i = coin; i <= amount; ++i) dp[i] = min(dp[i], dp[i - coin] + 1); return dp[amount] == amount + 1 ? -1 : dp[amount]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int coinChange(int[] coins, int amount) { // dp[i] := fewest # of coins to make up i int[] dp = new int[amount + 1]; Arrays.fill(dp, 1, dp.length, amount + 1); for (final int coin : coins) for (int i = coin; i <= amount; ++i) dp[i] = Math.min(dp[i], dp[i - coin] + 1); return dp[amount] == amount + 1 ? -1 : dp[amount]; } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # dp[i] := fewest # Of coins to make up i dp = [0] + [amount + 1] * amount for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return -1 if dp[amount] == amount + 1 else dp[amount] 

## Approach 2: Permutations

• Time: $O(|\texttt{coins}||\texttt{amount}|)$
• Space: $O(|\texttt{amount}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: int coinChange(vector& coins, int amount) { // dp[i] := fewest # of coins to make up i vector dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; ++i) for (const int coin : coins) if (coin <= i) dp[i] = min(dp[i], dp[i - coin] + 1); return dp[amount] == amount + 1 ? -1 : dp[amount]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int coinChange(int[] coins, int amount) { // dp[i] := fewest # of coins to make up i int[] dp = new int[amount + 1]; Arrays.fill(dp, 1, dp.length, amount + 1); for (int i = 1; i <= amount; ++i) for (final int coin : coins) if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1); return dp[amount] == amount + 1 ? -1 : dp[amount]; } }