Notesfoundation

Dynamic Programming

The whole craft in one place — what DP is, how to recognise it, and one 3-step framework (state → recurrence → base cases) applied to a dozen worked examples from Fibonacci to stock trading. Every practice problem links to LeetCode.

30 min read·verified Content review 2026·reviewed 2026-08-30

After this you should be able to

Explain the core idea in Dynamic Programming
Apply Dynamic Programming in a representative exercise

MemoizationTabulationState & Recurrence

DSA · Dynamic Programming · From the ground up

The whole craft in one place: what DP really is, how to recognise it under interview pressure, and a single 3-step framework that solves nearly every DP problem — applied to a dozen worked examples from Fibonacci to stock trading. Every practice problem links straight to LeetCode. Java throughout.

⭐ TRICK the insight that makes it easy ⚠ PITFALL a common mistake / gotcha 💡 TIP interview-relevant aside [+] my own addition

Companion notes Want the same topic taught recursion-first — one 4-step template, ten worked problems unchanged? See Dynamic Programming, From Recursion Up.

Notebook Summary (copy by hand)#

Telegraphic and deck-ready — arrows over sentences. Everything here is derivable from the chaptered notes below.

WHAT IS DP?
==========
DP = explore ALL solutions efficiently by reusing sub-answers.
Needs BOTH:
  1. overlapping subproblems  -> same small problem solved many times
  2. optimal substructure     -> best(whole) built from best(parts)
fib(n)=fib(n-1)+fib(n-2)  ->  both hold.  brute O(2^n) -> DP O(n)

vs cousins:
  greedy           -> optimal substructure, NO overlap
  divide & conquer -> splits, but subproblems DON'T overlap

TWO IMPLEMENTATIONS  (any DP can be either)
===========================================
              | TOP-DOWN (memoization)   | BOTTOM-UP (tabulation)
  built with  | recursion + hashmap/arr  | iteration + array
  starts at   | the answer, recurses down| base cases, builds up
  ordering    | don't care (recursion)   | must order subproblems
  speed       | recursion overhead       | usually FASTER
  ease        | EASIER to write          | trickier (loop order)
⭐ recursion WITHOUT memo = not DP, just slow recursion (O(2^n)).

WHEN IS IT DP?  (2 signals)
===========================
1. asks for OPTIMUM or COUNT:
     max/min cost, longest/shortest, # of ways, is-it-possible
2. future choices DEPEND on earlier choices
     (taking X now blocks Y later)  -> kills greedy

signal 1 alone -> could be greedy.  signal 1 + 2 -> DP.
⭐ test: assume greedy works, then hunt a counterexample.
   robber [2,7,9,3,1]: greedy grabs 7, loses the 9. -> DP.

THE FRAMEWORK  (3 pieces, top-down OR bottom-up)
================================================
state   = minimal variables that fully describe a scenario
          (keep only RELEVANT ones — not "sock colour")
1. dp(state) -> answer to the (generalised) problem for that state
2. recurrence  -> relate dp(state) to smaller states   [HARDEST step]
3. base cases  -> states answerable without recursion   [easiest step]

climb stairs: dp(i)=dp(i-1)+dp(i-2); dp(1)=1,dp(2)=2  (fib in disguise)
robber:       dp(i)=max(dp(i-1), dp(i-2)+nums[i])

MULTI-DIMENSIONAL  (more state vars = harder)
=============================================
state-var sources: index i | 2nd index j | limit k
                   | status flag (holding?) | bitmask of used
⭐ STATE REDUCTION: if vars relate, derive one from others.
   mult-ops: right = n-1-(i-left)  -> drop a whole dimension.
ITERATION IN RECURRENCE: choice is a RANGE not 2 options
   -> add an inner for-loop: dp(i)=min over j of (... dp(j) ...)

COMPLEXITY: time = #states x work/state ; space = #states
   #states = product of (range of each state var).
⭐ SPACE TRIM: static recurrence looks back k -> keep k vars. fib O(n)->O(1)

PATTERN CHEAT-SHEET
===================
COUNTING DP        sum states (no max/min); base case != 0.   climb, coin-change-2
STATE BY INACTION  "do nothing" -> dp(i)=dp(i-1).             robber, stock-IV
KADANE             max subarray; cur=max(cur+x,x); O(1).      max-subarray
PATHING (grid)     dp[r][c]=dp[r-1][c]+dp[r][c-1]; move 1-way.unique-paths
DP ON STRINGS      i (& j) index; "is it formable?".          word-break, LCS

