Algorithms · topic
Overlapping subproblems and optimal substructure, memoisation and tabulation; LCS, edit distance, 0/1 knapsack, subset sum, coin change counting and minimum coins, matrix-chain multiplication and longest increasing subsequence, each with its table, fill order and cost.
Dynamic programming (DP) solves an optimisation (or counting) problem by combining answers to smaller overlapping subproblems. Where plain recursion recomputes the same subproblem many times, DP stores each answer once and reuses it.
Three classical DP problems act on sequences: the longest common subsequence (LCS) of two strings, the edit distance (Levenshtein distance) between two strings, and the longest increasing subsequence (LIS) of one sequence.
Three classical DP problems share a tabular fill and a reconstruction step: the 0/1 knapsack problem (and its decision twin subset sum), and matrix-chain multiplication.3-4). Both need DP.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
