## Approach 1: Combinations

• Time:O(|\texttt{coins}||\texttt{amount}|)
• Space:O(|\texttt{amount}|)

## C++

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] := fewest # of coins to make up i
vector<int> 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];
}
};
``````

## JAVA

``````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];
}
}
``````

## Python

``````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}|)

## C++

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] := fewest # of coins to make up i
vector<int> 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];
}
};
``````

## JAVA

``````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];
}
}
``````