⭐ The whole craft in two moves Define the state (what minimal facts describe where you are) and find the recurrence (how the answer for a state is built from smaller states). Base cases, memoization, and the bottom-up rewrite are all mechanical once those two are right.

Detailed Study Notes#

You're asked: "How many ways can you climb a 30-step staircase taking 1 or 2 steps at a time?" You write the obvious recursion and for n=30 it's instant; for n=50 your fan spins up; for n=250 the universe ends first. Nothing got harder — you're just re-computing the same staircases billions of times. Dynamic programming is the discipline of never solving the same subproblem twice.

Pick a chapter, then expand only the cards you need.

CHAPTER 1Intro to Dynamic Programming

What DP is, the two ways to implement it, and how to recognise a DP problem in the wild.

What is Dynamic Programming?Concept+

DP systematically explores every possible solution while reusing the answers to the smaller problems inside it. A problem is a DP problem when it has two properties at once:

Overlapping subproblems — solving it means solving smaller versions of the same problem, and those repeat. To get F(6) you need F(4); to get F(5) you also need F(4). Same work, asked for twice.
Optimal substructure — the answer to the whole is built from the answers to its parts: F(n) = F(n-1) + F(n-2).

Analogy A contractor pricing a house. Optimal substructure = pricing the house by pricing each room and adding them up. Overlapping subproblems = noticing the kitchen and utility room share the same plumbing quote — so you price that quote once and reuse it.

fib(5) recursion tree — F2 is computed 3× and F3 twice. Memoising each the first time collapses the tree to a line.

Contrast the cousins DP is confused with. Greedy has optimal substructure but no overlap — it commits and never reconsiders. Divide and conquer (merge sort) splits into subproblems, but they're disjoint. DP lives precisely where subproblems overlap, and that overlap is what turns exponential brute force into linear work.

Top-down and Bottom-upConcept+

Every DP algorithm can be written two ways — approaching the same staircase from opposite ends.

Bottom-up (tabulation)+

Start at the base cases and iterate forward, filling a table until you reach the answer. For Fibonacci you know F(0)=0, F(1)=1, so you compute upward to F(n). A loop over an array — no recursion.

# Bottom-up: build from the base cases upward
F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

Top-down (memoization)+

Start at the answer, recurse toward the base cases, and cache every result the first time you compute it. Memoising means storing each computed value (hashmap or array) so a repeat call returns the stored answer instead of recursing again.

# Top-down: recurse, but remember what you've already solved
memo = hashmap
Function F(integer i):
    if i is 0 or 1:
        return i
    if i not in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

Same computation, opposite directions: top-down dives from the answer to the base; bottom-up climbs from the base to the answer.

Which is better?#

Bottom-up wins on speed. No call-stack overhead, and no stack-overflow on deep inputs.

Top-down wins on ease. Recursion sorts out the subproblem order for you, and it mirrors how you reason about the recurrence.

⚠ Pitfall Recursion without memoisation is not DP — it's just slow recursion (O(2ⁿ)). The usual workflow: write top-down first, convert to bottom-up if you need the speed.

When to Use DPConcept+

Recognising DP applies is half the battle. Use two practical signals instead of the slippery theory.

Signal 1 — asks for an optimum or a count: "minimum cost of…", "maximum profit from…", "how many ways to…", "longest possible…", "is it possible to reach…". This narrows it to greedy or DP.

Signal 2 — earlier decisions constrain later ones. Choosing now removes options later. This is what kills greedy and demands DP.

House Robber: a greedy pass takes 7 over 2 and forfeits the adjacent 9. Earlier choices constrain later ones ⇒ DP.

House Robber (max cash, never two adjacent): optimum is 2+9+1=12, but greedy takes 7 and loses the 9. Longest Increasing Subsequence is similar: taking a 6 early blocks the smaller 3 and 5 that build a longer run.

⭐ Trick — the greedy disproof Unsure whether signal 2 applies? Assume greedy works and hunt for a counterexample where an early choice sabotages a later one. Find one ⇒ DP is needed; can't find one ⇒ greedy may be correct.

