Dynamic Programming

01 · why it exists

Why this exists, and the weight it carries

since1952–57

Richard Bellman (RAND Corporation)

Richard Bellman studied multistage decision problems at the RAND Corporation; his 1952 PNAS paper is titled "On the Theory of Dynamic Programming", and his 1957 book Dynamic Programming spread the method. In his 1984 autobiography he recalled choosing the name to shield the work: the Secretary of Defense, Wilson, had "a pathological fear and hatred of the word, research", while "dynamic" was a word even a Congressman couldn't object to. The dates don't quite fit — Charles Wilson took office in January 1953, after the 1952 paper already used the name — so read it as Bellman's own recollection.

the problem it solvedMultistage decisions — choosing a sequence of actions over time — where trying every sequence is hopeless, but each stage depends only on the state you are in.

its jobs today

Routing: Bellman–Ford and Floyd–Warshall compute shortest paths as DP over "paths with at most k edges" or "through the first k vertices".
Text tools: spell-check suggestions rank words by edit distance, a two-sequence DP table; diff solves the same table's longest-common-subsequence problem with faster, specialised algorithms.
Speech and text recognition: the Viterbi algorithm, a DP over time steps, picks the most likely sequence of hidden states.

the weight it carries

Illustrative: Climbing Stairs for n = 45. Plain recursion makes 2·F(46) − 1 = 2 × 1,836,311,903 − 1 = 3,672,623,805 calls (≈ 3.7 billion). The two-variable DP does 44 additions.

without it

Every "best way" or "how many ways" question with a choice at each step — routes, edits, budgets — would stay exponential: 45 stairs already needs billions of calls.

when · why · how

when: A problem asks for a count, a best value or a yes/no over a sequence of choices, and the brute-force recursion repeats the same arguments.
why: Time becomes states × work per state (Climbing Stairs: O(2ⁿ) → O(n)). You pay memory for the table — often squeezable to one row or two variables.
how: Write the recursion, then cache it in an int[]/long[] filled with −1 (top-down), or fill dp[0..n] with a loop from the base cases up (bottom-up). Memoization's own story (Michie, 1968) is in the Recursion chapter.

since?

Bottom-up tables and rolling rows

Filling a table from the smallest subproblem up, and keeping only the rows you still read, is programming folklore with no single inventor. Its top-down twin, memoization, does have a clear origin — Donald Michie's 1968 "memo" functions, covered in the Recursion chapter.

its jobs today

No StackOverflowError: a loop over dp[0..n] handles n = 10⁶, where a memoized recursion 10⁶ calls deep would overflow Java's default thread stack.
Fitting in memory: two rolling rows let an O(m·n) string comparison run in O(min(m, n)) memory.
Interview follow-ups: "can you do it in O(1) space?" is answered by keeping just the last one or two values.

the weight it carries

Illustrative: LCS of two 10⁵-character strings. Full table: (10⁵)² = 10¹⁰ ints × 4 bytes = 40 GB. Two rows: 2 × (10⁵ + 1) ints × 4 bytes ≈ 800 KB. Both still take about 10¹⁰ steps.

without it

Deep inputs crash recursive solutions, and 2D tables for long strings don't fit in RAM.

when · why · how

when: The recursion would go deeper than ~10⁴ calls, the interviewer asks for less memory, or almost every state will be needed anyway.
why: No call stack, and an explicit fill order tells you exactly which cells are still read — so O(n) space can drop to O(1) and O(m·n) to O(n). The cost: you compute every state, even ones a memo would never reach.
how: new int[n + 1] (or [m + 1][n + 1]), set the base cases, loop so every cell you read is already filled; then replace the table with prev/cur rows or two variables.

since1956–57

0/1 and unbounded knapsack

G. B. Mathews (1890s); Richard Bellman & Stuart Dreyfus; George Dantzig; Richard Karp (1972)

The puzzle is old: its history is usually traced back to G. B. Mathews' paper "On the Partition of Numbers" (1896–97). In 1956 Bellman and Stuart Dreyfus wrote a RAND memo solving a cargo-loading problem — items that can't be split — with dynamic programming, and Dantzig's 1957 paper on discrete-variable problems includes a DP example too. In 1972 Richard Karp listed knapsack among his 21 NP-complete problems — which is why nobody expects a truly polynomial algorithm, and the DP stays "pseudo-polynomial".

the problem it solvedChoosing the most valuable set of indivisible items under a weight or budget limit, without trying all 2ⁿ subsets.

its jobs today

Budgeting: pick projects, ad slots or batch jobs whose total cost fits a fixed budget with the most value.
Exact-sum checks: can some of these invoices or refunds add up to exactly this amount? Partition Equal Subset Sum is this question.
Change-making: fewest coins or notes for an amount (Coin Change), and counting the ways to pay it (Coin Change II).

the weight it carries

Illustrative: 40 items, capacity 1,000. Trying every subset: 2⁴⁰ ≈ 1.1 × 10¹² subsets. The DP table: 40 × 1,001 = 40,040 cells, O(1) each.

