Dynamic Programming

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems, solving each subproblem once, and reusing the stored result.

Top-Down vs Bottom-Up

• Top-down (memoization)
  • Write the natural recursive solution
  • Store the result of each subproblem in a cache (hash map or array) and return it directly when the same state is seen again
  • Only the states that are actually reachable get computed
• Bottom-up (tabulation)
  • Solve the subproblems iteratively, in an order that guarantees every dependency is already computed
  • Fill a DP table or array; no recursion, so no stack overflow
  • Usually easier to optimize for space

Typical progression for any problem: brute-force recursion, then memoization, then tabulation, then space optimization.

How to Recognize DP

• The problem asks for a count, a minimum/maximum, or whether something is possible
• The brute force is a recursion that branches (take or skip, move right or down, match or mismatch)
• The same subproblems are solved repeatedly (overlapping subproblems)
• The optimal answer is built from optimal answers to smaller inputs (optimal substructure)

Recipe: State, Transition, Base Case

1. State: what is the smallest set of variables that fully describes a subproblem? Examples: an index i, a pair of indices (i, j), an index and a remaining capacity.
2. Transition: how does the answer for a state depend on smaller states? For example dp[i] = dp[i-1] + dp[i-2].
3. Base case: the states whose answer is known directly (empty input, out of bounds, capacity zero).
4. Order: the iteration order that computes dependencies first.
5. Answer: which state holds the final result (often the last one, but sometimes the best over all states).

Space Optimization

If a state only depends on the previous row (or the previous few values), keep just those instead of the whole table:

• 1D recurrences such as Fibonacci or House Robber need only a couple of variables: O(n) to O(1)
• 2D tables such as grid paths, LCS and knapsack need only the previous row: O(n * m) to O(m)
• In 0/1 knapsack with a single array, iterate capacity from high to low so an item is not used twice; in unbounded knapsack iterate from low to high so it can be reused

Patterns

Knapsack

• Two-dimensional DP: the subproblem tracks two variables, the item index and the remaining capacity (or target)
• For each item, compute two outcomes: include it or skip it, and take the best (or the sum, when counting)
• 0/1 knapsack: each item can be used at most once
• Unbounded knapsack: each item can be used any number of times
• Related problems include subset sum, partition, coin change and target sum

Longest Common Subsequence

• Two-dimensional DP: the subproblem needs one index per string (i1, i2)
• Recursive solution:
  • If out of bounds (base case), return 0
  • With memoization, if the state is cached, return cache[i1][i2]
  • If the characters at both indices are equal, return 1 + dfs(i1 + 1, i2 + 1)
  • Otherwise return max(dfs(i1 + 1, i2), dfs(i1, i2 + 1))
• Bottom-up mirrors the memoization:
  • Allocate a cache with an extra row and column, all initialized to 0
  • Iterate over both strings with two nested loops
  • If the characters are equal, cache[i + 1][j + 1] = 1 + cache[i][j]
  • Otherwise, cache[i + 1][j + 1] = max(cache[i][j + 1], cache[i + 1][j])
• The same table shape solves edit distance, distinct subsequences, interleaving string and shortest common supersequence

Palindromes

There is no dedicated template page, so the two standard approaches are described here.

Expand around center (O(n^2) time, O(1) space): every palindrome has a center, either a single character (odd length) or a gap between two characters (even length). Loop over each index i, and run two expansions, one starting with l, r = i, i and one with l, r = i, i + 1. While l >= 0, r < n and s[l] == s[r], the substring is a palindrome; move l left and r right. This fits longest palindromic substring and palindromic substrings (count every successful expansion).

def count_palindromes(s):
    res = 0
    for i in range(len(s)):
        for l, r in ((i, i), (i, i + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                res += 1
                l -= 1
                r += 1
    return res

Interval DP (O(n^2) time and space): let dp[l][r] describe the substring s[l..r]. A substring is a palindrome if s[l] == s[r] and the inside s[l+1..r-1] is a palindrome (or has length at most 2). For longest palindromic subsequence, dp[l][r] = dp[l+1][r-1] + 2 when the ends match, otherwise max(dp[l+1][r], dp[l][r-1]). Fill by increasing substring length (or l descending). Longest palindromic subsequence is also the LCS of s and its reverse.

Templates

• 1-Dimension DP: brute force, memoization and tabulation for Fibonacci-style recurrences such as climbing stairs and house robber
• 2-Dimension DP (Grid Paths): unique paths on a grid with row-based space optimization
• 0/1 Knapsack: each item used at most once
• Unbounded Knapsack: each item can be reused
• Longest Common Subsequence: two-string DP with brute force, memoization, tabulation and space optimization
• Pattern Catalogue: the full list of DP patterns with LeetCode problems

Related: Fibonacci (plain recursion and memoization of the same recurrence as 1-Dimension DP) and Kadane’s Algorithm.

Problems

For many more problems grouped by pattern (LIS, edit distance, state machine, digit DP, bitmask DP, and others), see the pattern catalogue.