← Back to TypeScript
Dynamic Programming
Overlapping subproblems and optimal substructure — count the paths, make the change, find the longest common thread. One small table beats a billion recursive calls.
Counting paths with a memo
advancedblankComplete the memoized staircase counter — the cache lookup, the cache write, and the table that holds them.
Challenge: make the change with fewest coins
advancedchallengeReturn the minimum number of coins that sums to an amount — bottom-up, one slot per cent.
Challenge: the longest common thread
advancedchallengeCompute the length of the longest common subsequence of two strings with the classic two-dimensional table.
Review: the change maker that settles for more
advancedreviewA greedy coin-change routine is optimal on the coins you see every day and quietly wrong everywhere else. Replace the heuristic with the optimum.