MEDIUM NC#114 Dynamic Programming 1D

518. Coin Change II

📖 Problem

Given an array of coins of different denominations and a target amount, return the number of combinations that make up that amount (different order counts as same combination).

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Array DP table updates
  • •State transition thinking
  • •Base case initialization

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Dynamic Programming reasoning pattern
  • •Apply Recursion reasoning pattern

💡 Approach

  • → dp[i] = number of ways to make amount i
  • → Process coins one at a time to avoid counting permutations
  • → dp[i] += dp[i - coin]
  • → Time: O(n * amount), Space: O(amount)

🧭 Prerequisites

#300 Longest Increasing Subsequence #322 Coin Change

🛠️ Hints & Pitfalls

Hints

  • •dp[i] = number of ways to make amount i
  • •Process coins one at a time to avoid counting permutations
  • •dp[i] += dp[i - coin]

Common Pitfalls

  • •Time: O(n * amount), Space: O(amount)

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
change(5, [1,2,5]);
Expected:
4
Test Case 2
Not run
Input:
change(3, [2]);
Expected:
0
Test Case 3
Not run
Input:
change(10, [10]);
Expected:
1

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#91 Decode Ways #139 Word Break #152 Maximum Product Subarray #198 House Robber #213 House Robber II
⌘K Search ⌘↩ Run ⌘S Submit