Om's Brain

8. Dynamic Programming

42 min read

1️⃣ Core Idea

Try all choices → write the recursion → cache it. That’s DP.

Dynamic Programming is just recursion that stops repeating itself. You explore every choice like brute force, but the moment you notice you’re solving the same subproblem twice, you remember the answer (memoize) instead of recomputing it.

Nobody "invents the table"

The polished 2D table you see in editorials is the last step, not the first. What actually happens in your head is:

  1. What’s my choice at each step? → write a plain recursion
  2. I’m recomputing the same state → cache it (memoization).
  3. (optional) Flip it into a table (bottom-up).
  4. (optional) Shrink the table to a few variables (space optimization).

DP applies when the problem has both:

  • Overlapping subproblems — the same smaller problem is solved again and again (this is what memoization kills).
  • Optimal substructure — the best answer is built from the best answers of subproblems.

This continues straight from Backtracking

In Backtracking, the Count (int) recursion ended with return left + right. That is the seed of DP. Add a cache to that recursion and you have top-down DP. Same tree, fewer recomputations.

2️⃣ When to Think DP

✔️ Strong Signals

  • “Count the number of ways to …”
  • “Find the minimum / maximum cost / length / profit …”
  • “Is it possible to reach / partition / make …”
  • “Longest / shortest subsequence / path / substring …”
  • The problem screams “try all choices”, but pure brute force TLEs

✔️ Constraint Check

  • Answer is a single number (count / optimum / boolean), not a list of every configuration
  • The naive recursion is exponential, yet the number of distinct states is small (polynomial)
  • Greedy fails — a locally best choice doesn’t guarantee a globally best answer

Backtracking vs DP — the one-line difference

  • Backtracking: “Give me ALL valid answers” → enumerate every configuration.
  • DP: “Give me the COUNT or the OPTIMAL answer” → collapse repeated work.

They are the same recursion tree. DP just adds a cache because it only needs a number, not the full list.

3️⃣ How to Actually Write DP — The 4-Rung Ladder

Every DP problem is climbed on the same ladder. Learn the ladder once and every pattern below is just a new recurrence plugged into it.

┌─────────────────────────────────────────────────────────────┐
│                    THE 4-RUNG LADDER                        │
│                                                             │
│   1) RECURSION      Try all choices. Pure brute force.      │
│         │           (exponential — but correct)             │
│         ▼                                                   │
│   2) + MEMOIZATION  Cache each state in `dp`.  ✅ DP done.  │
│         │           (top-down)                              │
│         ▼                                                   │
│   3) TABULATION     Copy the recurrence, solve() → dp[].    │
│         │           (bottom-up, no recursion stack)         │
│         ▼                                                   │
│   4) SPACE OPTIMIZED  Keep only the rows you actually use.  │
│                       (prev / curr)                         │
└─────────────────────────────────────────────────────────────┘

We’ll climb it once, fully, on House Robber. Rob houses so that no two adjacent houses are robbed; maximize the loot.

House Robber — LC 198 🔥 📍

State: solve(i) = max money robbable from houses [0..i]. Choice: rob i (nums[i] + solve(i-2), skip the neighbor) or skip i (solve(i-1)). Base case: here I use i == 0 (returns nums[0]) so it converts cleanly to a table; the easy i < 0 version works if you stop at memoization.

// LC 198. House Robber
// State : max money from houses [0..i]
// Choice: rob i -> nums[i] + f(i-2)   |   skip i -> f(i-1)
class Solution {
public:
    // ---------- 1) Recursion + Memoization (entry point) ----------
    vector<int> dp;
    int solve(vector<int>& nums, int i) {
        // if (i < 0) return 0;            // easy base case (memo only)
        if (i == 0) return nums[0];        // tabulation-ready base case
        if (i < 0)  return 0;              // i-2 can fall below 0
        if (dp[i] != -1) return dp[i];
        int take    = nums[i] + solve(nums, i - 2);
        int notTake = solve(nums, i - 1);
        return dp[i] = max(take, notTake);
    }
    int rob(vector<int>& nums) {
        dp.assign(nums.size(), -1);
        return solve(nums, nums.size() - 1);
    }
 
    // ---------- 2) Tabulation (SAME body as solve(), just solve() -> dp[]) ----------
    int robTab(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp(n);
        dp[0] = nums[0];                          // base case i == 0
        dp[1] = max(nums[0], nums[1]);            // dp[i-2] with i-2 < 0 behaves as 0
        for (int i = 2; i < n; i++) {
            int take    = nums[i] + dp[i - 2];    // solve(i-2) -> dp[i-2]
            int notTake = dp[i - 1];              // solve(i-1) -> dp[i-1]
            dp[i] = max(take, notTake);
        }
        return dp[n - 1];
    }
 
    // ---------- 3) Space Optimized ----------
    int robOpt(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int curr = max(nums[i] + prev2, prev1);
            prev2 = prev1; prev1 = curr;
        }
        return prev1;
    }
};
// TC: O(n) all rungs   SC: O(n) memo/tab -> O(1) optimized

How each rung is born from the one above it

  • Memo → Tabulation: copy the recurrence body verbatim — same variable names (take, notTake, …), same expression — and change only solve(x) → dp[x]. Turn the base case into the initialization and loop i forward (opposite of recursion).
  • Tabulation → Space Opt: if dp[i] only reads dp[i-1] and dp[i-2], you never need the whole array — just carry those one or two values in prev1 / prev2.

4️⃣ The Base-Case Rule: i == -1 vs i == 0

Choosing the base case is where most people get stuck. There are two styles, and you pick based on how far up the ladder you plan to go.

Base caseWhen to useWhy
i == -1You’ll stop at recursion + memoizationDead simple — return the identity value. Always works.
i == 0You plan to tabulateA table can’t have index -1, so the first element must be handled explicitly. Trickier, but table-ready.
Easy    :  if (i == -1) return <identity>;     // count -> 1/0,  min -> 0/INF,  sum -> 0
Table   :  if (i == 0)  { ...handle element 0... }

