Chapter 6.2: Classic DP Problems

📝 Before You Continue: Make sure you've mastered Chapter 6.1's core DP concepts — states, recurrences, and base cases. You should be able to implement Fibonacci and basic coin change from scratch.

In this chapter, we tackle three of the most important and widely-applied DP problems in competitive programming. Mastering these patterns will help you recognize and solve dozens of USACO problems.

6.2.1 Longest Increasing Subsequence (LIS)

Problem: Given an array A of N integers, find the length of the longest subsequence where elements are strictly increasing. A subsequence doesn't need to be contiguous.

Example: A = [3, 1, 8, 2, 5]

• LIS: [1, 2, 5] → length 3
• Or: [3, 8] → length 2 (not the longest)
• Or: [1, 5] → length 2

💡 Key Insight: A subsequence can skip elements but must maintain relative order. The key DP insight: for each index i, ask "what's the longest increasing subsequence that ends at A[i]?" Then the answer is the maximum over all i.

LIS O(N²) 状态转移示意（A=[3,1,8,2,5]）：

flowchart LR
    subgraph arr["数组 A"]
        direction LR
        A0(["A[0]=3\ndp=1"])
        A1(["A[1]=1\ndp=1"])
        A2(["A[2]=8\ndp=2"])
        A3(["A[3]=2\ndp=2"])
        A4(["A[4]=5\ndp=3"])
    end
    A0 -->|"3<8"| A2
    A1 -->|"1<8"| A2
    A1 -->|"1<2"| A3
    A1 -->|"1<5"| A4
    A3 -->|"2<5"| A4
    note["答案: max(dp)=3\nLIS=[1,2,5]"]
    style A4 fill:#dcfce7,stroke:#16a34a
    style note fill:#f0fdf4,stroke:#16a34a

💡 转移规则： dp[i] = 1 + max(dp[j]) 对所有 j<i 且 A[j]<A[i]。箭头表示“可以延伸”的关系。

The diagram above illustrates the LIS structure: arrows show which earlier elements each position can extend from, and highlighted elements form the longest increasing subsequence.

The diagram shows the array [3,1,4,1,5,9,2,6] with the LIS 1→4→5→6 highlighted in green. Each dp[i] value below the array shows the LIS length ending at that position. Arrows connect elements that extend the subsequence.

O(N²) DP Solution

• State: dp[i] = length of the longest increasing subsequence ending at index i
• Recurrence: dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i]
• Base case: dp[i] = 1 (a subsequence of just A[i])
• Answer: max(dp[0], dp[1], ..., dp[N-1])

Step-by-step trace for A = [3, 1, 8, 2, 5]:

dp[0] = 1  (LIS ending at 3: just [3])

dp[1] = 1  (LIS ending at 1: just [1], since no j<1 with A[j]<1)

dp[2] = 2  (LIS ending at 8: A[0]=3 < 8 → dp[0]+1=2; A[1]=1 < 8 → dp[1]+1=2)
            Best: 2 ([3,8] or [1,8])

dp[3] = 2  (LIS ending at 2: A[1]=1 < 2 → dp[1]+1=2)
            Best: 2 ([1,2])

dp[4] = 3  (LIS ending at 5: A[1]=1 < 5 → dp[1]+1=2; A[3]=2 < 5 → dp[3]+1=3)
            Best: 3 ([1,2,5])

LIS length = max(dp) = 3

// Solution: LIS O(N²) — simple but too slow for N > 5000
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> dp(n, 1);  // every element alone is a subsequence of length 1

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[j] < A[i]) {              // A[j] can extend subsequence ending at A[i]
                dp[i] = max(dp[i], dp[j] + 1);  // ← KEY LINE
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
    return 0;
}

Sample Input: 5 / 3 1 8 2 5 → Output: 3

Complexity Analysis:

• Time: O(N²) — double loop
• Space: O(N) — dp array

For N ≤ 5000, O(N²) is fast enough. For N up to 10^5, we need the O(N log N) approach.

