Coin Change Solver
AlgorithmsMediumCalculate the minimum coins needed or total ways to make change amounts.
Alt+Shift+C
Configuration Panel
Coin Change DP Table
Minimum Coins DP Grid:
DP table is empty.
Total Unique Ways DP Grid:
DP table is empty.
Time Complexity
O(N * amount)
Space Complexity
O(N * amount) / O(amount) optimized
Conceptual Overview
The Coin Change problem has two variations: Minimum Coins (find the fewest coins to make amount) and Number of Ways (find total unique combinations to make amount).
Recurrence Relation
dp[i][j] = min(dp[i-1][j], 1 + dp[i][j - coin]) for min coins; dp[i][j] = dp[i-1][j] + dp[i][j - coin] for total ways
State Transitions
For Min Coins: decides if taking coin i (1 + dp[i][j - coin]) is cheaper. For Ways: adds options using previous coins to options using coin i.
Source: CP-Algorithms dynamic programming reference