When the base case gets confusing, use i == -1

The i == -1 (empty-prefix) base case often removes ugly edge logic entirely. Classic example: in Target Sum, the i == -1 base handles zeros in the array automatically (a 0 naturally doubles the ways), while the i == 0 version needs a special “return 2” case. Use the easy one to get a correct answer fast, switch to i == 0 only when you tabulate.

The identity value depends on what you combine

  • Counting (+): empty prefix → return 1 (one way: pick nothing) or 0 if the target isn’t met.
  • Minimum (min): unreachable → return INF (e.g. 1e8), reachable-with-nothing → 0.
  • Maximum (max): usually 0.
  • Feasibility (||): return true if target met, else false.

5️⃣ The Thinking Framework — State · Choices · Transition · Base

For any DP problem, answer these four questions in order. Once you can, the code writes itself.

1. STATE       What do the parameters of solve(...) mean?
               → the smallest set of variables that fully describe a subproblem
               e.g. solve(i) = answer considering items [0..i]

2. CHOICES     What decisions can I make from this state?
               → take / not-take, pick a coin, cut here, jump 1 or 2, ...

3. TRANSITION  How do I combine the results of those choices?
               → COUNT ways  = a + b        (sum the branches)
               → MINIMUM     = min(a, b)
               → MAXIMUM     = max(a, b)
               → FEASIBLE?   = a || b

4. BASE CASE   Smallest subproblem I can answer directly?
               → i == -1 (easy) or i == 0 (table-ready)  — see point 4

The combine step is the problem type

The only thing that changes between “count ways”, “min cost”, and “is it possible” is step 3. Same state, same choices — swap + for min for ||, and you’ve switched problems. This is why one pattern solves dozens of questions.

6️⃣ The 5 Universal Patterns (Master Lens) 🧭

Almost every DP problem is one of five shapes. Learn to spot the shape and you already know the recurrence. The 9 detailed patterns below are all concrete instances of these five.

                         ┌───────────────────────────┐
                         │   What is the problem?    │
                         └─────────────┬─────────────┘
                                       │
   ┌───────────────┬───────────────┬───┴───────────┬───────────────┬───────────────┐
   ▼               ▼               ▼               ▼               ▼
1) MIN / MAX     2) DISTINCT     3) MERGING       4) DP ON        5) DECISION
   TO A TARGET      WAYS            INTERVALS         STRINGS         MAKING
   min/max cost     count paths     split [i..j]      align 2 idx     take/skip w/ state
   Coin Change      Unique Paths    Burst Balloons    LCS, Edit Dist  Buy/Sell Stock
#PatternSignalCombineTransition shape
1Min/Max to Target”min/max cost/steps to reach N / make amount”min/maxf(t) = best over choice c of cost(c) + f(t - c)
2Distinct Ways”how many ways to reach / decode / total”+f(t) = Σ f(t - choice)
3Merging Intervals”solve on a range, split at some k”min/maxf(i,j) = best over k of f(i,k) + f(k,j) + cost
4DP on Strings”two sequences / one sequence, match characters”variescompare a[i] vs b[j] → match or skip
5Decision Making”buy/sell, rob/skip, with a state that carries”maxf(i, state) = best over actions from state

🔻 Generic Top-Down Template (memoization)

int solve(State s) {
    if (base_case(s)) return identity;      // §4: i==-1 easy, or i==0 table-ready
    if (dp[s] != -1) return dp[s];          // memo hit
 
    int best = identity;                    // 0 for count, INF for min, -INF/0 for max
    for (choice c : choices(s))             // try every choice
        best = combine(best, value(c) + solve(next(s, c)));   // + / min / max / ||
 
    return dp[s] = best;
}

🔺 Generic Bottom-Up Template (tabulation)

// 1. init base states in dp
// 2. iterate states in an order where dependencies are already filled
for (State s : order_low_to_high) {
    dp[s] = identity;
    for (choice c : choices(s))
        dp[s] = combine(dp[s], value(c) + dp[next(s, c)]);
}
return dp[target_state];

The whole guide in one sentence

Pick the state, list the choices, choose the combine (+ / min / max / ||), write the base case — then climb the ladder. Everything below is this idea with different states.

7️⃣ Pattern 1 — Linear / 1D DP

💡 Signal: a decision at each index of a 1D array, where the answer at i depends on a fixed few earlier indices (i-1, i-2). The Fibonacci shape.

State is a single index. This is the gentlest pattern and the best place to drill the ladder. (The teaching example, House Robber, lives in point 3.)

Climbing Stairs — LC 70 🔥

Climb 1 or 2 steps at a time. Count distinct ways to reach step n.

State: solve(n) = ways to reach step n. Transition: f(n) = f(n-1) + f(n-2) (came from one below or two below). Combine: + (counting).

// LC 70. Climbing Stairs
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<int> dp;
    int solve(int n) {
        // if (n < 0) return 0;           // easy base case
        if (n <= 1) return 1;             // f(0)=f(1)=1
        if (dp[n] != -1) return dp[n];
        return dp[n] = solve(n - 1) + solve(n - 2);
    }
    int climbStairs(int n) {
        dp.assign(n + 1, -1);
        return solve(n);
    }
 
    // ---------- 2) Tabulation ----------
    int climbTab(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
 
    // ---------- 3) Space Optimized ----------
    int climbOpt(int n) {
        int prev2 = 1, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1; prev1 = curr;
        }
        return prev1;
    }
};
// TC: O(n)   SC: O(n) -> O(1)

This is literally Fibonacci

Climbing Stairs, Fibonacci, and Tribonacci are the same recurrence with different arity. If you see f(n) = f(n-1) + f(n-2), you’re done.

Min Cost Climbing Stairs — LC 746 📍

Each step has a cost. From step i you climb 1 or 2. Pay cost[i] to stand on i. Reach the top (just past the last step) for the minimum total.

