Begin Algo
Algorithms · 11 lessons

Dynamic ProgrammingOverlapping subproblems, remembered

DP rests on two things: subproblems recur, and the best answer to the whole is built from best answers to the parts. Start with memoisation, learn to define a state, write the transition and pick an order — then work through the common state designs: knapsack, sequences, grids, intervals, bitmasks and trees.

Why learn Dynamic Programming

Where it shows up
Spell check and autocorrect

How far apart are "teh" and "the"? Edit distance counts the fewest changes, and it is behind both input methods and "did you mean".

→ Lesson: Edit Distance
git diff

Which lines are unchanged, which were added or removed — that is the longest common subsequence.

→ Lesson: LCS
Budgets and resource allocation

A fixed budget, each option with a cost and a payoff, and you want the best combination. That is the knapsack problem, and cloud capacity planning is the same question.

→ Lesson: 0/1 Knapsack
Why plain recursion is not enough

Naive Fibonacci recomputes the same subproblem millions of times. Remember the answers and exponential time becomes linear — that is where DP starts.

→ Lesson: Memoization & Tabulation

Lessons

11 lessons
#AlgorithmDifficulty
01Memoization & Tabulation Memoisation and tabulationFibonacci and Climbing Stairs, top-down and bottom-upUsed for: Any recursion with overlapping subproblems — add a cache first021-D DP One-dimensional DPHouse Robber, Decode Ways — the state depends only on the last fewUsed for: Sequential decisions, simple scheduling and counting030/1 Knapsack 0/1 knapsackTake each item or do not; the 2D table and its space-compressed formUsed for: Budget allocation, portfolios, container loading04Unbounded Knapsack Unbounded knapsackItems can be reused — the DP behind Coin ChangeUsed for: Fewest coins for an amount, purchasing from unlimited supply05LIS Longest increasing subsequenceThe O(n²) DP and the O(n log n) patience-sorting versionUsed for: Stock trend analysis, the Russian doll envelopes problem06LCS Longest common subsequenceA 2D table; on a match, take the diagonal plus oneUsed for: diff tools, DNA alignment, plagiarism comparison07Edit Distance Edit distanceThe fewest inserts, deletes and substitutionsUsed for: Spell correction, fuzzy search, scoring speech recognition08Grid DP Paths on a gridUnique Paths and Min Path Sum, moving only right or downUsed for: Counting robot routes, seam carving in images09Interval DP Interval DPBurst Balloons and matrix chain multiplication — enumerate the split pointUsed for: Optimal parenthesisation, polygon triangulation10Bitmask DP Bitmask DPUse the bits of an integer to represent a set as the stateUsed for: TSP, small assignment problems11Tree DP DP on treesPost-order traversal, combining subtree answers into the parent'sUsed for: Tree diameter, maximum path sum, independent set on a tree