Dynamic Programming Patterns

Convert exponential brute force recursions into polynomial time algorithms. Master state definition, transition recurrences, top-down memoization, and bottom-up tabulation.

The Two Pillars of Dynamic Programming

Dynamic Programming (DP) solves complex optimization problems by breaking them down into simpler overlapping subproblems. A problem is solvable via DP if and only if it satisfies two mathematical properties:

1. Optimal Substructure:An optimal solution to the overall problem contains within it optimal solutions to its subproblems (e.g. shortest path from A to C via B requires shortest path from A to B).
2. Overlapping Subproblems:The recursive call tree computes the exact same subproblem states repeatedly (e.g. Fibonacci fib(3) evaluated exponentially many times in naive recursion).
Top-Down Memoization vs Bottom-Up Tabulation:Top-down uses recursion with a cache dictionary/array; bottom-up iteratively fills an array in topological order of dependencies, enabling O(1) or O(W) rolling array space optimizations.

Define the State: Identify what minimal parameters uniquely define a subproblem (e.g. dp[i][w] = max value considering first i items with remaining capacity w).
Formulate the Recurrence Transition: Express the answer for state dp[i] in terms of previously computed states: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]).
Identify Base Cases & Traversal Order: Initialize boundary conditions (e.g. dp[0] = 0 or dp[0][w] = 0), and iterate from smallest subproblem to target state.
Optimize Space Complexity: If dp[i] only depends on dp[i-1], compress the 2D matrix into a 1D rolling array by traversing backwards from capacity down to weight[i].

Definition: State Transition Equation

The mathematical recurrence relation that expresses the optimal value of a current subproblem state as a function of the optimal values of smaller previously solved subproblem states.

0/1 Knapsack State Transition

dp[i][w] = max( dp[i-1][w], dp[i-1][w - wt[i]] + val[i] )

Variable Definitions & Term Breakdown:

dp[i-1][w]Choice 1: Do NOT include item i (inherit capacity w from previous item)

dp[i-1][w - wt[i]] + val[i]Choice 2: INCLUDE item i (consume weight wt[i] and gain val[i])

Core Dynamic Programming Pattern Taxonomy

DP Pattern	State Representation	Standard Transition	Typical Complexity
0/1 Knapsack	dp[w] = max value at cap w	dp[w] = max(dp[w], dp[w-wt] + val)	O(N × W)
Unbounded Knapsack	dp[w] = max value at cap w	Forward loop w: dp[w] = max(dp[w], dp[w-wt] + val)	O(N × W)
Longest Common Subsequence	dp[i][j] for str1[i], str2[j]	if s1[i]==s2[j]: 1 + dp[i-1][j-1] else max(dp[i-1][j], dp[i][j-1])	O(N × M)
Matrix Chain / Interval DP	dp[i][j] over range [i, j]	min/max over k in [i, j]: dp[i][k] + dp[k+1][j] + cost	O(N³)

Standard patterns, state representations, and time complexities

Tip

For 0/1 Knapsack (each item used at most once), iterate the capacity loop in REVERSE (`capacity` down to `wt`). For Unbounded Knapsack (items can be reused infinitely like Coin Change), iterate FORWARD (`wt` up to `capacity`).

Python0/1 Knapsack 1D Space-Optimized Implementation

1def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
2    dp = [0] * (capacity + 1)
3    
4    for wt, val in zip(weights, values):
5        # Traverse backwards to prevent using the same item multiple times
6        for w in range(capacity, wt - 1, -1):
7            dp[w] = max(dp[w], dp[w - wt] + val)
8            
9    return dp[capacity]
10 
11# Test Case
12weights = [2, 3, 4, 5]
13values  = [3, 4, 5, 6]
14capacity = 8
15print(f'Max Knapsack Value for Capacity {capacity}:', knapsack_01(weights, values, capacity))

Output

Max Knapsack Value for Capacity 8: 10

C++C++ Longest Increasing Subsequence O(N log N) via Patience Sorting

1#include <iostream>
2#include <vector>
3#include <algorithm>
4 
5int lengthOfLIS(std::vector<int>& nums) {
6    std::vector<int> tails;
7    for (int x : nums) {
8        auto it = std::lower_bound(tails.begin(), tails.end(), x);
9        if (it == tails.end()) tails.push_back(x);
10        else *it = x;
11    }
12    return tails.size();
13}
14 
15int main() {
16    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
17    std::cout << "LIS Length: " << lengthOfLIS(nums) << "\n";
18    return 0;
19}

Output

LIS Length: 4

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
0/1 Knapsack (1D)	`for wt, val in items: for w in range(cap, wt - 1, -1): dp[w] = max(dp[w], dp[w - wt] + val)`
Unbounded Knapsack (1D)	`for wt, val in items: for w in range(wt, cap + 1): dp[w] = max(dp[w], dp[w - wt] + val)`
LCS Transition	`dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1] else max(dp[i-1][j], dp[i][j-1])`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Iterating forwards in 0/1 Knapsack 1D compression

Why it happens: Iterating forwards allows the current item to be included multiple times in the same step, turning 0/1 knapsack into unbounded knapsack.

Correction: Always loop backwards: `for w in range(capacity, wt - 1, -1)`.

# Correct 0/1 reverse loop:
for w in range(capacity, wt - 1, -1):
    dp[w] = max(dp[w], dp[w - wt] + val)

Frequently Asked Questions

Is 0/1 Knapsack solvable in polynomial time?

No. 0/1 Knapsack is NP-Complete. The O(N × W) DP solution is Pseudo-Polynomial time because W is the numeric value of the capacity, which requires O(log W) bits to represent. If W is exponential in input size, DP runtime explodes.