Wing
Dynamic Programming
Fibonacci (Memoized)
Richard Bellman, 1952
Computes Fibonacci numbers efficiently by caching previously computed results to avoid redundant work.
Longest Common Subsequence
Various (Bellman era), 1953
Finds the longest subsequence common to two sequences by filling a 2D table and tracing back through matches.
Rod Cutting
Richard Bellman, 1954
Maximizes revenue from cutting a rod into integer lengths using a price table and a one-dimensional Bellman equation.
Weighted Interval Scheduling
Folklore (CLRS style), 1955
Dynamic program over timelines that picks a maximum-weight feasible subset by scanning finish-sorted intervals and referencing disjoint predecessors.
0/1 Knapsack Problem
George Dantzig, 1957
Determines the most valuable combination of items that fits within a weight limit using a dynamic programming table.
Longest Increasing Subsequence
Craige Schensted (tableaux) / classical LIS, 1961
Computes the length of the longest strictly increasing subsequence with an O(n²) dynamic programming scan over endings.
Bitmask DP (Tiny TSP)
Michael Held & Richard Karp, 1962
Runs Held–Karp-style subset dynamic programming on four cities, filling dp[mask][j] in increasing subset size.
Edit Distance (Levenshtein)
Vladimir Levenshtein, 1965
Computes the minimum number of insertions, deletions, and substitutions needed to transform one string into another.
Viterbi Algorithm
Andrew Viterbi, 1967
Dynamic programming on a hidden Markov model to find the most likely state sequence.
Matrix Chain Multiplication
T.C. Hu & M.T. Shing, 1968
Determines the optimal order to multiply a chain of matrices, minimizing the total number of scalar multiplications.
Smith–Waterman
Temple F. Smith & Michael S. Waterman, 1981
Local pairwise alignment via DP with scores reset at zero — finds best matching substring.
Maximum Subarray (Kadane)
Jay Kadane, 1984
Scans once while remembering the optimum subarray ending at each index by comparing extending versus restarting at the newest value.