O(N log N) LIS with Binary Search (Patience Sorting)

The key idea: instead of tracking exact dp values, maintain a tails array where tails[k] = the smallest possible tail element of any increasing subsequence of length k+1 seen so far.

Why is this useful? Because if we can maintain this array, we can use binary search to find where to place each new element.

💡 Key Insight (Patience Sorting): Imagine dealing cards to piles. Each pile is a decreasing sequence (like Solitaire). A card goes on the leftmost pile whose top is ≥ it. If no such pile exists, start a new pile. The number of piles equals the LIS length! The tails array is exactly the tops of these piles.

Step-by-step trace for A = [3, 1, 8, 2, 5]:

Process 3: tails = [], no element ≥ 3, so push: tails = [3]
  → LIS length so far: 1

Process 1: tails = [3], lower_bound(1) hits index 0 (3 ≥ 1), replace:
  tails = [1]
  → LIS length still 1; but now the best 1-length subsequence ends in 1 (better!)

Process 8: tails = [1], lower_bound(8) hits end, push: tails = [1, 8]
  → LIS length: 2 (e.g., [1, 8])

Process 2: tails = [1, 8], lower_bound(2) hits index 1 (8 ≥ 2), replace:
  tails = [1, 2]
  → LIS length still 2; but best 2-length subsequence now ends in 2 (better!)

Process 5: tails = [1, 2], lower_bound(5) hits end, push: tails = [1, 2, 5]
  → LIS length: 3 (e.g., [1, 2, 5]) ✓

Answer = tails.size() = 3

ASCII Patience Sorting Visualization:

Cards dealt: 3, 1, 8, 2, 5

After 3:    After 1:    After 8:    After 2:    After 5:
[3]         [1]         [1][8]      [1][2]      [1][2][5]
Pile 1      Pile 1      P1  P2      P1  P2      P1  P2  P3

Number of piles = LIS length = 3 ✓

// Solution: LIS O(N log N) — fast enough for N up to 10^5
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> tails;  // tails[i] = smallest tail of any IS of length i+1

    for (int x : A) {
        // Find first tail >= x (for strictly increasing: use lower_bound)
        auto it = lower_bound(tails.begin(), tails.end(), x);

        if (it == tails.end()) {
            tails.push_back(x);   // x extends the longest subsequence
        } else {
            *it = x;              // ← KEY LINE: replace to maintain smallest possible tail
        }
    }

    cout << tails.size() << "\n";
    return 0;
}

⚠️ Note: tails doesn't store the actual LIS elements, just its length. The elements in tails are maintained in sorted order, which is why binary search works.

⚠️ Common Mistake: Using lower_bound gives LIS for strictly increasing (A[j] < A[i]). For non-decreasing (A[j] ≤ A[i]), use upper_bound instead.

Complexity Analysis:

• Time: O(N log N) — N elements, each with O(log N) binary search
• Space: O(N) — the tails array

LIS Application in USACO

Many USACO Silver problems reduce to LIS:

• "Minimum number of groups to partition a sequence so each group is non-increasing" → same as LIS length (by Dilworth's theorem)
• Sorting with restrictions often becomes LIS
• 2D LIS: sort by one dimension, find LIS of the other

🔗 Related Problem: USACO 2015 February Silver: "Censoring" — involves finding a pattern that's a subsequence.

6.2.2 The 0/1 Knapsack Problem

Problem: You have N items. Item i has weight w[i] and value v[i]. Your knapsack holds total weight W. Choose items to maximize total value without exceeding weight W. Each item can be used at most once (0/1 = take it or leave it).

Example:

• Items: (weight=2, value=3), (weight=3, value=4), (weight=4, value=5), (weight=5, value=6)
• W = 8
• Best: take items 1+2+3 (weight 2+3+4=9 > 8), or items 1+2 (weight 5, value 7), or items 1+4 (weight 7, value 9), or items 2+4 (weight 8, value 10). Answer: 10.

Visual: Knapsack DP Table

The 2D table shows dp[item][capacity]. Each row adds one item, and each cell represents the best value achievable with that capacity. The answer (8) is in the bottom-right corner. Highlighted cells show where new items changed the optimal value.

This static reference shows the complete knapsack DP table with the take/skip decisions highlighted for each item at each capacity level.

DP Formulation

0/1 背包决策过程示意（以第 i 个物品为例）：

flowchart TD
    State["当前状态: dp[i-1][w]"] --> Dec{"第 i 个物品\nweight[i]=wi, value[i]=vi"}
    Dec -->|"不拿 (skip)"| Skip["dp[i][w] = dp[i-1][w]"]
    Dec -->|"拿 (take)\n前提: wi ≤ w"| Take["dp[i][w] = dp[i-1][w-wi] + vi"]
    Skip --> Max["dp[i][w] = max(不拿, 拿)"]
    Take --> Max
    style Dec fill:#fef9ec,stroke:#d97706
    style Max fill:#dcfce7,stroke:#16a34a

💡 关键区别： 0/1 背包每个物品只能用一次，所以“拿”的时候从上一行 dp[i-1] 转移而来，而不是当前行。这就是为什么 1D 优化时要倒序遍历的原因。

• State: dp[i][w] = maximum value using items 1..i with total weight ≤ w
• Recurrence:
  • Don't take item i: dp[i][w] = dp[i-1][w]
  • Take item i (only if w[i] ≤ w): dp[i][w] = dp[i-1][w - weight[i]] + value[i]
  • Take the maximum: dp[i][w] = max(don't take, take)
• Base case: dp[0][w] = 0 (no items = zero value)
• Answer: dp[N][W]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, W;
    cin >> n >> W;

    vector<int> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];

    // dp[i][w] = max value using first i items with weight limit w
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // option 1: don't take item i

            if (weight[i] <= w) {    // option 2: take item i (if it fits)
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << dp[n][W] << "\n";
    return 0;
}

Space-Optimized 0/1 Knapsack — O(W) Space

We only need the previous row dp[i-1], so we can use a 1D array. Crucial: iterate w from W down to 0 (otherwise item i is used multiple times):

vector<int> dp(W + 1, 0);

for (int i = 1; i <= n; i++) {
    // Iterate BACKWARDS to prevent using item i more than once
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

cout << dp[W] << "\n";

Why backwards? When computing dp[w], we need dp[w - weight[i]] from the previous item's row (not current item's). Iterating backwards ensures dp[w - weight[i]] hasn't been updated by item i yet.

Unbounded Knapsack (Unlimited Items)

If each item can be used multiple times, iterate forwards:

for (int i = 1; i <= n; i++) {
    for (int w = weight[i]; w <= W; w++) {  // FORWARDS — allows reuse
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

6.2.3 Grid Path Counting

Problem: Count the number of paths from the top-left corner (1,1) to the bottom-right corner (N,M) of a grid, moving only right or down. Some cells are blocked.

Example: 3×3 grid with no blockages → 6 paths (C(4,2) = 6).

Visual: Grid Path DP Values

Each cell shows the number of paths from (0,0) to that cell. The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] adds paths arriving from above and from the left. The Pascal's triangle pattern emerges naturally when there are no obstacles.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int r = 0; r < n; r++) cin >> grid[r];

    // dp[r][c] = number of paths to reach (r, c)
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Base case: starting cell (if not blocked)
    if (grid[0][0] != '#') dp[0][0] = 1;

    // Fill first row (can only come from the left)
    for (int c = 1; c < m; c++) {
        if (grid[0][c] != '#') dp[0][c] = dp[0][c-1];
    }

    // Fill first column (can only come from above)
    for (int r = 1; r < n; r++) {
        if (grid[r][0] != '#') dp[r][0] = dp[r-1][0];
    }

    // Fill rest of the grid
    for (int r = 1; r < n; r++) {
        for (int c = 1; c < m; c++) {
            if (grid[r][c] == '#') {
                dp[r][c] = 0;  // blocked — no paths through here
            } else {
                dp[r][c] = dp[r-1][c] + dp[r][c-1];  // from above + from left
            }
        }
    }

    cout << dp[n-1][m-1] << "\n";
    return 0;
}

Grid Maximum Value Path

Problem: Find the path from (1,1) to (N,M) (moving right or down) that maximizes the sum of values.

vector<vector<int>> val(n, vector<int>(m));
for (int r = 0; r < n; r++)
    for (int c = 0; c < m; c++)
        cin >> val[r][c];

vector<vector<long long>> dp(n, vector<long long>(m, 0));
dp[0][0] = val[0][0];

for (int c = 1; c < m; c++) dp[0][c] = dp[0][c-1] + val[0][c];
for (int r = 1; r < n; r++) dp[r][0] = dp[r-1][0] + val[r][0];

for (int r = 1; r < n; r++) {
    for (int c = 1; c < m; c++) {
        dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + val[r][c];
    }
}

cout << dp[n-1][m-1] << "\n";

6.2.4 USACO DP Example: Hoof Paper Scissors

Problem (USACO 2019 January Silver): Bessie plays N rounds of Hoof-Paper-Scissors (like Rock-Paper-Scissors but with cow gestures). She knows the opponent's moves in advance. She can change her gesture at most K times. Maximize wins.

State: dp[i][j][g] = max wins in the first i rounds, having changed j times, currently playing gesture g.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    // 0=Hoof, 1=Paper, 2=Scissors
    vector<int> opp(n + 1);
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == 'H') opp[i] = 0;
        else if (c == 'P') opp[i] = 1;
        else opp[i] = 2;
    }

    // dp[j][g] = max wins using j changes so far, currently playing gesture g
    // (2D since we process rounds iteratively)
    const int NEG_INF = -1e9;
    vector<vector<int>> dp(k + 1, vector<int>(3, NEG_INF));

    // Initialize: before round 1, 0 changes, any starting gesture
    for (int g = 0; g < 3; g++) dp[0][g] = 0;

    for (int i = 1; i <= n; i++) {
        vector<vector<int>> ndp(k + 1, vector<int>(3, NEG_INF));

        for (int j = 0; j <= k; j++) {
            for (int g = 0; g < 3; g++) {
                if (dp[j][g] == NEG_INF) continue;

                int win = (g == opp[i]) ? 1 : 0;  // do we win this round?

                // Option 1: don't change gesture
                ndp[j][g] = max(ndp[j][g], dp[j][g] + win);

                // Option 2: change gesture (costs 1 change)
                if (j < k) {
                    for (int ng = 0; ng < 3; ng++) {
                        if (ng != g) {
                            int nwin = (ng == opp[i]) ? 1 : 0;
                            ndp[j+1][ng] = max(ndp[j+1][ng], dp[j][g] + nwin);
                        }
                    }
                }
            }
        }

        dp = ndp;
    }

    int ans = 0;
    for (int j = 0; j <= k; j++)
        for (int g = 0; g < 3; g++)
            ans = max(ans, dp[j][g]);

    cout << ans << "\n";
    return 0;
}