State: solve(i) = min cost to stand on step i = cost[i] + min(solve(i-1), solve(i-2)). The top is reachable from the last two steps → answer is min(solve(n-1), solve(n-2)).

// LC 746. Min Cost Climbing Stairs
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<int> dp;
    int solve(vector<int>& cost, int i) {
        if (i == 0 || i == 1) return cost[i];   // can start at step 0 or 1 for free
        if (dp[i] != -1) return dp[i];
        return dp[i] = cost[i] + min(solve(cost, i - 1), solve(cost, i - 2));
    }
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        dp.assign(n, -1);
        return min(solve(cost, n - 1), solve(cost, n - 2));   // top is above the last step
    }
 
    // ---------- 2) Tabulation ----------
    int minCostTab(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[0] = cost[0]; dp[1] = cost[1];
        for (int i = 2; i < n; i++) dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
        return min(dp[n - 1], dp[n - 2]);
    }
 
    // ---------- 3) Space Optimized ----------
    int minCostOpt(vector<int>& cost) {
        int n = cost.size();
        int prev2 = cost[0], prev1 = cost[1];
        for (int i = 2; i < n; i++) {
            int curr = cost[i] + min(prev1, prev2);
            prev2 = prev1; prev1 = curr;
        }
        return min(prev1, prev2);
    }
};
// TC: O(n)   SC: O(n) -> O(1)

House Robber II — LC 213 📍

Same as House Robber, but the houses are in a circle — the first and last are adjacent.

Trick: a circle just means the first and last can’t both be robbed. So run the linear House Robber twice: once on [0..n-2] (skip the last) and once on [1..n-1] (skip the first), and take the max.

// LC 213. House Robber II
class Solution {
public:
    // Linear House Robber on nums[lo..hi] (space-optimized form from LC 198)
    int robLinear(vector<int>& nums, int lo, int hi) {
        int prev2 = 0, prev1 = 0;
        for (int i = lo; i <= hi; i++) {
            int curr = max(nums[i] + prev2, prev1);
            prev2 = prev1; prev1 = curr;
        }
        return prev1;
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        // circle => can't take both ends: rob [0..n-2] OR [1..n-1]
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }
};
// TC: O(n)   SC: O(1)

Turn a hard constraint into two easy subproblems

“Circular” / “can’t use both X and Y” problems often reduce to solving the linear version twice with one endpoint removed each time. Remember this move.

Maximum Subarray — LC 53 🔥 📍

Find the contiguous subarray with the largest sum. This is Kadane’s algorithm, but it’s really 1D DP.

State: dp[i] = max sum of a subarray ending exactly at i = max(nums[i], nums[i] + dp[i-1]) — either start fresh at i, or extend the best subarray ending at i-1. Answer is the max over all i.

// LC 53. Maximum Subarray
class Solution {
public:
    // ---------- 2) Tabulation (dp[i] = best subarray ending at i) ----------
    int maxSubArrayTab(vector<int>& nums) {
        int n = nums.size(), best = nums[0];
        vector<int> dp(n);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);   // start fresh vs extend
            best  = max(best, dp[i]);
        }
        return best;
    }
 
    // ---------- 3) Space Optimized (classic Kadane) ----------
    int maxSubArray(vector<int>& nums) {
        int best = nums[0], curr = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            curr = max(nums[i], nums[i] + curr);         // dp[i] depends only on dp[i-1]
            best = max(best, curr);
        }
        return best;
    }
};
// TC: O(n)   SC: O(n) -> O(1)

Why the entry point here is iterative, not memo

The answer is the max over all ending indices, and each dp[i] only needs dp[i-1]. A top-down memo would just be an awkward wrapper around this loop, so tabulation / Kadane is the natural home. Not every problem needs all four rungs — use the simplest one that’s correct.

8️⃣ Pattern 2 — Grid / 2D DP

💡 Signal: move through a grid (usually down / right), counting paths or optimizing a path cost. State is (row, col).

The recurrence looks back at the cell above and the cell to the left. Because each row only needs the previous row, these all compress to O(cols) space.

Unique Paths — LC 62 🔥

Robot at top-left, moves only down or right, count paths to bottom-right.

State: solve(i,j) = paths from (0,0) to (i,j) = solve(i-1,j) + solve(i,j-1). Combine: + (distinct ways).

// LC 62. Unique Paths
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(int i, int j) {
        // if (i < 0 || j < 0) return 0;   // easy base case
        if (i == 0 && j == 0) return 1;    // reached start
        if (i < 0 || j < 0)   return 0;    // fell off the grid
        if (dp[i][j] != -1) return dp[i][j];
        int top  = solve(i - 1, j);
        int left = solve(i, j - 1);
        return dp[i][j] = top + left;
    }
    int uniquePaths(int m, int n) {
        dp.assign(m, vector<int>(n, -1));
        return solve(m - 1, n - 1);
    }
 
    // ---------- 2) Tabulation ----------
    int uniquePathsTab(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) { dp[i][j] = 1; continue; }   // base case
                int top  = (i > 0) ? dp[i - 1][j] : 0;   // solve(i-1,j) -> dp[i-1][j] (0 if off-grid)
                int left = (j > 0) ? dp[i][j - 1] : 0;   // solve(i,j-1) -> dp[i][j-1]
                dp[i][j] = top + left;
            }
        return dp[m - 1][n - 1];
    }
 
    // ---------- 3) Space Optimized (one row) ----------
    int uniquePathsOpt(int m, int n) {
        vector<int> prev(n, 0);
        for (int i = 0; i < m; i++) {
            vector<int> curr(n, 0);
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) { curr[j] = 1; continue; }
                int top  = prev[j];                       // cell above
                int left = (j > 0) ? curr[j - 1] : 0;     // cell to the left
                curr[j] = top + left;
            }
            prev = curr;
        }
        return prev[n - 1];
    }
};
// TC: O(m*n)   SC: O(m*n) -> O(n)

Unique Paths II — LC 63 📍

Same, but some cells are obstacles (grid[i][j] == 1). An obstacle contributes 0 paths.