CHAPTER 2Strategic Approach to DP

The 3-step framework, worked end-to-end on House Robber, then multidimensional state, top-down→bottom-up conversion, and how to read off complexity.

A Framework for DP ProblemsConcept+

Every DP solution is the same three pieces. First, one definition: a state is the minimal set of variables that fully describes a scenario. In Climbing Stairs the only relevant state variable is the step you're on — your sock colour is a variable too, but it doesn't change the answer, so it's irrelevant and dropped.

A function / array

dp(state) returns the original problem, generalised to "considered up to this state."

A recurrence

Relates dp(state) to smaller states. Almost always the hardest step.

Base cases

States answerable without the recurrence, so it terminates. Usually the easiest step.

For Climbing Stairs (reach step n, 1 or 2 steps at a time):

Function: dp(i) = ways to reach step i; answer dp(n).
Recurrence: arrive from i-1 or i-2, so dp(i) = dp(i-1) + dp(i-2).
Base cases: dp(1)=1, dp(2)=2.

⭐ Trick Climbing Stairs is Fibonacci in disguise. Spotting a known recurrence under new clothing is half of DP fluency.

Naive top-down is correct but O(2ⁿ) — every call spawns two more. Add a memo and it's O(n):

class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<>();
    private int dp(int i) {
        if (i <= 2) return i;                // base cases
        if (!memo.containsKey(i)) {
            memo.put(i, dp(i - 1) + dp(i - 2)); // compute once, then cache
        }
        return memo.get(i);
    }
    public int climbStairs(int n) { return dp(n); }
}

Bottom-up follows the exact same three pieces — base cases first, then iterate up:

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;                 // base cases
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];    // recurrence
        return dp[n];
    }
}

💡 Tip A hashmap is overkill for a dense 0…n range — an array is leaner. But hashmaps shine when top-down only visits a sparse subset of states.

LC 70 Climbing StairsEasy The canonical framework example — Fibonacci in disguise.
LC 509 Fibonacci NumberEasy The recurrence everything else builds on.

Example — House RobberExample+

Framework end-to-end. Rob houses for max money, never two adjacent.

State & function. Index i of the house; dp(i) = most money from houses 0…i; answer dp(n-1).
Recurrence. Skip i → keep dp(i-1); rob it → dp(i-2)+nums[i] (robbing forces skipping i-1). Take the better: dp(i) = max(dp(i-1), dp(i-2)+nums[i]).
Base cases. dp(0)=nums[0], dp(1)=max(nums[0],nums[1]).

⭐ Trick — why no "robbed-previous?" flag It feels like you need a boolean for "did I rob the last house?" You don't: anchoring the recurrence on dp(i-2) when you rob bakes the constraint in, halving the state space. Designing the recurrence to absorb a constraint is a recurring move (see State Reduction).

class Solution {                                 // top-down
    private HashMap<Integer, Integer> memo = new HashMap<>();
    private int[] nums;
    private int dp(int i) {
        if (i == 0) return nums[0];                          // base cases
        if (i == 1) return Math.max(nums[0], nums[1]);
        if (!memo.containsKey(i)) memo.put(i, Math.max(dp(i - 1), dp(i - 2) + nums[i]));
        return memo.get(i);
    }
    public int rob(int[] nums) { this.nums = nums; return dp(nums.length - 1); }
}

class Solution {                                 // bottom-up
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];                                     // base cases
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        return dp[nums.length - 1];
    }
}

Both O(n) time and space — and droppable to O(1) space with rolling variables (see State Reduction).

LC 198 House RobberMedium The archetype: max + adjacency constraint.
LC 746 Min Cost Climbing StairsEasy Reach i from i-1 or i-2; pick the cheaper.
LC 1137 N-th Tribonacci NumberEasy Fibonacci with three look-back terms.
LC 740 Delete and EarnMedium House Robber in disguise — bucket counts by value, then rob over values.

Multidimensional DPConcept+

"Dimensions" = number of state variables. Everything so far was 1-D; most interview DP is 2-D, and the framework doesn't change — you just think harder about the function and recurrence. Extra state variables usually come from: a second index, an explicit limit (k transactions), a status flag (holding / not), or a bitmask of used items.