6.2.5 Interval DP — Matrix Chain and Burst Balloons Patterns

Interval DP is a powerful DP technique where the state represents a contiguous subarray or subrange, and we combine solutions of smaller intervals to solve larger ones.

💡 Key Insight: When the optimal solution for a range [l, r] depends on how we split that range at some point k, and the sub-problems for [l, k] and [k+1, r] are independent, interval DP applies.

The Interval DP Framework

Interval DP 填表顺序示意（以 n=4 为例）：

flowchart LR
    subgraph len1["len=1 （基础情况）"]
        direction TB
        L11["dp[1][1]"] 
        L22["dp[2][2]"]
        L33["dp[3][3]"]
        L44["dp[4][4]"]
    end
    subgraph len2["len=2"]
        direction TB
        L12["dp[1][2]"]
        L23["dp[2][3]"]
        L34["dp[3][4]"]
    end
    subgraph len3["len=3"]
        direction TB
        L13["dp[1][3]"]
        L24["dp[2][4]"]
    end
    subgraph len4["len=4 （答案）"]
        direction TB
        L14["dp[1][4] ⭐"]
    end
    len1 -->|"依赖"| len2
    len2 -->|"依赖"| len3
    len3 -->|"依赖"| len4
    style L14 fill:#dcfce7,stroke:#16a34a
    style len4 fill:#f0fdf4,stroke:#16a34a