One extra line vs Unique Paths: short-circuit any obstacle cell to 0.

// LC 63. Unique Paths II
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || j < 0)      return 0;
        if (grid[i][j] == 1)     return 0;      // obstacle blocks the path
        if (i == 0 && j == 0)    return 1;
        if (dp[i][j] != -1) return dp[i][j];
        int top  = solve(grid, i - 1, j);
        int left = solve(grid, i, j - 1);
        return dp[i][j] = top + left;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        dp.assign(m, vector<int>(n, -1));
        return solve(grid, m - 1, n - 1);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int uniquePathsTab(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)  { dp[i][j] = 0; continue; }   // obstacle
                if (i == 0 && j == 0) { dp[i][j] = 1; continue; }   // base case
                int top  = (i > 0) ? dp[i - 1][j] : 0;   // solve(i-1,j) -> dp[i-1][j]
                int left = (j > 0) ? dp[i][j - 1] : 0;   // solve(i,j-1) -> dp[i][j-1]
                dp[i][j] = top + left;
            }
        return dp[m - 1][n - 1];
    }
 
    // ---------- 3) Space Optimized ----------
    int uniquePathsOpt(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> prev(n, 0);
        for (int i = 0; i < m; i++) {
            vector<int> curr(n, 0);
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)  { curr[j] = 0; continue; }
                if (i == 0 && j == 0) { curr[j] = 1; continue; }
                int top  = prev[j];
                int left = (j > 0) ? curr[j - 1] : 0;
                curr[j] = top + left;
            }
            prev = curr;
        }
        return prev[n - 1];
    }
};
// TC: O(m*n)   SC: O(m*n) -> O(n)

Minimum Path Sum — LC 64 🔥

Each cell has a cost. Find the minimum sum path from top-left to bottom-right.

Same state, swap + for min: solve(i,j) = grid[i][j] + min(solve(i-1,j), solve(i,j-1)).

// LC 64. Minimum Path Sum
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<vector<int>>& grid, int i, int j) {
        if (i == 0 && j == 0) return grid[0][0];
        if (i < 0 || j < 0)   return INT_MAX;    // invalid direction (won't be chosen)
        if (dp[i][j] != -1) return dp[i][j];
        int top  = solve(grid, i - 1, j);
        int left = solve(grid, i, j - 1);
        return dp[i][j] = grid[i][j] + min(top, left);
    }
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        dp.assign(m, vector<int>(n, -1));
        return solve(grid, m - 1, n - 1);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int minPathSumTab(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) { dp[i][j] = grid[0][0]; continue; }   // base case
                int top  = (i > 0) ? dp[i - 1][j] : INT_MAX;   // solve(i-1,j) -> dp[i-1][j]
                int left = (j > 0) ? dp[i][j - 1] : INT_MAX;   // solve(i,j-1) -> dp[i][j-1]
                dp[i][j] = grid[i][j] + min(top, left);
            }
        return dp[m - 1][n - 1];
    }
 
    // ---------- 3) Space Optimized ----------
    int minPathSumOpt(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> prev(n, 0);
        for (int i = 0; i < m; i++) {
            vector<int> curr(n, 0);
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) { curr[j] = grid[0][0]; continue; }
                int top  = (i > 0) ? prev[j]     : INT_MAX;
                int left = (j > 0) ? curr[j - 1] : INT_MAX;
                curr[j] = grid[i][j] + min(top, left);
            }
            prev = curr;
        }
        return prev[n - 1];
    }
};
// TC: O(m*n)   SC: O(m*n) -> O(n)

Distinct-ways vs min-cost — same skeleton

Unique Paths and Minimum Path Sum have the identical state and moves. The only difference is the combine step: + (count all paths) vs min (best single path). This is the §5 lesson made concrete.

Minimum Falling Path Sum — LC 931 📍

Fall from any cell in row 0 to the bottom. From (i,j) you drop to (i+1, j-1), (i+1, j), or (i+1, j+1). Minimize the total.

State: solve(i,j) = min falling sum from the top ending at (i,j) = mat[i][j] + min of the three cells directly above. Answer = min over the last row.

// LC 931. Minimum Falling Path Sum
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<vector<int>>& mat, int i, int j) {
        int n = mat.size();
        if (j < 0 || j >= n) return INT_MAX;     // fell off the side
        if (i == 0) return mat[0][j];            // top row: cost is the cell itself
        if (dp[i][j] != INT_MAX) return dp[i][j];
        int a = solve(mat, i - 1, j - 1);
        int b = solve(mat, i - 1, j);
        int c = solve(mat, i - 1, j + 1);
        return dp[i][j] = mat[i][j] + min({a, b, c});
    }
    int minFallingPathSum(vector<vector<int>>& mat) {
        int n = mat.size();
        dp.assign(n, vector<int>(n, INT_MAX));   // INT_MAX sentinel (sums can be negative)
        int best = INT_MAX;
        for (int j = 0; j < n; j++) best = min(best, solve(mat, n - 1, j));
        return best;
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int minFallingTab(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int j = 0; j < n; j++) dp[0][j] = mat[0][j];      // base case i == 0
        for (int i = 1; i < n; i++)
            for (int j = 0; j < n; j++) {
                int a = (j > 0)     ? dp[i - 1][j - 1] : INT_MAX;   // solve(i-1,j-1)
                int b =               dp[i - 1][j];                 // solve(i-1,j)
                int c = (j < n - 1) ? dp[i - 1][j + 1] : INT_MAX;   // solve(i-1,j+1)
                dp[i][j] = mat[i][j] + min({a, b, c});
            }
        return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
 
    // ---------- 3) Space Optimized ----------
    int minFallingOpt(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<int> prev(mat[0].begin(), mat[0].end());
        for (int i = 1; i < n; i++) {
            vector<int> curr(n);
            for (int j = 0; j < n; j++) {
                int a = (j > 0)     ? prev[j - 1] : INT_MAX;
                int b =               prev[j];
                int c = (j < n - 1) ? prev[j + 1] : INT_MAX;
                curr[j] = mat[i][j] + min({a, b, c});
            }
            prev = curr;
        }
        return *min_element(prev.begin(), prev.end());
    }
};
// TC: O(n^2)   SC: O(n^2) -> O(n)