Maximum Score from Multiplication Operations: over m ops, the i-th gains multipliers[i] × a number from the left or right end of nums (then removed). Maximise total.

⭐ Trick — state reduction by arithmetic You seem to need three facts (ops done, left index, right index), but they relate: if i ops total and left from the left, then i-left came from the right, so right = n-1-(i-left). Two state variables instead of three — and since #states is the product of ranges, dropping a dimension is a real complexity win.

Function: dp(i, left) = max score after i ops with left taken from the left; answer dp(0,0).
Recurrence: with mult=multipliers[i], dp(i,left)=max(mult·nums[left]+dp(i+1,left+1), mult·nums[right]+dp(i+1,left)).
Base case: i == m → return 0.

class Solution {                          // top-down (2D memo for tight limits)
    private int[][] memo;
    private int[] nums, multipliers;
    private int n, m;
    private int dp(int i, int left) {
        if (i == m) return 0;                          // base case
        int mult = multipliers[i];
        int right = n - 1 - (i - left);                // derived 3rd variable
        if (memo[i][left] == 0) memo[i][left] = Math.max(mult * nums[left]  + dp(i + 1, left + 1), mult * nums[right] + dp(i + 1, left));
        return memo[i][left];
    }
    public int maximumScore(int[] nums, int[] multipliers) {
        n = nums.length; m = multipliers.length;
        this.nums = nums; this.multipliers = multipliers;
        this.memo = new int[m][m];
        return dp(0, 0);
    }
}

Both implementations are O(m²) time and space.

LC 1770 Maximum Score from Multiplication OperationsMedium Two-end pick; classic 3→2 state reduction.
LC 1143 Longest Common SubsequenceMedium dp(i,j): match → 1+dp(i-1,j-1), else max of dropping one char from either.
LC 221 Maximal SquareMedium dp[r][c]=1+min(up,left,up-left) for the square's bottom-right corner.

Top-down → Bottom-up ConversionConcept+

Solve top-down first (easier), then mechanically rewrite as a loop for speed:

Start from a finished top-down solution.
Make a dp array sized by your state variables; init to the value opposite the goal (-∞ for max, +∞ for min).
Set the same base cases.
Write nested loops over the state variables, iterating from the base cases outward.
Copy the recurrence into the innermost loop; turn every dp(...) into dp[...].
Return dp[...] for the original state.

⚠ Pitfall — loop direction Loops must start at the base cases and move toward the answer — sometimes backwards. If the base case is at i=n, iterate i high → low, or you'll read cells not yet filled.

Time and Space ComplexityConcept+

Less daunting than it sounds, because we compute each state exactly once.

Time = (number of states) × (work per state). When the recurrence is an O(1) equation, time = the number of states. Space = number of states. To count states, take each state variable's range and multiply.

Example: variables i (0…n), k (0…K), boolean holding → n·K·2 states → O(n·K). When work-per-state isn't constant (Word Break's substring), time grows but space still tracks the state count.

CHAPTER 3Common Patterns in DP

Three recurring shapes: a loop inside the recurrence, DP on strings, and the "do nothing" transition.

Iteration in the Recurrence — Job SchedulePattern+

Sometimes the choice at a state is a range ("do 1 job today, or 2, or 3…"), so the recurrence itself contains a for loop that tries every option and keeps the best.

Minimum Difficulty of a Job Schedule: finish n jobs (in order) over exactly d days, ≥1/day; a day's difficulty is its hardest job; minimise the sum.

State: dp(i, day) = min total difficulty starting with job i on day; answer dp(0,1).
Recurrence: do jobs i…j today (leaving ≥1/remaining-day, so j < n-(d-day)), tracking hardest: dp(i,day)=min over j of ( hardest(i..j) + dp(j+1, day+1) ).
Base case: last day → take all remaining jobs = hardest from i on (precompute hardestJobRemaining[]). If n < d → return -1.