without it

Every "choose under a limit" question would mean trying all 2ⁿ subsets — 30 items is already 2³⁰ ≈ 10⁹ of them.

when · why · how

when: Items with a weight or cost, a capacity or target, each item taken at most once (0/1) or any number of times (unbounded).
why: O(n·W) instead of O(2ⁿ) — but W is a value, so W = 10⁹ is hopeless (pseudo-polynomial).
how: int[] dp = new int[W + 1]; for each item, loop c from W down to its weight (0/1) or up from its weight (unbounded): dp[c] = Math.max(dp[c], dp[c - w] + v).

since1965–76

Two-string DP: edit distance and LCS

Vladimir Levenshtein; Robert Wagner & Michael Fischer; James Hunt & Douglas McIlroy

In 1965 Vladimir Levenshtein, working on error-correcting codes, measured the distance between strings by insertions, deletions and substitutions. In 1974 Wagner and Fischer published the table method used here: fill dp[i][j] for every pair of prefixes. In a 1976 Bell Labs report, Hunt and McIlroy described the algorithm inside Unix diff, which finds a longest common subsequence of lines. Biologists reached the same table idea for proteins in 1970 (Needleman–Wunsch).

the problem it solvedMeasuring how different two sequences are — words, lines of code, DNA — in O(m·n) instead of trying every alignment.

its jobs today

Spell checkers and search: suggest the dictionary words with the smallest edit distance to what you typed.
Code review: Unix diff is built on longest common subsequence; git diff defaults to Myers' algorithm, a faster relative of the same idea.
Bioinformatics: aligning DNA and protein sequences (Needleman–Wunsch).

the weight it carries

Illustrative: two 1,000-line files. The table has 1,001 × 1,001 ≈ 10⁶ cells, each O(1) — about a million cheap steps. Plain recursion branches up to 3 ways per call over a depth of up to 2,000.

without it

No "did you mean", no line-by-line diffs in code review, no DNA alignment at scale.

when · why · how

when: Two strings or sequences: convert one into the other, align them, compare them, or find what they share.
why: One cell per pair of prefixes → O(m·n) time. Each cell reads only ↖ ↑ ←, so two rows (or one row + a diag variable) give O(min(m, n)) memory.
how: int[][] dp = new int[m + 1][n + 1]; row 0 and column 0 are the empty prefix; compare a.charAt(i - 1) with b.charAt(j - 1).

since1960–75

Longest increasing subsequence (patience sorting)

Colin Mallows (patience sorting); Michael Fredman (the n log n bound)

A card game gives LIS a fast algorithm: deal each card onto the leftmost pile whose top card is not smaller; the number of piles is the LIS length. As Aldous and Diaconis tell it, the name patience sorting comes from Colin Mallows, whose 1960 analysis was published only in 1973; in a 1963 note Mallows credited A. S. C. Ross with inventing the game. In 1975 Michael Fredman showed the binary-search version needs about n log n comparisons in the worst case, and that no comparison method does better.

the problem it solvedFinding the longest increasing run (gaps allowed) in O(n log n) instead of O(n²).

its jobs today

Fewest moves to sort: the LIS can stay put and the other n − LIS items must move — e.g. reordering a list in a UI with the fewest drags.
Nesting and chains: boxes in boxes, envelopes, version chains — sort by one key, then run LIS on the other.

the weight it carries

Illustrative: n = 10⁵ prices. The O(n²) DP: about n²/2 = 5 × 10⁹ comparisons. Patience + binary search: n × ⌈log₂ n⌉ = 10⁵ × 17 = 1.7 × 10⁶.

without it

LIS on large inputs would be quadratic — 10⁵ items already need billions of steps.

when · why · how

when: Longest strictly increasing subsequence, chains, nesting, or "fewest elements to remove so the rest is sorted".
why: O(n log n), because tails stays sorted and each element needs one binary search. The O(n²) DP is easier to explain and can rebuild the sequence itself.
how: int[] tails plus a hand-written lower-bound binary search over [0, size); size is the answer.

02 · plain english

The idea in 30 seconds

Many recursive solutions ask the same small question again and again. Fibonacci(40) calls fib(2) over 60 million times.

DP = recursion + a notebook: the first time you solve a subproblem, write the answer down; every later time, just read it.

Once you can say "the answer for n is built from the answers for smaller n", you can fill a table from small to big — no recursion needed.

picture this

An Excel sheet where cell B7 is =B5+B6. Excel doesn't re-add the whole column every time you look at B7: every cell already holds its value, and a new cell only reads cells that are finished. A DP table is that sheet — one cell per small question, each filled once, each built from cells above it or to its left.

03 · remember

What you must know

