Leetcode

Coin Change

May 26, 2022 by aAshish

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