Advanced · Module 15
Dynamic programming
Solve each subproblem once and reuse it: memoization, tables and reconstructing answers.
Dynamic programming solves problems whose subproblems repeat, by solving each one once and reusing its answer. This module builds the method step by step: caching a recursion, filling a table in dependency order, the common shapes of one- and two-dimensional problems, knapsack and its many disguises, and finally recovering the actual solution and fitting large tables into small memory.
- 1MemoizationPro — members onlyWhen a recursion solves the same subproblem many times, store each answer the first time and look it up after that. The cost becomes the number of distinct subproblems times the work for each.14 min
- 2Bottom-up tablesPro — members onlyInstead of recursing and caching, fill an array of answers in an order where every value a cell needs has already been computed. No recursion, no lookups, and the structure of the table becomes visible.14 min
- 3One-dimensional problemsPro — members onlyMany problems over a sequence have a DP with one cell per position: the best answer for the prefix ending there. Take-or-skip, counting the ways, and best-ending-here cover most of them.15 min
- 4Grids and stringsPro — members onlyTwo-dimensional DP fills a table whose cells depend on their neighbors above and to the left. On grids it counts or optimizes paths; on two strings, a cell compares two prefixes, which is how diff tools, spell checkers and DNA alignment work.15 min
- 5Knapsack and subsetsPro — members onlyChoosing a subset of items under a capacity is solved with a table over items and capacities. Whether each item can be used once or many times comes down to the direction of one loop.15 min
- 6Rebuilding the answer and saving memoryPro — members onlyA DP table holds the value of the best solution, not the solution itself. Walking back through the table recovers the choices. When only the value is needed, keeping one or two rows cuts memory from O(n × m) to O(m).14 min