Sentinel choice matters

Values here can be negative, so -1 is a valid answer and can’t be the “not computed” marker. Use INT_MAX as both the out-of-bounds cost and the memo sentinel. Always pick a sentinel outside the range of real answers.

9️⃣ Pattern 3 — Distinct Ways / Counting

💡 Signal: “how many ways to …”. You never optimize — you sum the ways from every valid choice.

Combine is always +. The base case returns 1 for a valid completion and 0 for a dead end.

Decode Ways — LC 91 🔥 📍

'A'..'Z' map to "1".."26". Count ways to decode a digit string.

State: solve(i) = ways to decode the prefix s[0..i]. Choices: take one digit (s[i], if not '0') → solve(i-1); take two digits (s[i-1..i], if in 10..26) → solve(i-2).

// LC 91. Decode Ways
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<int> dp;
    int solve(string& s, int i) {
        if (i < 0) return 1;                    // empty prefix = one valid decoding
        if (i == 0) return s[0] == '0' ? 0 : 1;
        if (dp[i] != -1) return dp[i];
        int ways = 0;
        if (s[i] != '0') ways += solve(s, i - 1);              // one digit
        int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (two >= 10 && two <= 26) ways += solve(s, i - 2);   // two digits
        return dp[i] = ways;
    }
    int numDecodings(string s) {
        int n = s.size();
        dp.assign(n, -1);
        return solve(s, n - 1);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]; keep 0-indexing) ----------
    int numDecodingsTab(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        dp[0] = s[0] == '0' ? 0 : 1;            // base case i == 0
        for (int i = 1; i < n; i++) {
            int ways = 0;
            if (s[i] != '0') ways += dp[i - 1];                    // solve(i-1) -> dp[i-1]
            int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (two >= 10 && two <= 26)
                ways += (i - 2 >= 0) ? dp[i - 2] : 1;              // solve(i-2); i-2<0 -> base 1
            dp[i] = ways;
        }
        return dp[n - 1];
    }
 
    // ---------- 3) Space Optimized ----------
    int numDecodingsOpt(string s) {
        int n = s.size();
        int prev2 = 1;                          // dp[i-2] with i-2 == -1 -> 1
        int prev1 = (s[0] == '0' ? 0 : 1);      // dp[0]
        for (int i = 1; i < n; i++) {
            int ways = 0;
            if (s[i] != '0') ways += prev1;
            int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (two >= 10 && two <= 26) ways += prev2;
            prev2 = prev1; prev1 = ways;
        }
        return prev1;
    }
};
// TC: O(n)   SC: O(n) -> O(1)

Zeros are the whole difficulty of Decode Ways

'0' cannot stand alone (no letter maps to 0), so a single '0' only survives as part of 10 or 20. Every “off by one” bug here is a mishandled '0'. Test "06", "100", "0".

Combination Sum IV — LC 377 📍

Count combinations that sum to target, where order matters ([1,2] and [2,1] are different) and numbers can repeat.

State: solve(t) = ordered ways to make t = Σ solve(t - x) for each x in nums.

// LC 377. Combination Sum IV
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<long long> dp;                       // long long: intermediate sums can overflow int
    long long solve(vector<int>& nums, int target) {
        if (target == 0) return 1;
        if (dp[target] != -1) return dp[target];
        long long ways = 0;
        for (int x : nums)
            if (target - x >= 0) ways += solve(nums, target - x);
        return dp[target] = ways;
    }
    int combinationSum4(vector<int>& nums, int target) {
        dp.assign(target + 1, -1);
        return (int)solve(nums, target);
    }
 
    // ---------- 2) Tabulation (target OUTER, nums INNER => ORDERED) ----------
    int combinationSum4Tab(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        for (int t = 1; t <= target; t++)       // build every total
            for (int x : nums)                  // try each number as the LAST added
                if (t - x >= 0) dp[t] += dp[t - x];
        return dp[target];
    }
};
// TC: O(target * n)   SC: O(target)

Order matters here — remember it for Pattern 5

Because we ask solve(t - x) for every x at every total, [1,2] and [2,1] are counted separately. In the tabulation, the target loop is outer. Contrast this with Coin Change II (§1️⃣1️⃣) where the coin loop is outer and order does not matter. Same code shape, one loop swapped, completely different meaning.

Number of Dice Rolls With Target Sum — LC 1155 📍

n dice with k faces each. Count ways the faces sum to target (mod 1e9+7).

State: solve(dice, t) = ways to make t using dice dice = Σ_{face=1..k} solve(dice-1, t-face).

// LC 1155. Number of Dice Rolls With Target Sum
class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<vector<int>> dp;
    int solve(int dice, int k, int target) {
        if (dice == 0)  return target == 0 ? 1 : 0;   // used all dice: valid iff sum hit exactly
        if (target <= 0) return 0;
        if (dp[dice][target] != -1) return dp[dice][target];
        long long ways = 0;
        for (int face = 1; face <= k; face++)
            if (target - face >= 0)
                ways = (ways + solve(dice - 1, k, target - face)) % MOD;
        return dp[dice][target] = ways;
    }
    int numRollsToTarget(int n, int k, int target) {
        dp.assign(n + 1, vector<int>(target + 1, -1));
        return solve(n, k, target);
    }
};
// TC: O(n * target * k)   SC: O(n * target)

🔟 Pattern 4 — 0/1 Knapsack (Subsequences)

💡 Signal: a set of items, each usable at most once, and a budget / capacity / target. At every item you decide take or don’t take.

State: solve(i, cap) — considering items [0..i] with remaining capacity/target cap. The template that never changes:

notTake = solve(i-1, cap)                       // skip item i
take    = (fits) ? value + solve(i-1, cap - w)  // take item i, move to i-1
                 : identity