class Solution {
    private int n, d;
    private int[][] memo;
    private int[] jobDifficulty, hardestJobRemaining;
    private int dp(int i, int day) {
        if (day == d) return hardestJobRemaining[i];       // last day: take the rest
        if (memo[i][day] == -1) {
            int best = Integer.MAX_VALUE, hardest = 0;
            for (int j = i; j < n - (d - day); j++) {      // the iteration in the recurrence
            hardest = Math.max(hardest, jobDifficulty[j]);
            best = Math.min(best, hardest + dp(j + 1, day + 1));
            }
            memo[i][day] = best;
        }
        return memo[i][day];
    }
    public int minDifficulty(int[] jobDifficulty, int d) {
        n = jobDifficulty.length;
        if (n < d) return -1;                              // impossible schedule
        hardestJobRemaining = new int[n];
        int h = 0;
        for (int i = n - 1; i >= 0; i--) {                 // precompute the base case
            h = Math.max(h, jobDifficulty[i]);
            hardestJobRemaining[i] = h;
        }
        memo = new int[n][d + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        this.d = d; this.jobDifficulty = jobDifficulty;
        return dp(0, 1);
    }
}

💡 Tip — complexity with a loop in the recurrence The "≥1/day" constraint makes many states unreachable; we visit only d·(n−d), each with a j-loop of ~(n−d) → time O(d·(n−d)²). Top-down space is O(d·(n−d)) (only reachable states memoised) vs O(n·d) bottom-up — a rare case where top-down's space bound is tighter.

LC 1335 Minimum Difficulty of a Job ScheduleHard Range choice per day → loop in the recurrence.
LC 322 Coin ChangeMedium dp[i]=min over coins of dp[i-coin]+1; the coin loop is the iteration.

Example — Word Break (DP on strings)Example+

The trickiest "is it even DP?" case — no numbers, and "is it possible to…" isn't an obvious flag. Word Break: can s be segmented into words from wordDict (reusable)? Greedy fails — with s="abcdef" and ["abcde","ef","abc","a","d"], both longest-match ("abcde") and shortest-match ("a") dead-end. Order matters ⇒ DP.

State: index i; dp[i] = can s up to i be built? (no 2nd variable — the dict never changes.)
Recurrence: dp[i] is true if some word ends at i and the prefix before it, dp[i-word.length], is also true.
Base case: a word starting at 0 needs dp[-1]; treat "i == word.length-1" as the satisfied prefix.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (String word : wordDict) {
                if (i >= word.length() - 1 && (i == word.length() - 1 || dp[i - word.length()])) {
                    if (s.substring(i - word.length() + 1, i + 1).equals(word)) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }
}

💡 Tip — work per state isn't always O(1) Each state loops over k words and does a substring of length ~L, so time is O(n·k·L), not O(n). Space is O(n). The law: time = #states × work-per-state.

LC 139 Word BreakMedium "Is it possible?" + order matters ⇒ DP, not greedy.
LC 300 Longest Increasing SubsequenceMedium dp[i] = LIS ending at i; extend any earlier smaller element.

State Transition by Inaction — Stock IVPattern+

Sometimes the best move is to not act, making two states share a value — dp(i)=dp(i-1) as one branch of a max. You saw it in House Robber (skipping a house); it shines in the stock problems.

Best Time to Buy and Sell Stock IV: at most k transactions, never hold two lots, maximise profit.

State (3-D): i = day; t = transactions left; holding ∈ {0,1}. dp(i,t,holding) = max profit from here; answer dp(0,k,0).
Recurrence: every state has "do nothing" = dp(i+1,t,holding), plus one action — holding → sell prices[i]+dp(i+1,t-1,0); not holding → buy -prices[i]+dp(i+1,t,1). Take the max.
Base cases: t==0 or i==prices.length → 0.

class Solution {
    private int[] prices;
    private int[][][] memo;
    private int dp(int i, int t, int holding) {
        if (t == 0 || i == prices.length) return 0;          // base cases
        if (memo[i][t][holding] == 0) {
            int doNothing = dp(i + 1, t, holding);
            int doSomething = (holding == 1) ? prices[i]  + dp(i + 1, t - 1, 0)           // sell
            : -prices[i] + dp(i + 1, t, 1);              // buy
            memo[i][t][holding] = Math.max(doNothing, doSomething);
        }
        return memo[i][t][holding];
    }
    public int maxProfit(int k, int[] prices) {
        this.prices = prices;
        this.memo = new int[prices.length][k + 1][2];
        return dp(0, k, 0);
    }
}

Time and space are O(n·k·2)=O(n·k) — the state count again.

LC 188 Best Time to Buy and Sell Stock IVHard 3-D state; "do nothing" branch.
LC 309 Buy and Sell Stock with CooldownMedium Three statuses: holding / free-to-buy / on cooldown.
LC 714 Buy and Sell Stock with Transaction FeeMedium Subtract the fee on each completed transaction.

CHAPTER 4Common Patterns Continued

Squeezing state, counting instead of optimising, and DP's leanest form — Kadane.

State ReductionConcept+

Two distinct savings under one name.

Fewer state variables → less time. If two variables relate by an equation, derive one and drop a dimension — as in Multidimensional DP (right=n-1-(i-left)), or House Robber skipping the "robbed-previous?" boolean.

Rolling variables → less space. When the recurrence is static and only looks back a fixed number of states, drop the array. Fibonacci needs only the last two values:

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int one_back = 1, two_back = 0;
        for (int i = 2; i <= n; i++) {
            int temp = one_back;
            one_back += two_back;   // keep only the two values the recurrence reads
            two_back = temp;
        }
        return one_back;
    }
}