💡 填表顺序关键： 必须按区间长度由小到大填表。计算 dp[l][r] 时，所有更短的子区间 dp[l][k] 和 dp[k+1][r] 已经就绪。

State:   dp[l][r] = optimal solution for the subproblem on interval [l, r]
Base:    dp[i][i] = cost/value for a single element (often 0 or trivial)
Order:   Fill by increasing interval LENGTH (len = 1, 2, 3, ..., n)
         This ensures dp[l][k] and dp[k+1][r] are computed before dp[l][r]
Transition:
         dp[l][r] = min/max over all split points k in [l, r-1] of:
                    dp[l][k] + dp[k+1][r] + cost(l, k, r)
Answer:  dp[1][n]  (or dp[0][n-1] for 0-indexed)

Enumeration order matters! We enumerate by interval length, not by left endpoint. This guarantees all sub-intervals are solved before we need them.

Classic Example: Matrix Chain Multiplication

Problem: Given N matrices A₁, A₂, ..., Aₙ where matrix Aᵢ has dimensions dim[i-1] × dim[i], find the parenthesization that minimizes the total number of scalar multiplications.

Why DP? Different parenthesizations have wildly different costs:

• (A₁A₂)A₃: cost = p×q×r + p×r×s (where shapes are p×q, q×r, r×s)
• A₁(A₂A₃): cost = q×r×s + p×q×s

State: dp[l][r] = minimum multiplications to compute the product Aₗ × Aₗ₊₁ × ... × Aᵣ

Transition: Try every split point k ∈ [l, r-1]. When we split at k:

• Left product Aₗ...Aₖ has cost dp[l][k], resulting shape dim[l-1] × dim[k]
• Right product Aₖ₊₁...Aᵣ has cost dp[k+1][r], resulting shape dim[k] × dim[r]
• Multiplying these two results costs dim[l-1] × dim[k] × dim[r]

// Solution: Matrix Chain Multiplication — O(N³) time, O(N²) space
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;  // number of matrices

    // dim[i-1] × dim[i] is the shape of matrix i (1-indexed)
    // So we need n+1 dimensions
    vector<int> dim(n + 1);
    for (int i = 0; i <= n; i++) cin >> dim[i];
    // Matrix i has shape dim[i-1] × dim[i]

    // dp[l][r] = min cost to compute product of matrices l..r
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    const long long INF = 1e18;

    // Fill dp by increasing interval length
    for (int len = 2; len <= n; len++) {          // interval length
        for (int l = 1; l + len - 1 <= n; l++) {  // left endpoint
            int r = l + len - 1;                   // right endpoint
            dp[l][r] = INF;

            // Try every split point k
            for (int k = l; k < r; k++) {
                long long cost = dp[l][k]                    // left subproblem
                               + dp[k+1][r]                  // right subproblem
                               + (long long)dim[l-1] * dim[k] * dim[r]; // merge cost
                dp[l][r] = min(dp[l][r], cost);
            }
        }
    }

    cout << dp[1][n] << "\n";  // min cost to multiply all n matrices
    return 0;
}

Complexity Analysis:

• States: O(N²) — all pairs (l, r) with l ≤ r
• Transition: O(N) per state — try all split points k
• Total Time: O(N³)
• Space: O(N²)

Example trace for N=4, dims = [10, 30, 5, 60, 10]:

Matrices: A1(10×30), A2(30×5), A3(5×60), A4(60×10)

