Dynamic Programming
Optimal substructure & memoization
Longest Common Subsequence
Finds the longest subsequence shared by two strings by building a 2-D table of subproblem answers.
Time O(m · n) · Space O(m · n)
0/1 Knapsack
Maximizes total value under a weight limit, deciding for each item whether to take it or leave it.
Time O(n · W) · Space O(n · W)
Edit Distance
Fewest single-character insertions, deletions or replacements to turn one string into another (Levenshtein).
Time O(m · n) · Space O(m · n)
Coin Change
Fewest coins that sum to a target amount, given unlimited supply of each denomination.
Time O(n · amount) · Space O(n · amount)
Fibonacci (Tabulation)
Builds the Fibonacci sequence bottom-up, each term being the sum of the two before it — no repeated work.
Time O(n) · Space O(n)
Kadane's Algorithm
Maximum subarray sum in one pass: extend the running sum while it helps, restart at the current element when it turns negative.
Time O(n) · Space O(1)
Longest Increasing Subsequence
Longest run of values that strictly increases (not necessarily contiguous), via dp[i] = best subsequence ending at i.
Time O(n²) · Space O(n)