⭐ Trick — when to reach for rolling variables If dp[i] only depends on dp[i-1] and dp[i-2], everything before i-2 is dead weight — replace the array with a few variables. (Cuts space; the variable-count reduction above cuts time.)

LC 746 Min Cost Climbing StairsEasy Re-solve in O(n) time, O(1) space with two rolling vars.

Counting DPPattern+

Many DP problems ask for a count, not an optimum (Climbing Stairs already did). Two things change:

The recurrence sums. Instead of max/min, you add the ways from contributing states: dp(i)=dp(i-1)+dp(i-2).

Base cases aren't 0. An additive recurrence with a 0 seed stays 0. Reason out the seed by hand — e.g. dp[0]=1.

⚠ Pitfall Forgetting the non-zero seed (often dp[0]=1) collapses the whole table to 0. In Coin Change II, dp[0]=1 = "one way to make amount 0: pick no coins."

LC 518 Coin Change IIMedium Count combinations; seed dp[0]=1, loop coins outside amount.
LC 91 Decode WaysMedium One-digit always; two-digit if 10–26. Watch leading '0'.
LC 276 Paint FenceMedium Same colour vs different (k-1 choices) at each post.

Kadane's AlgorithmPattern+

Kadane finds the maximum-sum subarray in O(n) time and O(1) space — DP at its leanest. At each index, decide whether the running sum is worth keeping or should restart.

Analogy Hiking and tracking net elevation. Whenever your cumulative climb dips below zero, the stretch behind you was net downhill — dragging it along only hurts your best run, so reset and measure fresh, while remembering the best climb you ever banked.

best = -infinity
current = 0
for num in nums:
    current = max(current + num, num)   # keep the streak, or restart at num
    best = max(best, current)
return best

Kadane keeps the running sum unless restarting at the current element is better; the peak ever seen is the answer.

💡 Tip Kadane only matters with negatives present (all-positive ⇒ the whole array). It's genuine DP — current is "best subarray ending at the previous index," carried forward.

LC 53 Maximum SubarrayMedium Kadane, verbatim.
LC 918 Maximum Sum Circular SubarrayMedium Kadane for the max, plus total − min-subarray for the wrap-around case.
LC 121 Best Time to Buy and Sell StockEasy A Kadane variant on price differences.

CHAPTER 5DP for Paths in a Matrix

Grid problems where one-way movement (e.g. only down/right) makes DP apply.

Pathing Problems — Unique PathsPattern+

Move through a matrix under rules that prevent going "backwards." Those one-way constraints are what make it DP rather than a graph search — and here bottom-up is often the more intuitive start.

Unique Paths: count distinct paths from top-left to bottom-right of an m×n grid, moving only down or right.

State: dp[row][col] = paths from start to that cell.
Recurrence: arrive from above or left — dp[row][col]=dp[row-1][col]+dp[row][col-1] (out-of-bounds = 0).
Base case: dp[0][0]=1.

Unique Paths on a 3×3 grid: first row/column all 1; every other cell sums its top and left neighbours → 6 at the goal.

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;                         // base case
        for (int row = 0; row < m; row++) for (int col = 0; col < n; col++) {
            if (row> 0) dp[row][col] += dp[row - 1][col];   // from above
            if (col > 0) dp[row][col] += dp[row][col - 1];   // from the left
        }
        return dp[m - 1][n - 1];
    }
}