DP applies when a problem has overlapping subproblems (the same sub-question repeats) and optimal substructure (the best answer is built from best answers to sub-questions).
The ladder: plain recursion (exponential) → memoization / top-down (cache results) → tabulation / bottom-up (fill a table in order) → space optimisation (keep only the rows you still read).
The 5-step recipe: 1) state — what does dp[i] (or dp[i][j]) mean in one sentence; 2) transition — how it's built from smaller states; 3) base cases; 4) order — fill so every state you read is already done; 5) answer — which cell holds it.
Time ≈ number of states × work per state. Fibonacci: n states × O(1). LCS: m·n states × O(1). LIS: n states × O(n) = O(n²).
0/1 knapsack (each item once) loops capacity downward in a 1D array; unbounded (reuse allowed) loops upward. That single loop direction is the whole difference.
Two-string DP (LCS, edit distance): dp[i][j] = answer for the first i chars of one and the first j chars of the other. Compare the last characters and look at the 3 neighbours: ↖, ↑, ←.
Grid DP: dp[r][c] from the cell above and the cell to the left (and sometimes up-left). Edges have only one neighbour — they are your base cases.
Interval DP (palindromes, burst balloons): dp[i][j] for a range, filled from short intervals to long ones. Often O(n³).
Counting problems use +, optimisation problems use min/max, feasibility problems use ||. The skeleton is the same.
If dp[i] only reads dp[i-1] and dp[i-2], you only need two variables. If a 2D row only reads the previous row, you only need one or two rows.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Why plain recursion explodes

The same fib(k) is computed again and again (red). The counter shows how often each value is recomputed.

loading simulation…

javajava.util.*

1class FibRecursive {2    /** Plain recursion: correct, but recomputes the same fib(k) again and again. */3    static long fib(int n) {4        if (n <= 1) return n;5        return fib(n - 1) + fib(n - 2);6    }7}

sim

Memoization collapses the tree

Same recursion, plus a notebook. Repeated calls become instant memo hits (green leaves) — whole subtrees disappear.

loading simulation…

javajava.util.*

1class FibMemoMap {2    private final Map<Integer, Long> memo = new HashMap<>();3 4    /** Top-down: the same recursion, but every answer is saved the first time it is computed. */5    long fib(int n) {6        if (n <= 1) return n;7        Long cached = memo.get(n);8        if (cached != null) return cached;9        long result = fib(n - 1) + fib(n - 2);10        memo.put(n, result);11        return result;12    }13}

sim

Bottom-up: a 1D table

No recursion at all: fill dp[1], dp[2], … left to right. Each new cell reads two finished cells.

loading simulation…

java

