Leetcode

Coin Change 2

May 26, 2022 by aAshish

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

C++

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

JAVA

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

Python

 
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]