Leetcode Problem 518. Coin Change II

518. Coin Change II

Leetcode Solutions

Dynamic Programming with Space Optimization

  1. Initialize a 1D array dp of size amount + 1 and set dp[0] = 1 (base case: there's one way to make up amount 0).
  2. Iterate over each coin in coins.
  3. For each coin, iterate over all amounts from the coin's value up to amount.
  4. For each amount j, update dp[j] by adding dp[j - coin] to it. This represents using the current coin to make up the amount j.
  5. After processing all coins, return dp[amount] which contains the number of combinations to make up the desired amount.
UML Thumbnail

Top-Down Dynamic Programming (Memoization)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...