answer  = combine(take, notTake)                // max / +/ ||

0/1 means "take moves to i-1"

Each item is used once, so after taking it we recurse on i-1. (In Unbounded Knapsack — §1️⃣1️⃣ — take stays on i.) This single index is the whole difference between the two families.

0/1 Knapsack — GfG 🔥

Items with weight wt[i] and value val[i]. Maximize value without exceeding capacity W.

// GfG. 0/1 Knapsack
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<int>& val, vector<int>& wt, int i, int W) {
        // if (i < 0) return 0;                        // easy base case
        if (i == 0) return wt[0] <= W ? val[0] : 0;    // take item 0 only if it fits
        if (dp[i][W] != -1) return dp[i][W];
        int notTake = solve(val, wt, i - 1, W);
        int take = 0;
        if (wt[i] <= W) take = val[i] + solve(val, wt, i - 1, W - wt[i]);
        return dp[i][W] = max(take, notTake);
    }
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        int n = val.size();
        dp.assign(n, vector<int>(W + 1, -1));
        return solve(val, wt, n - 1, W);
    }
 
    // ---------- 2) Tabulation ----------
    int knapsackTab(int W, vector<int>& val, vector<int>& wt) {
        int n = val.size();
        vector<vector<int>> dp(n, vector<int>(W + 1, 0));
        for (int w = 0; w <= W; w++) dp[0][w] = (wt[0] <= w) ? val[0] : 0;
        for (int i = 1; i < n; i++)
            for (int w = 0; w <= W; w++) {
                int notTake = dp[i - 1][w];
                int take = (wt[i] <= w) ? val[i] + dp[i - 1][w - wt[i]] : 0;
                dp[i][w] = max(take, notTake);
            }
        return dp[n - 1][W];
    }
 
    // ---------- 3) Space Optimized (one row) ----------
    int knapsackOpt(int W, vector<int>& val, vector<int>& wt) {
        int n = val.size();
        vector<int> prev(W + 1, 0);
        for (int w = 0; w <= W; w++) prev[w] = (wt[0] <= w) ? val[0] : 0;
        for (int i = 1; i < n; i++) {
            vector<int> curr(W + 1, 0);
            for (int w = 0; w <= W; w++) {
                int notTake = prev[w];
                int take = (wt[i] <= w) ? val[i] + prev[w - wt[i]] : 0;
                curr[w] = max(take, notTake);
            }
            prev = curr;
        }
        return prev[W];
    }
};
// TC: O(n*W)   SC: O(n*W) -> O(W)

Partition Equal Subset Sum — LC 416 🔥 📍

Can the array be split into two subsets with equal sum?

Reframe: if total is odd → impossible. Otherwise, ask “is there a subset summing to total/2?” — a 0/1 knapsack with a boolean combine (||).

// LC 416. Partition Equal Subset Sum
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    bool solve(vector<int>& nums, int i, int target) {
        if (target == 0) return true;              // found a subset
        if (i == 0) return nums[0] == target;
        if (dp[i][target] != -1) return dp[i][target];
        bool notTake = solve(nums, i - 1, target);
        bool take = false;
        if (nums[i] <= target) take = solve(nums, i - 1, target - nums[i]);
        return dp[i][target] = (take || notTake);
    }
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2) return false;               // odd total can't split evenly
        int target = total / 2, n = nums.size();
        dp.assign(n, vector<int>(target + 1, -1));
        return solve(nums, n - 1, target);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    bool canPartitionTab(vector<int>& nums) {
        int total = 0; for (int x : nums) total += x;
        if (total % 2) return false;
        int target = total / 2, n = nums.size();
        vector<vector<char>> dp(n, vector<char>(target + 1, false));
        for (int i = 0; i < n; i++) dp[i][0] = true;          // target == 0 -> true
        if (nums[0] <= target) dp[0][nums[0]] = true;         // base case i == 0
        for (int i = 1; i < n; i++)
            for (int t = 1; t <= target; t++) {
                bool notTake = dp[i - 1][t];                            // solve(i-1, t)
                bool take = (nums[i] <= t) ? dp[i - 1][t - nums[i]] : false;
                dp[i][t] = take || notTake;
            }
        return dp[n - 1][target];
    }
 
    // ---------- 3) Space Optimized ----------
    bool canPartitionOpt(vector<int>& nums) {
        int total = 0; for (int x : nums) total += x;
        if (total % 2) return false;
        int target = total / 2, n = nums.size();
        vector<char> prev(target + 1, false);
        prev[0] = true;
        if (nums[0] <= target) prev[nums[0]] = true;
        for (int i = 1; i < n; i++) {
            vector<char> curr(target + 1, false);
            curr[0] = true;
            for (int t = 1; t <= target; t++) {
                bool notTake = prev[t];
                bool take = (nums[i] <= t) ? prev[t - nums[i]] : false;
                curr[t] = take || notTake;
            }
            prev = curr;
        }
        return prev[target];
    }
};
// TC: O(n*sum)   SC: O(n*sum) -> O(sum)

"Equal partition", "subset sum", "can we make X" are all one problem

They’re 0/1 knapsack with a boolean target. Same for Minimum Subset Sum Difference (find all reachable subset sums, then minimize |total - 2*s|) — see the tracker.

Target Sum — LC 494 🔥 💀

Assign + or - to each number so the expression equals target. Count the assignments.

Reframe (the clever step): let P = positives, N = negatives. P - N = target and P + N = total, so P = (total + target) / 2. Now it’s “count subsets summing to P” — a counting 0/1 knapsack.