1class Solution {2    public int climbStairs(int n) {3        if (n <= 2) return n;4        int[] dp = new int[n + 1]; // dp[i] = ways to reach step i5        dp[1] = 1;6        dp[2] = 2;7        for (int i = 3; i <= n; i++) {8            dp[i] = dp[i - 1] + dp[i - 2];9        }10        return dp[n];11    }12}

sim

Squeeze the table into two variables

Same answers, but only prev2 and prev1 live in memory. Faded cells are values nobody will read again.

loading simulation…

java

1class Solution {2    public int climbStairs(int n) {3        int prev2 = 1, prev1 = 1; // ways(0), ways(1)4        for (int i = 2; i <= n; i++) {5            int cur = prev1 + prev2; // last move: 1 step or 2 steps6            prev2 = prev1;7            prev1 = cur;8        }9        return prev1;10    }11}

sim

Grid DP as a 3D landscape

Each tile's height is its path count. Watch the landscape rise toward the goal corner. Orbit with the mouse.

loading simulation…

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        int[][] dp = new int[m][n]; // dp[r][c] = paths that reach (r, c)4        for (int r = 0; r < m; r++) {5            for (int c = 0; c < n; c++) {6                if (r == 0 || c == 0) dp[r][c] = 1; // edges: only one way in7                else dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above + from left8            }9        }10        return dp[m - 1][n - 1];11    }12}

sim

Min Path Sum: build, then trace back

Each cell takes the cheaper of above/left. At the end, walking back along cheaper neighbours reveals the path.

loading simulation…

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        int m = grid.length, n = grid[0].length;4        int[][] dp = new int[m][n]; // dp[r][c] = cheapest sum to reach (r, c)5        for (int r = 0; r < m; r++) {6            for (int c = 0; c < n; c++) {7                if (r == 0 && c == 0) dp[r][c] = grid[0][0];8                else if (r == 0) dp[r][c] = dp[r][c - 1] + grid[r][c]; // top row: only from the left9                else if (c == 0) dp[r][c] = dp[r - 1][c] + grid[r][c]; // left column: only from above10                else dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);11            }12        }13        return dp[m - 1][n - 1];14    }15}

sim

0/1 Knapsack table

Row i allows items 0..i−1. Every cell compares "skip" (straight above) with "take" (above, shifted left by the weight).

loading simulation…

javajava.util.*

1class Knapsack01 {2    /** dp[i][c] = best value using only the first i items with capacity c. */3    static int knapsack(int[] wt, int[] val, int cap) {4        int n = wt.length;5        int[][] dp = new int[n + 1][cap + 1]; // row 0 = no items = value 06        for (int i = 1; i <= n; i++) {7            for (int c = 0; c <= cap; c++) {8                dp[i][c] = dp[i - 1][c]; // option 1: skip item i9                if (wt[i - 1] <= c) {10                    // option 2: take item i once, so look at the row ABOVE11                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - wt[i - 1]] + val[i - 1]);12                }13            }14        }15        return dp[n][cap];16    }17}

sim

LCS table with arrows

↖ = characters match (extend the diagonal). ↑ / ← = drop a character from one string. Follow the arrows back to read the LCS.

loading simulation…

javajava.util.*

1class Solution {2    public int longestCommonSubsequence(String text1, String text2) {3        int m = text1.length(), n = text2.length();4        int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = LCS of first i chars and first j chars5        for (int i = 1; i <= m; i++) {6            for (int j = 1; j <= n; j++) {7                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {8                    dp[i][j] = dp[i - 1][j - 1] + 1; // match: extend the diagonal9                } else {10                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop a char from one side11                }12            }13        }14        return dp[m][n];15    }16}

sim

Edit Distance table

Each cell = cheapest of replace (↖), delete (↑), insert (←), or free when the characters match.

loading simulation…

javajava.util.*

1class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length(), n = word2.length();4        int[][] dp = new int[m + 1][n + 1];5        for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all i chars6        for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all j chars7        for (int i = 1; i <= m; i++) {8            for (int j = 1; j <= n; j++) {9                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {10                    dp[i][j] = dp[i - 1][j - 1]; // same char: free11                } else {12                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // replace13                            Math.min(dp[i - 1][j],             // delete14                                     dp[i][j - 1]));           // insert15                }16            }17        }18        return dp[m][n];19    }20}

sim

LIS in O(n²)

dp[i] = longest increasing run that ENDS at i. Each i looks back at every smaller earlier number.

loading simulation…

javajava.util.*

1class Solution {2    public int lengthOfLIS(int[] nums) {3        int n = nums.length;4        int[] dp = new int[n]; // dp[i] = longest increasing subsequence ENDING at i5        Arrays.fill(dp, 1);    // every element alone has length 16        int best = 1;7        for (int i = 1; i < n; i++) {8            for (int j = 0; j < i; j++) {9                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);10            }11            best = Math.max(best, dp[i]);12        }13        return best;14    }15}

sim

LIS in O(n log n): patience piles

Deal numbers onto piles like solitaire. Number of piles = LIS length. Binary search picks the pile.

loading simulation…

javajava.util.*

1class Solution {2    public int lengthOfLIS(int[] nums) {3        int[] tails = new int[nums.length]; // tails[k] = smallest tail of any increasing run of length k+14        int size = 0;5        for (int x : nums) {6            int lo = 0, hi = size; // binary search: first tail >= x7            while (lo < hi) {8                int mid = (lo + hi) >>> 1;9                if (tails[mid] < x) lo = mid + 1;10                else hi = mid;11            }12            tails[lo] = x; // replace that tail (or append)13            if (lo == size) size++;14        }15        return size;16    }17}

05 · cost

Time & space, explained

The DP ladder (Fibonacci / Climbing Stairs)
	Time	Extra space	why
Plain recursion	O(2ⁿ) (≈ 1.618ⁿ)	O(n)	Each call spawns two more; the tree has ~φⁿ nodes. Space is the recursion depth.
Memoization (top-down)	O(n)	O(n)	Each of the n+1 states is computed once; later calls are O(1) lookups. Memo + stack are O(n).
Tabulation (bottom-up)	O(n)	O(n)	One loop over n cells, O(1) work each. The table has n+1 slots, no stack.
Space-optimised	O(n)	O(1)	Each cell reads only the previous two, so two variables replace the table.

Classic DP shapes
	Time	Table space	Optimised space	why
1D linear (stairs, robber, decode ways)	O(n)	O(n)	O(1)	n states × O(1) transition; only the last 1–2 cells are read.
Coin change / Combination Sum IV (amount A, k values)	O(A·k)	O(A)	O(A)	A states, each tries k values. The 1D table is already minimal.
Grid m × n (unique paths, min path, maximal square)	O(m·n)	O(m·n)	O(n)	One O(1) step per cell; a row only reads itself and the row above.
Triangle (n rows)	O(n²)	O(n²)	O(n)	n(n+1)/2 cells, O(1) each; bottom-up needs only the row below.
0/1 knapsack (n items, capacity W)	O(n·W)	O(n·W)	O(W)	n·W cells, O(1) each. Pseudo-polynomial: it grows with the value W, not its digit count.
LIS	O(n²) or O(n log n)	O(n)	O(n)	n states × O(n) look-back; patience replaces the look-back with a binary search.
Two strings (LCS, edit distance)	O(m·n)	O(m·n)	O(min(m, n))	One cell per pair of prefixes; each reads 3 neighbours from this row and the previous one.
Interval DP (burst balloons)	O(n³)	O(n²)	O(n²)	n² intervals × O(n) choices of split point. Every interval may be read later, so no row trick.

06 · java

Raw vs Collections Framework

Memo: plain array vs HashMap

javalong[] memojava.util.*

1class FibMemoArray {2    /** Same idea with a plain array: index = n, 0 = "not computed yet" (fib(k) > 0 for k >= 1). */3    static long fib(int n) {4        return fib(n, new long[n + 1]);5    }6 7    private static long fib(int n, long[] memo) {8        if (n <= 1) return n;9        if (memo[n] != 0) return memo[n];10        return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);11    }12}

javaHashMap<Integer, Long> memojava.util.*

1class FibMemoMap {2    private final Map<Integer, Long> memo = new HashMap<>();3 4    /** Top-down: the same recursion, but every answer is saved the first time it is computed. */5    long fib(int n) {6        if (n <= 1) return n;7        Long cached = memo.get(n);8        if (cached != null) return cached;9        long result = fib(n - 1) + fib(n - 2);10        memo.put(n, result);11        return result;12    }13}

When states are small integers (0..n, or i×j), use an array: faster, no boxing, and int[]/long[] start at 0 for free.
Use a HashMap when states are sparse, huge, negative, or not integers (e.g. a String key or a pair encoded as i + "," + j).
You need a value that means "not computed yet". 0 works only if 0 can't be a real answer; otherwise Arrays.fill(memo, -1) or use Integer[]/Boolean[] where null = unknown.
Don't write memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2)) on a HashMap: the recursive call modifies the map inside computeIfAbsent, which throws ConcurrentModificationException (Java 9+). Use get → compute → put.

Bottom-up table, then squeeze it

javalong[] dp tablejava.util.*

1class FibTable {2    /** Bottom-up: fill the table from the smallest subproblem upward. No recursion at all. */3    static long fib(int n) {4        if (n <= 1) return n;5        long[] dp = new long[n + 1];6        dp[0] = 0;7        dp[1] = 1;8        for (int i = 2; i <= n; i++) {9            dp[i] = dp[i - 1] + dp[i - 2];10        }11        return dp[n];12    }13}

javatwo rolling variablesjava.util.*

1class FibTwoVars {2    /** dp[i] only reads dp[i-1] and dp[i-2], so keep just those two numbers. */3    static long fib(int n) {4        if (n <= 1) return n;5        long prev2 = 0, prev1 = 1;6        for (int i = 2; i <= n; i++) {7            long cur = prev1 + prev2;8            prev2 = prev1;9            prev1 = cur;10        }11        return prev1;12    }13}

Tabulation has no recursion, so no StackOverflowError on large n — Java's default stack overflows somewhere around 10⁴ frames.
Always write the full table first. Only squeeze to variables or rows once it works — it's an easy, safe last step in an interview.
long instead of int when values grow fast: fib(47) already overflows int.

Knapsack: 2D table vs one rolling row

java0/1 knapsack, 2Djava.util.*

1class Knapsack01 {2    /** dp[i][c] = best value using only the first i items with capacity c. */3    static int knapsack(int[] wt, int[] val, int cap) {4        int n = wt.length;5        int[][] dp = new int[n + 1][cap + 1]; // row 0 = no items = value 06        for (int i = 1; i <= n; i++) {7            for (int c = 0; c <= cap; c++) {8                dp[i][c] = dp[i - 1][c]; // option 1: skip item i9                if (wt[i - 1] <= c) {10                    // option 2: take item i once, so look at the row ABOVE11                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - wt[i - 1]] + val[i - 1]);12                }13            }14        }15        return dp[n][cap];16    }17}

java0/1 knapsack, 1D (capacity downward)java.util.*

1class Knapsack01Rolling {2    /** One row is enough. Loop capacity DOWNWARD so each item is used at most once. */3    static int knapsack(int[] wt, int[] val, int cap) {4        int[] dp = new int[cap + 1];5        for (int i = 0; i < wt.length; i++) {6            for (int c = cap; c >= wt[i]; c--) {7                dp[c] = Math.max(dp[c], dp[c - wt[i]] + val[i]);8            }9        }10        return dp[cap];11    }12}

In the 1D version, dp[c - w] must still be the value from the previous item's row. Going downward guarantees we haven't overwritten it yet.
Going upward instead lets an item be counted twice — that's the unbounded knapsack below.

Unbounded knapsack: same code, opposite loop

javaunlimited copies (capacity upward)java.util.*

1class KnapsackUnbounded {2    /** Unlimited copies: loop capacity UPWARD so dp[c - w] may already contain item i. */3    static int knapsack(int[] wt, int[] val, int cap) {4        int[] dp = new int[cap + 1];5        for (int i = 0; i < wt.length; i++) {6            for (int c = wt[i]; c <= cap; c++) {7                dp[c] = Math.max(dp[c], dp[c - wt[i]] + val[i]);8            }9        }10        return dp[cap];11    }12}

Coin Change (fewest coins) and Coin Change II (count ways) are both unbounded knapsack: coins can be reused.
Outer loop over items + inner loop over capacity counts combinations. Swap the loops and you count ordered sequences — that's Combination Sum IV (LC 377) in this chapter.

Java API you will actually use
call	does	cost
`new int[n + 1]`	Table of n+1 zeros (index = state). Off-by-one +1 so dp[n] exists.	O(n)
`new int[m + 1][n + 1]`	2D table, row 0 / column 0 = empty prefix	O(m·n)
`Arrays.fill(dp, -1)`	Mark every state "not computed" (or fill with a sentinel like amount + 1)	O(n)
`new Integer[m][n] / new Boolean[n]`	Memo where null = unknown (when 0 / false are real answers)	O(m·n)
`map.get(k) / map.put(k, v)`	HashMap memo for sparse or non-integer states	O(1) avg
`Math.max(a, b) / Math.min(a, b)`	The heart of every optimisation transition	O(1)
`Arrays.binarySearch(a, 0, size, x)`	Index of x, or −(insertionPoint) − 1 if absent — usable for LIS patience	O(log n)
`s.substring(i, j)`	Copies j − i chars (Word Break, Decode Ways) — not free	O(j − i)
`Arrays.stream(nums).sum()`	Total of an int[] (Partition Equal Subset Sum)	O(n)

Fastest way to a correct answer from a recursive idea

→ Memoization (top-down)

Add a cache to the recursion you already wrote. Only reachable states get computed.

Large n (deep recursion) or you need to squeeze space

→ Tabulation (bottom-up)

No stack overflow, and an explicit fill order makes row/variable reuse possible.

States are 0..n or (i, j) grids

→ int[] / int[][] / long[]

Direct indexing, no boxing, cache-friendly.

States are sparse, negative or composite (strings, tuples)

→ HashMap<Key, Value>

Arrays would be huge or impossible to index.

0 or false are legitimate answers

→ Integer[] / Boolean[] (null = unknown) or a −1 sentinel

Otherwise you can't tell "computed as 0" from "never computed".

07 · recognise

Spot the pattern

"Count the number of ways…"

Counting DP: dp[state] = sum of ways of the smaller states it comes from

"Minimum / maximum cost, length, profit…" with choices at each step

Optimisation DP: dp[state] = best over choices (min/max)

"Is it possible to…" (reach, split, partition, form)

Feasibility DP with booleans: dp[state] = OR over choices

Your recursion has parameters that repeat (draw the tree — same arguments appear twice)

Overlapping subproblems → memoize

Choose items with a weight/budget limit; each item once

0/1 knapsack (capacity loop downward in 1D)

Unlimited supply of each item (coins, ribbon pieces)

Unbounded knapsack (capacity loop upward)

"How many sequences add up to target" and the order matters

Unbounded knapsack with the target loop OUTSIDE (Combination Sum IV)

Two strings: compare, align, convert, common subsequence

2D DP on prefixes dp[i][j]

Grid, move only right/down (or down a triangle)

Grid DP: dp[r][c] from above and left; triangles go bottom-up

Largest square of 1s in a binary grid

dp[r][c] = 1 + min(up, left, up-left): the square ending at this corner

Subsequence (not subarray!) that increases / is the longest

LIS: O(n²) DP or O(n log n) patience

Merge / burst / split a range and the order matters

Interval DP: dp[i][j], short intervals first, try every split point k

n ≤ ~20 and you need subsets

Probably backtracking or bitmask DP, not a plain table

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Not writing the meaning of dp[i] in one sentence before coding. Most wrong DP code comes from a fuzzy state.
Off-by-one between dp[i] = "first i characters" and s.charAt(i - 1). Pick one convention and say it out loud.
Using 0 as "not computed" when 0 is a valid answer — the memo never hits (slow) or returns wrong values.
Filling the table in the wrong order: reading dp[i+1] before it's computed silently uses 0.
Integer.MAX_VALUE as infinity, then + 1 → overflows to a negative number and becomes the "minimum". Use amount + 1 or check before adding.
1D knapsack with the capacity loop in the wrong direction: upward = items reused, downward = each once.
Coin Change II with loops swapped (amount outside, coins inside) counts 1+2 and 2+1 as different — that's Combination Sum IV's answer, not 518's.
Greedy instead of DP: coins {1, 3, 4} for amount 6 — greedy gives 4+1+1 (3 coins), DP finds 3+3 (2 coins).
Forgetting that recursion depth itself costs O(depth) space, and that Java may throw StackOverflowError for depth ≳ 10⁴.

tricks

Always start from the brute-force recursion. Say "this recomputes the same states — let me cache them". That's the interviewer's favourite path.
Write the 5 steps as comments before any code: state, transition, base case, order, answer.
Chalo, dry-run karte hain: fill the table for a tiny input by hand (3–4 cells). If your hand-made table is right, your code will be.
Draw the dependency arrows: if dp[i][j] reads up, left and up-left, the fill order is rows top→bottom, columns left→right.
After it works, ask "which cells do I still read?" — that tells you if you can drop to two rows or two variables.
Name things in English: ways, best, canMake, fewest. dp alone is fine only if you've said what it means.
For "reconstruct the answer" follow-ups, keep the full table and walk back from the answer cell (like the arrows in the LCS sim).

09 · why & how

Questions you might be too shy to ask

How do I know a problem is DP and not greedy or backtracking?

Ask two questions. 1) Do I make a sequence of choices, and is the best answer built from best answers to smaller versions? 2) Does a brute-force recursion hit the same arguments more than once? If both are yes, it's DP. If a simple local rule always works (and you can argue why), it's greedy. If you must list all solutions, not just count or optimise them, it's backtracking.

The memoized fib still calls itself twice. How did it become O(n)?

Each state is fully computed only once. The first fib(5) does the real work and writes it down. Every later fib(5) call finds the answer in the memo and returns in O(1), without going deeper. So at most n + 1 states do real work, each making 2 calls: about 2n calls in total, O(n).

I freeze when I can't see the recurrence. What do I do?

Don't hunt for the formula first. Write the slow recursion that tries every choice — you can always do that. Then circle its changing parameters (that's the state), draw its calls for a tiny input to see the repeats, and add a memo. The table version comes after, almost mechanically. Bas itna yaad rakho: brute force first, cache second, table third.

Memoization or tabulation — which should I write in an interview?

Whichever you can write correctly first. Memoization is usually easier because it's your recursion plus 3 lines. Then mention tabulation removes recursion (no stack overflow) and enables space optimisation. Many interviewers then ask you to convert — the 5-step recipe makes that mechanical.

How do I come up with the state?

Look at your brute-force recursion: its changing parameters are the state. rob(i) → dp[i]. lcs(i, j) → dp[i][j]. knap(i, capacity) → dp[i][c]. If you need more information to decide the next move (like "the previous element" in LIS), it goes into the state too.

Why is the table new int[n + 1], and what value goes in dp[0]?

When dp[i] means "the first i items", i runs from 0 to n, which is n + 1 slots, and the answer sits in dp[n]. dp[0] is the empty case and it's your base case. Ask "what is the answer for nothing?": ways to climb 0 stairs or make amount 0 → 1 (do nothing, one way). Fewest coins for 0 → 0. Can the empty string be broken into words → true.

Why is knapsack O(n·W) called "pseudo-polynomial"?

W is a number, and the table has W+1 columns. If W = 10⁹, the table is impossibly big even though W fits in 4 bytes. Running time is polynomial in the value of W, but exponential in the number of bits used to write W. That's why 0/1 knapsack is still NP-hard in general.

What is the difference between subarray and subsequence?

A subarray (or substring) is contiguous: [2, 3, 4] inside [1, 2, 3, 4, 5]. A subsequence keeps order but may skip elements: [1, 3, 5]. Subarray problems often fall to sliding window or Kadane; subsequence problems usually need DP like LIS or LCS.

My memoized solution gets StackOverflowError. Is it wrong?

Probably not — the recursion is just too deep for Java's default thread stack. How deep is too deep depends on frame size and settings — think "a few thousand to tens of thousands of calls", not an exact number. Convert it to tabulation: same states and transition, filled with loops instead of calls.

How do I know the fill order for tabulation?

Look at what the transition reads. If dp[i] reads dp[i−1], go i upward. If dp[i][j] reads dp[i+1][j−1] (palindromes), go by interval length, short to long. The rule: every cell you read must already be filled.

Why does LIS return the biggest dp[i], not just dp[n − 1]?

dp[i] is the longest run that ends at i. The best run can end anywhere. In [1, 2, 3, 0], dp[3] is 1 (just the 0), but the answer is 3 (1, 2, 3, ending at index 2). So keep a running best over all i. When dp[i] means "the first i items" instead (House Robber), dp[n] already is the answer.

In Edit Distance, why does ↑ mean delete and ← mean insert?

Read the cell you came from. dp[i − 1][j] (↑): the first i − 1 chars of word1 already became word2's first j, so word1's i-th char is extra: delete it. dp[i][j − 1] (←): the first i chars of word1 already became word2's first j − 1, so insert word2's j-th char. dp[i − 1][j − 1] (↖): replace one char with the other. Each costs 1.

How do I return the actual items/path, not just the number?

Keep the full table, then walk backwards from the answer cell asking "which choice produced this value?" In knapsack: if dp[i][c] ≠ dp[i−1][c], item i was taken. In LCS: diagonal moves are kept characters. That's why space-optimised versions often can't reconstruct.

Is DP always faster than greedy?

No — greedy is usually faster (often O(n) or O(n log n)) when it is correct. DP is the safe tool when greedy has a counter-example. Coin change with coins {1, 3, 4}: greedy picks 4+1+1 for 6, DP finds 3+3.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#70
Climbing Stairsmust-do
EasyAdobeInfosysBloombergAmazonMicrosoft+1
#746
Min Cost Climbing Stairs
EasyAmazonGoogleBloombergMicrosoft
#198
House Robbermust-do
MediumInfosysAmazonByteDance / TikTokAirbnbWalmart+1
#213
House Robber IImust-do
MediumMicrosoftAmazonGoogle
#91
Decode Waysmust-do
MediumMicrosoftMetaAmazonGoogle
#152
Maximum Product Subarraymust-do
MediumLinkedInAdobeAmazonGoogleMicrosoft
#139
Word Breakmust-do
MediumWalmartIntuitUberAmazonBloomberg+1
#322
Coin Changemust-do
MediumPayPalIntuitByteDance / TikTokWalmartAmazon+1
#518
Coin Change II
MediumAmazonGoogleMicrosoftBloomberg
#377
Combination Sum IV
MediumGoogleMetaAmazonBloombergMicrosoft
#416
Partition Equal Subset Summust-do
MediumAmazonGoogleMicrosoftMeta
#62
Unique Pathsmust-do
MediumAmazonBloombergMetaGoogleGoldman Sachs
#63
Unique Paths II
MediumBloombergAmazonGoogleMicrosoftGoldman Sachs
#64
Minimum Path Sum
MediumGoldman SachsMicrosoftAmazonGoogle
#120
Triangle
MediumBloombergAmazonMicrosoftGoogleGoldman Sachs
#221
Maximal Square
MediumPayPalByteDance / TikTokAirbnbGoogleApple+1
#300
Longest Increasing Subsequencemust-do
MediumSamsungByteDance / TikTokPayPalWalmartMicrosoft+1
#1143
Longest Common Subsequencemust-do
MediumMicrosoftGoogleAmazonMeta
#72
Edit Distancemust-do
MediumAmazonBloombergMicrosoftGoogle
#5
Longest Palindromic Substringmust-do
MediumTCSMicrosoftBloombergAmazonByteDance / TikTok+1
#312
Burst Balloons
HardSamsungGoogleAmazon

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#509
Fibonacci Number
Easyin Recursion
The smallest DP there is — memo or two variables. The warm-up for Climbing Stairs.
#53
Maximum Subarray
Mediumin Arrays & Strings
Kadane's algorithm is 1D DP: best sum ending here = max(x, best ending before + x).
#338
Counting Bits
Easyin Bits
dp[i] = dp[i >> 1] + (i & 1): a one-line DP over numbers instead of indices.
#329
Longest Increasing Path in a Matrix
Hardin Topo Sort
DP on a DAG: memoize the longest path from each cell — LIS in two dimensions.
#787
Cheapest Flights Within K Stops
Mediumin Shortest Paths
Bellman–Ford is DP over "paths that use at most k edges" — one table row per extra edge.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
DP = recursion + a notebook. Solve each small question once, store it, and build bigger answers from stored ones.
use it when
"Count the ways", "min/max cost", "is it possible" — with a choice at each step and a brute-force recursion that repeats the same arguments.
template
State (what dp[i] means) → transition → base cases → fill order → answer cell. Write these 5 lines as comments first.
cost
Time = states × work per state. Stairs: n × O(1). LCS: m·n × O(1). LIS: n × O(n). Knapsack: n·W — pseudo-polynomial.
template
Memo: int[] memo filled with −1, check → compute → store. Table: new int[n + 1], loop up from the base cases.
pro tip
Only the last 1–2 cells or rows are read? Keep prev2/prev1 or prev/cur rows: O(n) → O(1), O(m·n) → O(n).
trap
0/1 knapsack in 1D: loop capacity DOWN. Going up lets an item be reused — that's unbounded knapsack.
trap
Coins outside → combinations (LC 518). Target outside → orderings (LC 377). Swap the loops and you change the answer.
trap
Integer.MAX_VALUE + 1 wraps negative: use amount + 1 as infinity. Use −1 (not 0) for "not computed" when 0 is a real answer.
pro tip
Stuck? Write the brute-force recursion first. Its changing parameters ARE the DP state.

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Which two properties make a problem a DP problem?

tap or Space to flip ↻

Question 1: Which two properties make a problem a DP problem?

13 · check yourself

Quick quiz

Which two properties make a problem a good fit for DP?
Memoized fib(n) makes how many calls?
In the 1D 0/1 knapsack, why does the capacity loop go downward?
Coins {1, 3, 4}, amount 6. Greedy (largest coin first) uses how many coins, and what's optimal?
dp[t] += dp[t − x], with the target loop OUTSIDE and the numbers loop inside. What does it count?
LCS of "abcde" and "ace": text1[i−1] == text2[j−1]. What is dp[i][j]?
Unique Paths II: the START cell is a rock. What is the answer?
What does tails[k] mean in the O(n log n) LIS?
dp[i][j] for a palindrome table reads dp[i+1][j−1]. Which fill order is correct?
Your memoized Java solution throws StackOverflowError at n = 10⁵. Best fix?

0/0 correct · 10 left

14 · learn more