Introduction

Dynamic Programming (DP) solves a problem by breaking it into overlapping subproblems, solving each subproblem exactly once, and reusing the stored answer instead of recomputing it — turning an exponential tree of repeated recursive calls into a linear or polynomial table of unique states.

Recognize the pattern

• The problem asks for an optimal value (max/min/count) built from choices over a sequence, set, or grid (e.g., "maximum value we can fit", "minimum edits", "number of ways").
• A greedy local choice provably fails because taking or skipping an item now changes what is optimal later — the decision has to be weighed against future consequences.
• A brute-force recursive solution, when you draw its call tree, revisits the same (index, remaining-capacity) pair many times.
• The problem has optimal substructure (best answer for a state is built from best answers of smaller states) and overlapping subproblems (those smaller states repeat).

Running example: 0/1 Knapsack

Given item weights/values and a capacity, choose a subset of items (each item taken 0 or 1 times) to maximize total value without exceeding capacity. At each item you make one binary decision: skip it, or take it (if it fits) and recurse on the remaining capacity.

Brute force (recursion on all subsets)

int knapsackRec(int i, int cap, int[] wt, int[] val) {
    if (i == wt.length || cap == 0) return 0;
    int skip = knapsackRec(i + 1, cap, wt, val);
    int take = 0;
    if (wt[i] <= cap) {
        take = val[i] + knapsackRec(i + 1, cap - wt[i], wt, val);
    }
    return Math.max(skip, take);
}

Cost: at every index there are 2 branches, so the call tree has up to 2^n leaves — O(2^n) time, O(n) space (recursion stack). Most of those branches recompute the identical (index, capacity) pair.

Optimal: memoize, then tabulate

Cache each unique (i, cap) state the first time it's solved; every later call to the same state is O(1). That collapses the exponential tree down to the number of distinct states.

int knapsackMemo(int i, int cap, int[] wt, int[] val, Integer[][] memo) {
    if (i == wt.length || cap == 0) return 0;
    if (memo[i][cap] != null) return memo[i][cap];
    int skip = knapsackMemo(i + 1, cap, wt, val, memo);
    int take = 0;
    if (wt[i] <= cap) {
        take = val[i] + knapsackMemo(i + 1, cap - wt[i], wt, val, memo);
    }
    return memo[i][cap] = Math.max(skip, take);
}

// Bottom-up, same recurrence, no recursion:
int knapsackTab(int[] wt, int[] val, int capacity) {
    int n = wt.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = n - 1; i >= 0; i--) {
        for (int cap = 0; cap <= capacity; cap++) {
            int skip = dp[i + 1][cap];
            int take = (wt[i] <= cap) ? val[i] + dp[i + 1][cap - wt[i]] : 0;
            dp[i][cap] = Math.max(skip, take);
        }
    }
    return dp[0][capacity];
}

Complexity, derived

The recursion is defined by T(i, cap) = T(i+1, cap) + T(i+1, cap-wt[i]). Without memoization this recurrence unrolls into a binary tree of depth n, giving T(n) = 2·T(n-1) → O(2^n) calls. With memoization, the number of distinct states is bounded by the grid of (index, capacity) pairs: n choices of index × (capacity+1) choices of remaining capacity = O(n·capacity) states, each solved in O(1) work once cached → O(n·capacity) time. Space is O(n·capacity) for the table (recursion adds O(n) stack for the memoized version); the tabulated version can be compressed to O(capacity) by keeping only the current and next row, since row i only depends on row i+1.

Traced example

Items, 0-indexed as (weight, value): item0=(1,1), item1=(3,4), item2=(4,5), item3=(5,7); capacity = 7. dp[i][cap] means "best value achievable using items i..3 within capacity cap", so row 4 is the empty-suffix base case and row 0 (the final answer) is filled last, from the bottom up.

Two cells worth checking by hand, since row 0 is where mistakes hide: dp[0][3] = max(skip = dp[1][3] = 4, take = val[0] + dp[1][3-1] = 1 + dp[1][2]). dp[1][2] is 0 (item1 alone doesn't fit in capacity 2), so take = 1, and dp[0][3] = max(4, 1) = 4. Likewise dp[0][4] = max(skip = dp[1][4] = 5, take = 1 + dp[1][3] = 1 + 4 = 5) = 5. Both match the recurrence exactly — row 0 is (0, 4, 5, 9).

Reading dp[0][7] = 9: it comes from the skip branch at item0 — dp[0][7] = dp[1][7] = 9, meaning item0 is left out entirely. One level down, dp[1][7] = 9 comes from the take branch at item1 — val[1] + dp[2][7-3] = 4 + dp[2][4] = 4 + 5 = 9. And dp[2][4] = 5 comes from the take branch at item2 — val[2] + dp[3][0] = 5 + 0 = 5. Walking those choices back up gives the concrete optimal set: item1(3,4) + item2(4,5) = weight 7, value 9 — an exact fit at capacity 7, and the true optimum (any set including item0 or item3 either exceeds 7 or scores lower, e.g. item0+item1+item2 has weight 8 and doesn't fit).

Pitfalls

• Forgetting the base cases (i == n or cap == 0) causes array-index-out-of-bounds or infinite recursion.
• Iterating the capacity loop in the wrong direction for the space-optimized 1-D array turns 0/1 knapsack into unbounded knapsack (an item gets reused) — for 0/1 you must iterate capacity descending when using a single row.
• Using a HashMap for memo keys when a simple 2-D array would do adds constant-factor overhead and hides the state space size.
• Assuming memoized recursion and tabulation always have identical complexity — memoization only pays for states actually reached, tabulation fills the whole table even for unreachable states.

When to use / when not

Use DP when the problem has optimal substructure + overlapping subproblems and the state space (here, index × capacity) is small enough to enumerate — polynomial, not exponential, in the input size. Avoid it when: (a) a greedy choice is provably optimal (e.g., fractional knapsack — sort by value/weight ratio, no need for a table, O(n log n) beats O(n·capacity)); (b) capacity or another state dimension is astronomically large (pseudo-polynomial O(n·capacity) blows up when capacity ~10^9), in which case branch-and-bound or approximation algorithms are preferred — and if instead the item count is tiny (n ≤ ~40) while capacity is astronomical, meet-in-the-middle (split the items in half, enumerate all 2^(n/2) subset sums of each half, then two-pointer/binary-search to combine) runs in O(2^(n/2)) and sidesteps the capacity dimension entirely; (c) subproblems don't actually overlap, in which case plain divide-and-conquer is simpler and needs no memo table.

Takeaways

• DP = recursion + caching of overlapping states; identify the state (here, (index, remaining capacity)) before writing any code.
• Derive complexity from the state-space size, not memorized formulas: O(states × work-per-state).
• Memoization (top-down) and tabulation (bottom-up) solve the identical recurrence; tabulation enables space compression, memoization only computes reachable states.
• 0/1 knapsack is pseudo-polynomial — its runtime depends on the numeric value of capacity, not just n, so it can still be slow for large weights.

Recall: Why does the 1-D space-optimized 0/1 knapsack array require iterating the capacity dimension from high to low, and what breaks if you go low to high?

Synthesized from the classic 0/1 Knapsack DP pattern; complexity and transition derivations are original to this page.