// LC 494. Target Sum
class Solution {
public:
    // ---------- 1) Recursion + Memoization (easy i==-1 base handles 0s automatically) ----------
    vector<vector<int>> dp;
    int solve(vector<int>& nums, int i, int t) {
        if (i < 0) return t == 0 ? 1 : 0;          // empty prefix: 1 way iff nothing left to make
        if (dp[i][t] != -1) return dp[i][t];
        int notTake = solve(nums, i - 1, t);
        int take = (nums[i] <= t) ? solve(nums, i - 1, t - nums[i]) : 0;
        return dp[i][t] = take + notTake;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0; for (int x : nums) total += x;
        // need P = (total + target) / 2 to be a non-negative integer
        if (abs(target) > total || (total + target) % 2) return 0;
        int subset = (total + target) / 2, n = nums.size();
        dp.assign(n, vector<int>(subset + 1, -1));
        return solve(nums, n - 1, subset);
    }
 
    // ---------- 2) Tabulation (needs the trickier i==0 base: note the zero handling) ----------
    int findTargetSumWaysTab(vector<int>& nums, int target) {
        int total = 0; for (int x : nums) total += x;
        if (abs(target) > total || (total + target) % 2) return 0;
        int subset = (total + target) / 2, n = nums.size();
        vector<vector<int>> dp(n, vector<int>(subset + 1, 0));
        dp[0][0] = (nums[0] == 0) ? 2 : 1;             // {} and {0} both make 0
        if (nums[0] != 0 && nums[0] <= subset) dp[0][nums[0]] = 1;
        for (int i = 1; i < n; i++)
            for (int t = 0; t <= subset; t++) {
                int notTake = dp[i - 1][t];
                int take = (nums[i] <= t) ? dp[i - 1][t - nums[i]] : 0;
                dp[i][t] = take + notTake;
            }
        return dp[n - 1][subset];
    }
};
// TC: O(n*subset)   SC: O(n*subset)

Target Sum is the poster child for the i == -1 base case

With i == -1 (empty-prefix), a 0 in the array is handled for free: at that index both “take” (subtract 0) and “not take” recurse to the same state, naturally doubling the count. The i == 0 tabulation base must special-case it with return 2. When zeros make your base case ugly, reach for i == -1. (See §4.)

1️⃣1️⃣ Pattern 5 — Unbounded Knapsack

💡 Signal: same as 0/1 knapsack, but each item can be used unlimited times (coins, rods, ropes).

The one change from 0/1: when you take an item, you stay on the same index i (so you can take it again) instead of moving to i-1.

0/1        :  take -> ... + solve(i-1, cap - w)     // each item once
UNBOUNDED  :  take -> ... + solve(i,   cap - w)     // reuse allowed

Coin Change — LC 322 🔥 📍

Fewest coins to make amount (coins reusable). Return -1 if impossible.

Combine: min (fewest). Identity for “impossible”: a big sentinel like 1e8.

// LC 322. Coin Change
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<int>& coins, int i, int amt) {
        // if (i < 0) return amt == 0 ? 0 : 1e8;   // easy base case
        if (i == 0) {                              // only coin 0 is available
            if (amt % coins[0] == 0) return amt / coins[0];
            return 1e8;                            // can't form amt with coin 0 alone
        }
        if (dp[i][amt] != -1) return dp[i][amt];
        int notTake = solve(coins, i - 1, amt);
        int take = 1e8;
        if (coins[i] <= amt) take = 1 + solve(coins, i, amt - coins[i]);   // stay at i (reuse)
        return dp[i][amt] = min(take, notTake);
    }
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        dp.assign(n, vector<int>(amount + 1, -1));
        int ans = solve(coins, n - 1, amount);
        return ans >= 1e8 ? -1 : ans;
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int coinChangeTab(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n, vector<int>(amount + 1, 0));
        for (int amt = 0; amt <= amount; amt++)             // base case i == 0
            dp[0][amt] = (amt % coins[0] == 0) ? amt / coins[0] : (int)1e8;
        for (int i = 1; i < n; i++)
            for (int amt = 0; amt <= amount; amt++) {
                int notTake = dp[i - 1][amt];                        // solve(i-1, amt)
                int take = 1e8;
                if (coins[i] <= amt) take = 1 + dp[i][amt - coins[i]];   // solve(i, ...) -> dp[i][...]
                dp[i][amt] = min(take, notTake);
            }
        int ans = dp[n - 1][amount];
        return ans >= 1e8 ? -1 : ans;
    }
 
    // ---------- 3) Space Optimized ----------
    int coinChangeOpt(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> prev(amount + 1);
        for (int amt = 0; amt <= amount; amt++)
            prev[amt] = (amt % coins[0] == 0) ? amt / coins[0] : (int)1e8;
        for (int i = 1; i < n; i++) {
            vector<int> curr(amount + 1);
            for (int amt = 0; amt <= amount; amt++) {
                int notTake = prev[amt];
                int take = 1e8;
                if (coins[i] <= amt) take = 1 + curr[amt - coins[i]];   // curr = dp[i] (reuse)
                curr[amt] = min(take, notTake);
            }
            prev = curr;
        }
        int ans = prev[amount];
        return ans >= 1e8 ? -1 : ans;
    }
};
// TC: O(n*amount)   SC: O(n*amount) -> O(amount)

The unbounded tell: dp[i][amt - coin], not dp[i-1][amt - coin]

Because “take” stays on i, tabulation reads the current row (dp[i][...] / curr[...]), which was already filled for smaller amounts. That’s exactly how a coin gets reused. In 0/1 it would read dp[i-1][...].

Coin Change II — LC 518 🔥 📍

Count the number of combinations that make amount (order doesn’t matter).

Combine: + (counting). Same unbounded structure — take stays on i.