len=2:
  dp[1][2] = dim[0]*dim[1]*dim[2] = 10*30*5 = 1500
  dp[2][3] = dim[1]*dim[2]*dim[3] = 30*5*60 = 9000
  dp[3][4] = dim[2]*dim[3]*dim[4] = 5*60*10 = 3000

len=3:
  dp[1][3]: try k=1: dp[1][1]+dp[2][3]+10*30*60 = 0+9000+18000 = 27000
             try k=2: dp[1][2]+dp[3][3]+10*5*60  = 1500+0+3000  = 4500
             dp[1][3] = 4500
  dp[2][4]: try k=2: dp[2][2]+dp[3][4]+30*5*10  = 0+3000+1500  = 4500
             try k=3: dp[2][3]+dp[4][4]+30*60*10 = 9000+0+18000 = 27000
             dp[2][4] = 4500

len=4:
  dp[1][4]: try k=1: dp[1][1]+dp[2][4]+10*30*10 = 0+4500+3000  = 7500
             try k=2: dp[1][2]+dp[3][4]+10*5*10  = 1500+3000+500 = 5000 ← min!
             try k=3: dp[1][3]+dp[4][4]+10*60*10 = 4500+0+6000  = 10500
             dp[1][4] = 5000

Answer: 5000 scalar multiplications (parenthesization: (A1 A2)(A3 A4))

Other Classic Interval DP Problems

1. Burst Balloons (LeetCode 312):

• dp[l][r] = max coins from bursting all balloons between l and r
• Key twist: think of k as the last balloon to burst in [l, r] (not first split!)
• dp[l][r] = max over k of (nums[l-1]*nums[k]*nums[r+1] + dp[l][k-1] + dp[k+1][r])

2. Optimal Binary Search Tree:

• dp[l][r] = min cost of BST for keys l..r with given access frequencies
• Split at root k: dp[l][r] = dp[l][k-1] + dp[k+1][r] + sum_freq(l, r)

3. Palindrome Partitioning:

• dp[l][r] = min cuts to partition s[l..r] into palindromes
• dp[l][r] = 0 if s[l..r] is already a palindrome, else min over k of (dp[l][k] + dp[k+1][r] + 1)

Template Summary

// Generic Interval DP Template
// Assumes 1-indexed, n elements
void intervalDP(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // Base case: intervals of length 1
    for (int i = 1; i <= n; i++) dp[i][i] = base_case(i);

    // Fill by increasing length
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;  // or -INF for maximization

            for (int k = l; k < r; k++) {  // split at k (or k+1)
                int val = dp[l][k] + dp[k+1][r] + cost(l, k, r);
                dp[l][r] = min(dp[l][r], val);  // or max
            }
        }
    }
    // Answer is dp[1][n]
}

⚠️ Common Mistake: Iterating over left endpoint l in the outer loop and length in the inner loop. This is wrong — when you compute dp[l][r], the sub-intervals dp[l][k] and dp[k+1][r] must already be computed. Always iterate by length in the outer loop.

// WRONG — dp[l][k] might not be ready yet!
for (int l = 1; l <= n; l++)
    for (int r = l + 1; r <= n; r++)
        ...

// CORRECT — all shorter intervals are computed first
for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        ...
    }

⚠️ Common Mistakes in Chapter 6.2

1. LIS: using upper_bound for strictly increasing: For strictly increasing, use lower_bound. For non-decreasing, use upper_bound. Getting this wrong gives LIS length off by 1.
2. 0/1 Knapsack: iterating weight forward: Iterating w from 0 to W (forward) allows using item i multiple times — that's unbounded knapsack, not 0/1. Always iterate backwards for 0/1.
3. Grid paths: forgetting to handle blocked cells: If grid[r][c] == '#', set dp[r][c] = 0 (not dp[r-1][c] + dp[r][c-1]).
4. Overflow in grid path counting: Even for small grids, the number of paths can be astronomically large. Use long long or modular arithmetic.
5. LIS: thinking tails contains the actual LIS: It doesn't! tails contains the smallest possible tail elements for subsequences of each length. The actual LIS must be reconstructed separately.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: In the O(N log N) LIS solution, does the tails array store the actual LIS?