Both styles are O(m·n). [+] Each row only reads the row above, so dp collapses to a single O(n) array — a nice space-reduction exercise.

LC 62 Unique PathsMedium The base pathing template.
LC 63 Unique Paths IIMedium Same, but obstacle cells force dp=0.
LC 64 Minimum Path SumMedium min of top/left, plus the cell's own value.
LC 931 Minimum Falling Path SumMedium Arrive from the three cells above-left, above, above-right.

III

Interview & Practice Q&A#

Q1 What two properties make a problem a DP problem?

Overlapping subproblems (the same smaller problem is solved repeatedly) and optimal substructure (the whole is built from its parts). Both must hold. Greedy has optimal substructure but no overlap; divide-and-conquer splits but its subproblems don't overlap.

Q2 Top-down vs bottom-up — which would you pick and why?

I'd derive top-down first because recursion mirrors the recurrence and figures out the subproblem order for me. Then, if speed or stack depth matters, convert to bottom-up — iteration avoids call-stack overhead. Same time complexity; the choice is ergonomics and constant factors.

Q3 Is plain recursion the same as dynamic programming?

No. Recursion without caching re-solves overlapping subproblems and stays exponential. It becomes DP only once you memoise (top-down) or tabulate (bottom-up) so each state is computed once. Climbing Stairs is O(2ⁿ) recursive, O(n) the moment you add a memo.

Q4 How do you decide between greedy and DP for a max/min problem?

I check whether earlier decisions constrain later ones. My test: assume greedy works and try to build a counterexample where a locally-best choice blocks a better global outcome. House Robber [2,7,9,3,1] is one — greedy grabs 7 and loses the 9. If such a case exists, greedy is unsafe and I use DP.

Q5 How do you compute the time and space complexity of a DP solution?

Time = number of states × work per state; the state count is the product of each variable's range. With an O(1) recurrence, time = state count; when a state does more work (a substring in Word Break, an inner loop in Job Schedule), multiply that in. Space = stored states, though rolling variables can cut it.

Q6 What is state reduction, and when can you apply it?

Two flavours. (1) If state variables relate, derive one and drop a dimension — Max Score's right=n-1-(i-left) turns 3 variables into 2. (2) If the recurrence is static and reads only the last few states, replace the array with rolling variables — Fibonacci goes O(n)→O(1) space. The first helps both styles; the space trim is mostly bottom-up.

Q7 How is "counting DP" different from a max/min DP?

The recurrence adds states instead of taking max/min, and base cases are usually non-zero (often dp[0]=1). A 0 seed makes the additive recurrence stay 0. Climbing Stairs and Coin Change II are counting DPs.

Q8 When does an inner loop appear inside the recurrence?

When the choice at a state is a range, not a fixed handful. In Minimum Difficulty of a Job Schedule you can assign 1, 2, 3… jobs to today, so the recurrence loops over split points and keeps the best. Coin Change loops over coins. This raises work-per-state and the time complexity.

Q9 Why is Kadane's algorithm considered dynamic programming?

Its current variable holds "the maximum subarray ending at the previous index" — an optimal sub-answer carried forward and extended, i.e. optimal substructure with reuse, expressed in a single rolling variable. That gives O(n) time and O(1) space. It only matters when negatives are present.

Key Takeaways#

DP = optimal substructure + overlapping subproblems. Reuse sub-answers; never solve the same state twice.
Spot it with two signals: it asks for an optimum/count, and earlier choices constrain later ones (ruling out greedy).
One framework, every problem: define dp(state), find the recurrence (hardest), set the base cases (easiest). Identical top-down and bottom-up.
Recursion + memo = top-down; loop + array = bottom-up. Write top-down first; convert for speed. Recursion without a memo isn't DP.
Complexity is mechanical: time = #states × work/state; space = #states. Count states by multiplying each variable's range.
State reduction drops a dimension (derive one variable from others) or trims space (rolling variables for static recurrences).
Know the named patterns: counting DP, inaction, Kadane, grid pathing, and string DP cover most of the field.

Every DP problem reduces to two questions: what is the state? (the minimal facts that describe where you are) and what is the recurrence? (how this state's answer is built from smaller ones). Nail those two and the memo, the base cases, and the bottom-up rewrite are all turn-the-crank.