V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Coin Change

Build the minimum number of reusable coins for every amount and reconstruct one optimal combination.

Core idea

For each amount, try appending every coin to a solved smaller amount. The minimum reachable candidate becomes the state value, and a predecessor coin can reconstruct one solution.

Read the visualization

The amount row grows from zero toward the target. Candidate arrows point back by one coin value, while unreachable cells remain infinite until a valid predecessor appears.

012345
∅100000
1
2
5

Set amount zero to zero coins and every positive amount to unreachable.

1function change(amount: number, coins: number[]): number {
2 const m = coins.length;
3 const dp = Array.from({ length: m + 1 },
4 () => Array(amount + 1).fill(0));
5 dp[0][0] = 1; // init 0 item init 1 init: init not selected
6 for (let i = 1; i <= m; i++) {
7 const c = coins[i - 1];
8 for (let a = 0; a <= amount; a++) {
9 dp[i][a] = dp[i - 1][a]; // unused number i skip coin
10 if (a >= c) dp[i][a] += dp[i][a - c]; // use one coin ( current row, add)
11 }
12 }
13 return dp[m][amount];
14}
coin1,2,5
amount5
1 / 20

Complexity and tradeoffs

Time: O(nA). Space: O(A). The amount A defines the pseudo-polynomial state space; unreachable states remain infinite.

Invariant: When amount a is finalized, every transition into it comes from a smaller amount whose minimum coin count is already correct.

Where it fits

The same unbounded DP pattern handles denominations, minimum pieces, and repeated actions. Counting combinations instead of minimizing changes the state meaning and loop order.