A: No! tails stores "the minimum tail element of increasing subsequences of each length". Its length equals the LIS length, but the elements themselves may not form a valid increasing subsequence. To reconstruct the actual LIS, you need to record each element's "predecessor".

Q2: Why does 0/1 knapsack require reverse iteration over w?

A: Because dp[w] needs the "previous row's" dp[w - weight[i]]. If iterating forward, dp[w - weight[i]] may already be updated by the current row (equivalent to using item i multiple times). Reverse iteration ensures each item is used at most once.

Q3: What is the only difference between unbounded knapsack (items usable unlimited times) and 0/1 knapsack code?

A: Just the inner loop direction. 0/1 knapsack: w from W down to weight[i] (reverse). Unbounded knapsack: w from weight[i] up to W (forward).

Q4: What if the grid path can also move up or left?

A: Then simple grid DP no longer works (because there would be cycles). You need BFS/DFS or more complex DP. Standard grid path DP only applies to "right/down only" movement.

🔗 Connections to Later Chapters

• Chapter 3.3 (Sorting & Binary Search): binary search is the core of O(N log N) LIS — lower_bound on the tails array
• Chapter 6.3 (Advanced DP): extends knapsack to bitmask DP (item sets → bitmask), extends grid DP to interval DP
• Chapter 4.1 (Greedy): interval scheduling problems can sometimes be converted to LIS (via Dilworth's theorem)
• LIS is extremely common in USACO Silver — 2D LIS, weighted LIS, LIS counting variants appear frequently

Practice Problems

Problem 6.2.1 — LIS Length 🟢 Easy Read N integers. Find the length of the longest strictly increasing subsequence.

Problem 6.2.2 — Number of LIS 🔴 Hard Read N integers. Find the number of distinct longest increasing subsequences. (Answer modulo 10^9+7.)

Solution sketch: Maintain both dp[i] (LIS length ending at i) and cnt[i] (number of such LIS). When dp[j]+1 > dp[i]: update dp[i] and reset cnt[i] = cnt[j]. When equal: add cnt[j] to cnt[i].

Problem 6.2.3 — 0/1 Knapsack 🟡 Medium N items with weights and values, capacity W. Find maximum value. (N, W ≤ 1000)

Problem 6.2.4 — Collect Stars 🟡 Medium An N×M grid has stars ('*') and obstacles ('#'). Moving only right or down from (1,1) to (N,M), collect as many stars as possible. Print the maximum stars collected.

Problem 6.2.5 — Variations of Knapsack 🔴 Hard Read N items each with weight w[i] and value v[i]. Capacity W.

• Variant A: Each item available up to k[i] times (bounded knapsack)
• Variant B: Must fill the knapsack exactly (no extra space allowed)
• Variant C: Minimize weight while achieving value ≥ target V

Solution sketch: (A) Treat each item as k[i] copies for 0/1 knapsack, or use monotonic deque optimization. (B) Initialize dp[0] = 0, all other dp[w] = INF, answer is dp[W]. (C) Swap the roles of weight and value in the DP.

🏆 Challenge Problem: USACO 2019 January Silver: Grass Planting Each of N fields has a certain grass density. Farmer John can re-plant any number of non-overlapping intervals. Design a DP to maximize the number of fields with the specific grass density he wants after at most K re-plantings. (Interval DP combined with 1D DP)

Visual: LIS via Patience Sorting

This diagram illustrates LIS using the patience sorting analogy. Each "pile" represents a potential subsequence endpoint. The number of piles equals the LIS length. Binary search finds where each card goes in O(log N), giving an O(N log N) overall algorithm.

Visual: Knapsack DP Table

The 0/1 Knapsack DP table: rows = items considered, columns = capacity. Each cell shows the maximum value achievable. Blue cells show single-item contributions, green cells show combinations, and the starred cell is the optimal answer.