// LC 518. Coin Change II
class Solution {
public:
    // ---------- 1) Recursion + Memoization ----------
    vector<vector<int>> dp;
    int solve(vector<int>& coins, int i, int amt) {
        // if (i < 0) return amt == 0 ? 1 : 0;    // easy base case
        if (i == 0) return (amt % coins[0] == 0) ? 1 : 0;   // only coin 0
        if (dp[i][amt] != -1) return dp[i][amt];
        int notTake = solve(coins, i - 1, amt);
        int take = 0;
        if (coins[i] <= amt) take = solve(coins, i, amt - coins[i]);   // stay at i (reuse)
        return dp[i][amt] = take + notTake;
    }
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        dp.assign(n, vector<int>(amount + 1, -1));
        return solve(coins, n - 1, amount);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int changeTab(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n, vector<int>(amount + 1, 0));
        for (int amt = 0; amt <= amount; amt++)             // base case i == 0
            dp[0][amt] = (amt % coins[0] == 0) ? 1 : 0;
        for (int i = 1; i < n; i++)
            for (int amt = 0; amt <= amount; amt++) {
                int notTake = dp[i - 1][amt];                    // solve(i-1, amt)
                int take = 0;
                if (coins[i] <= amt) take = dp[i][amt - coins[i]];   // solve(i, ...) -> dp[i][...]
                dp[i][amt] = take + notTake;
            }
        return dp[n - 1][amount];
    }
 
    // ---------- 3) Space Optimized (1D, coin loop OUTER) ----------
    int changeOpt(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins)                       // coin OUTER => combinations (unordered)
            for (int amt = coin; amt <= amount; amt++)
                dp[amt] += dp[amt - coin];
        return dp[amount];
    }
};
// TC: O(n*amount)   SC: O(n*amount) -> O(amount)

The loop-order trap: combinations vs permutations

In the 1D form, coin loop outside counts combinations (Coin Change II — {1,2} == {2,1}). Swapping to amount loop outside counts permutations (that’s exactly Combination Sum IV, §9️⃣). Same three lines, one swap, completely different answer. Know which one the problem wants.

1️⃣2️⃣ Pattern 6 — Longest Increasing Subsequence (LIS)

💡 Signal: “longest increasing / chain / divisible subsequence” — pick elements in order under a “next must beat current” rule.

Cleanest state: solve(i) = length of the LIS that ends exactly at index i. The answer is the max over all i. This state makes recursion and tabulation line up perfectly.

Longest Increasing Subsequence — LC 300 🔥 📍

// LC 300. Longest Increasing Subsequence
class Solution {
public:
    // ---------- 1) Recursion + Memoization (dp[i] = LIS ending exactly at i) ----------
    vector<int> dp;
    int solve(vector<int>& nums, int i) {
        if (dp[i] != -1) return dp[i];
        int best = 1;                                // element i alone
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                best = max(best, 1 + solve(nums, j));
        return dp[i] = best;
    }
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        dp.assign(n, -1);
        int ans = 1;
        for (int i = 0; i < n; i++) ans = max(ans, solve(nums, i));
        return ans;
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int lengthOfLISTab(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<int> dp(n, 1);                        // base: each element alone = length 1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], 1 + dp[j]);   // solve(j) -> dp[j]
            ans = max(ans, dp[i]);
        }
        return ans;
    }
 
    // ---------- 3) O(n log n): patience sorting + binary search ----------
    int lengthOfLISBinary(vector<int>& nums) {
        vector<int> tails;                           // tails[k] = smallest tail of an LIS of length k+1
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);   // x extends the longest run
            else *it = x;                                // shrink a tail to keep options open
        }
        return tails.size();
    }
};
// TC: O(n^2) DP  |  O(n log n) binary   SC: O(n)

The O(n log n) trick in one line

Keep an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, binary-search the first tail >= x and overwrite it (or append if x beats all). tails stays sorted; its length is the LIS. It doesn’t store an actual subsequence, just the length.

Same skeleton, new rule

Swap the nums[j] < nums[i] test and you get the whole family: Largest Divisible Subset (nums[i] % nums[j] == 0, sort first), Russian Doll Envelopes (2D LIS), Number of LIS (carry a count alongside the length). See the tracker.

1️⃣3️⃣ Pattern 7 — DP on Strings

💡 Signal: two strings (or one string vs its reverse), compare characters at two pointers (i, j), decide match or skip.

Indexing convention: let solve(i, j) work on the prefixes of length i and j (so s[i-1] is the current char). Then the base case is i == 0 || j == 0 (empty prefix), which becomes row/col 0 in the table — no negative indices, and recursion ↔ tabulation line up cleanly.

Longest Common Subsequence — LC 1143 🔥 📍

Match (a[i-1]==b[j-1]): take it, 1 + solve(i-1, j-1). No match: drop one char from either string, max(solve(i-1,j), solve(i,j-1)).

// LC 1143. Longest Common Subsequence
class Solution {
public:
    // ---------- 1) Recursion + Memoization (i, j = prefix lengths) ----------
    vector<vector<int>> dp;
    int solve(string& a, string& b, int i, int j) {
        if (i == 0 || j == 0) return 0;            // empty prefix
        if (dp[i][j] != -1) return dp[i][j];
        if (a[i - 1] == b[j - 1])
            return dp[i][j] = 1 + solve(a, b, i - 1, j - 1);   // match
        int skipA = solve(a, b, i - 1, j);
        int skipB = solve(a, b, i, j - 1);
        return dp[i][j] = max(skipA, skipB);
    }
    int longestCommonSubsequence(string a, string b) {
        int m = a.size(), n = b.size();
        dp.assign(m + 1, vector<int>(n + 1, -1));
        return solve(a, b, m, n);
    }
 
    // ---------- 2) Tabulation (SAME body, solve() -> dp[]) ----------
    int lcsTab(string a, string b) {
        int m = a.size(), n = b.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));   // row/col 0 = base case (empty prefix)
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];   // solve(i-1,j-1)
                } else {
                    int skipA = dp[i - 1][j];          // solve(i-1,j)
                    int skipB = dp[i][j - 1];          // solve(i,j-1)
                    dp[i][j] = max(skipA, skipB);
                }
            }
        return dp[m][n];
    }
};
// TC: O(m*n)   SC: O(m*n)

The 1-based shift is the string-DP superpower

Sizing the table (m+1) x (n+1) and letting row/col 0 mean “empty string” turns the recursion’s i==0/j==0 base case into a pre-filled border — no boundary ifs inside the loop. Almost every two-string DP uses this.

2 items under this folder.

Mindmap

Graph View

Backlinks