DP 進階技巧

// LC 486. Predict the Winner — 2D DP
public boolean predictTheWinner(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][n];

    // Base case: single element → take it
    for (int i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }

    // Fill by increasing subarray length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(
                nums[i] - dp[i + 1][j],   // pick left
                nums[j] - dp[i][j - 1]    // pick right
            );
        }
    }

    return dp[0][n - 1] >= 0;  // player 1 wins or ties
}

// java
// LC 834
// Reference: leetcode_java/src/main/java/LeetCodeJava/Tree/SumOfDistancesInTree.java

/**
 * Problem: Given an undirected tree with n nodes, return an array where
 * answer[i] = sum of distances between node i and all other nodes.
 *
 * Example:
 * Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
 * Output: [8,12,6,10,10,10]
 *
 * WHY RE-ROOTING DP?
 *
 * A naive BFS/DFS from every node → O(N²), TLE for N = 3×10⁴.
 * Re-rooting DP solves it in O(N) with two DFS passes.
 *
 * KEY INSIGHT (Re-rooting Formula):
 *
 *   When moving root from node u to its child v:
 *     - count[v] nodes get 1 unit CLOSER  (they are in v's subtree)
 *     - (N - count[v]) nodes get 1 unit FARTHER (they are outside v's subtree)
 *
 *   Therefore:
 *     ans[v] = ans[u] - count[v] + (N - count[v])
 *
 * ALGORITHM:
 *
 *   Pass 1 — Post-order DFS (bottom-up):
 *     For each node u, compute:
 *       count[u] = size of u's subtree (including u)
 *       ans[u]   = sum of distances from u to all nodes in u's subtree
 *     After this pass, ans[root] is correct (total distance from root to all nodes).
 *
 *   Pass 2 — Pre-order DFS (top-down, re-root):
 *     For each edge u→v, compute ans[v] from ans[u] using the formula above.
 *     This propagates the correct answer to every node.
 *
 * Time:  O(N) — two DFS passes
 * Space: O(N) — adjacency list + count[] + ans[]
 */

// V0-1: Re-rooting DP (clean implementation)
int[] ans;
int[] count;
List<Set<Integer>> adj;
int n;

public int[] sumOfDistancesInTree(int n, int[][] edges) {
    this.n = n;
    ans = new int[n];
    count = new int[n];
    adj = new ArrayList<>();

    for (int i = 0; i < n; i++)
        adj.add(new HashSet<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }

    // Pass 1: Post-order DFS → compute count[] and ans[0]
    dfs1(0, -1);

    // Pass 2: Pre-order DFS → re-root to compute all ans[i]
    dfs2(0, -1);

    return ans;
}

// Post-order: count subtree sizes, accumulate distances for root
private void dfs1(int u, int parent) {
    count[u] = 1;
    for (int v : adj.get(u)) {
        if (v == parent) continue;
        dfs1(v, u);
        count[u] += count[v];
        // Distance from u to all nodes in v's subtree
        // = (dist from v to its subtree) + (number of nodes in v's subtree)
        ans[u] += ans[v] + count[v];
    }
}

// Pre-order: shift root from parent u to child v
private void dfs2(int u, int parent) {
    for (int v : adj.get(u)) {
        if (v == parent) continue;
        // Re-rooting formula:
        // count[v] nodes get closer, (n - count[v]) nodes get farther
        ans[v] = ans[u] - count[v] + (n - count[v]);
        dfs2(v, u);
    }
}

/**
 * STEP-BY-STEP EXAMPLE:
 *
 *        0
 *       / \
 *      1   2
 *         /|\
 *        3  4  5
 *
 * n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
 *
 * Pass 1 (Post-order, root=0):
 *   count = [6, 1, 4, 1, 1, 1]
 *   ans   = [8, 0, 3, 0, 0, 0]   ← only ans[0]=8 is the full answer
 *
 *   ans[2] = ans[3]+count[3] + ans[4]+count[4] + ans[5]+count[5]
 *          = 0+1 + 0+1 + 0+1 = 3
 *   ans[0] = ans[1]+count[1] + ans[2]+count[2]
 *          = 0+1 + 3+4 = 8 ✓ (matches expected output)
 *
 * Pass 2 (Pre-order, re-root):
 *   ans[1] = ans[0] - count[1] + (6 - count[1]) = 8 - 1 + 5 = 12 ✓
 *   ans[2] = ans[0] - count[2] + (6 - count[2]) = 8 - 4 + 2 = 6  ✓
 *   ans[3] = ans[2] - count[3] + (6 - count[3]) = 6 - 1 + 5 = 10 ✓
 *   ans[4] = ans[2] - count[4] + (6 - count[4]) = 6 - 1 + 5 = 10 ✓
 *   ans[5] = ans[2] - count[5] + (6 - count[5]) = 6 - 1 + 5 = 10 ✓
 *
 * Final: [8, 12, 6, 10, 10, 10] ✓
 */

# python
# LC 834 Sum of Distances in Tree
# Re-rooting DP template

# V0
# IDEA: Re-rooting DP (two-pass DFS)
class Solution:
    def sumOfDistancesInTree(self, n, edges):
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        count = [1] * n  # subtree size
        ans = [0] * n

        # Pass 1: Post-order DFS (iterative to avoid recursion limit)
        # Compute count[] and ans[0]
        order = []
        visited = [False] * n
        parent = [-1] * n
        stack = [0]
        visited[0] = True
        while stack:
            u = stack.pop()
            order.append(u)
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    stack.append(v)

        # Process in reverse order (post-order)
        for u in reversed(order):
            for v in adj[u]:
                if v == parent[u]:
                    continue
                count[u] += count[v]
                ans[u] += ans[v] + count[v]

        # Pass 2: Pre-order DFS (re-root)
        for u in order:
            for v in adj[u]:
                if v == parent[u]:
                    continue
                ans[v] = ans[u] - count[v] + (n - count[v])

        return ans

ans[child] = f(ans[parent], subtree_info[child], n)

LC 834:  ans[v] = ans[u] - count[v] + (n - count[v])
         moving the root across edge u->v pulls count[v] nodes one step
         closer and pushes the other (n - count[v]) one step further

Building dp[0][5] (entire interval):
  Try k=1 (value 3) as LAST:
    coins = balloons[0] * balloons[1] * balloons[5] = 1 * 3 * 1 = 3
    total = 3 + dp[0][1] + dp[1][5]

  Try k=2 (value 1) as LAST:
    coins = balloons[0] * balloons[2] * balloons[5] = 1 * 1 * 1 = 1
    total = 1 + dp[0][2] + dp[2][5]

  Try k=3 (value 5) as LAST:
    coins = balloons[0] * balloons[3] * balloons[5] = 1 * 5 * 1 = 5
    total = 5 + dp[0][3] + dp[3][5]

  Try k=4 (value 8) as LAST:
    coins = balloons[0] * balloons[4] * balloons[5] = 1 * 8 * 1 = 8
    total = 8 + dp[0][4] + dp[4][5]

Result: dp[0][5] = 167

def maxCoins_inclusive(nums):
    """Alternative: dp[i][j] includes balloons i through j"""
    n = len(nums)
    balloons = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    # Iterate through window lengths (len) from 1 to n
    for length in range(1, n + 1):
        for left in range(1, n - length + 2):
            right = left + length - 1

            # Try every balloon k in [left, right] as LAST to burst
            for k in range(left, right + 1):
                coins = (dp[left][k - 1] + dp[k + 1][right] +
                        balloons[left - 1] * balloons[k] * balloons[right + 1])
                dp[left][right] = max(dp[left][right], coins)

    return dp[1][n]

def maxCoins_topdown(nums):
    """Top-down with memoization"""
    balloons = [1] + nums + [1]
    memo = {}

    def dp(left, right):
        """Max coins from bursting balloons between left and right (exclusive)"""
        if left + 1 == right:  # No balloons between left and right
            return 0

        if (left, right) in memo:
            return memo[(left, right)]

        max_coins = 0
        # Try each balloon k as the last to burst
        for k in range(left + 1, right):
            coins = (balloons[left] * balloons[k] * balloons[right] +
                    dp(left, k) + dp(k, right))
            max_coins = max(max_coins, coins)

        memo[(left, right)] = max_coins
        return max_coins

    return dp(0, len(balloons) - 1)

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] balloons = new int[n + 2];
    balloons[0] = balloons[n + 1] = 1;
    for (int i = 0; i < n; i++) {
        balloons[i + 1] = nums[i];
    }

    int[][] dp = new int[n + 2][n + 2];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = -1;  // -1 means not computed yet
        }
    }

    return burst(balloons, 0, n + 1, dp);
}

private int burst(int[] balloons, int left, int right, int[][] dp) {
    if (left + 1 == right) return 0;  // No balloons between left and right

    if (dp[left][right] != -1) {
        return dp[left][right];
    }

    int maxCoins = 0;
    for (int k = left + 1; k < right; k++) {
        int coins = balloons[left] * balloons[k] * balloons[right];
        coins += burst(balloons, left, k, dp) + burst(balloons, k, right, dp);
        maxCoins = Math.max(maxCoins, coins);
    }

    dp[left][right] = maxCoins;
    return maxCoins;
}

dp[i][j] depends on:
    dp[i+1][j-1]   ← diagonal (i+1, j-1): both already computed
    dp[i+1][j]     ← row below: need i+1 before i  → loop i BACKWARD
    dp[i][j-1]     ← column left: need j-1 before j → loop j FORWARD

int n = s.length();
int[][] dp = new int[n][n];

// Base case: single characters
for (int i = 0; i < n; i++) dp[i][i] = 1;

// i backwards (so dp[i+1][...] is already filled)
for (int i = n - 1; i >= 0; i--) {
    // j forwards (so dp[...][j-1] is already filled)
    for (int j = i + 1; j < n; j++) {
        if (s.charAt(i) == s.charAt(j)) {
            dp[i][j] = dp[i + 1][j - 1] + 2;   // expand palindrome
        } else {
            dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);  // skip i or j
        }
    }
}
return dp[0][n - 1];

def interval_dp(arr):
    """DP for interval/subarray problems"""
    n = len(arr)
    # dp[i][j] = optimal value for interval [i, j]
    dp = [[0] * n for _ in range(n)]

    # Base case: single elements
    for i in range(n):
        dp[i][i] = arr[i]

    # Iterate by interval length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Try all split points
            for k in range(i, j):
                dp[i][j] = max(dp[i][j],
                              dp[i][k] + dp[k+1][j] + cost(i, j))

    return dp[0][n-1]

def interval_dp(arr):
    """Matrix chain multiplication style"""
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

    # Length of interval
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')

            # Try all possible split points
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + arr[i] * arr[k+1] * arr[j+1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-2] if n > 1 else 0

# LC 746: Min Cost Climbing Stairs
def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)  # Need n+1 for the "top floor"

    # You can start from step 0 or step 1
    dp[0] = 0
    dp[1] = 0

    for i in range(2, n + 1):  # Loop to n+1
        # You can arrive from i-1 or i-2
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

    return dp[n]  # The top floor is at position n

We need to represent amounts: 0, 1, 2, 3, 4, 5
                         ↓    ↓   ↓   ↓   ↓   ↓
Array indices needed:    [0]  [1] [2] [3] [4] [5]

Therefore: dp array size = 6 = amount + 1

int amount = 5;
int[] dp = new int[amount + 1];  // size = 6, indices 0-5

// Now we can store results for each amount:
dp[0] = ...  // result for amount 0
dp[1] = ...  // result for amount 1
dp[2] = ...  // result for amount 2
dp[3] = ...  // result for amount 3
dp[4] = ...  // result for amount 4
dp[5] = ...  // result for amount 5

public int change(int amount, int[] coins) {
    // dp[i] = total number of COMBINATIONS that make up amount i
    // Index corresponds to the amount value
    
    // Example: if amount = 5
    // We need: dp[0], dp[1], dp[2], dp[3], dp[4], dp[5]
    // Therefore: dp array size = 5 + 1 = 6
    
    int[] dp = new int[amount + 1];  // Size = amount + 1
    
    // Base case: There is exactly 1 way to make amount 0 (empty set)
    dp[0] = 1;
    
    // OUTER LOOP: Iterate through each coin
    // This ensures combinations (not permutations)
    for (int coin : coins) {
        // INNER LOOP: Update dp for all reachable amounts
        for (int i = coin; i <= amount; i++) {
            // Accumulate combinations:
            // Ways to make i = current ways + ways to make (i - coin)
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];  // Answer is at index = amount
}

Initial:        dp = [1, 0, 0, 0, 0, 0]
After coin 1:   dp = [1, 1, 1, 1, 1, 1]  (all amounts reachable with 1s)
After coin 2:   dp = [1, 1, 2, 2, 3, 3]  (add combinations with 2s)
After coin 5:   dp = [1, 1, 2, 2, 3, 4]  (add combination with 5)

Result: dp[5] = 4 combinations: {5}, {2+2+1}, {2+1+1+1}, {1+1+1+1+1}

public int coinChange(int[] coins, int amount) {
    // dp[i] = minimum coins needed to make amount i
    // Same sizing: dp array size = amount + 1
    
    int[] dp = new int[amount + 1];
    
    // Initialize all to "infinity" except dp[0]
    Arrays.fill(dp, amount + 1);  // Use amount+1 as infinity
    dp[0] = 0;  // Base case: 0 coins needed for amount 0
    
    // OUTER LOOP: For each amount (can be any order)
    for (int i = 1; i <= amount; i++) {
        // INNER LOOP: Try each coin
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

# Combinations (coins outer):
Initial:           dp = [1, 0, 0, 0]
After coin=1:      dp = [1, 1, 1, 1]   ← all amounts built from 1s only
After coin=2:      dp = [1, 1, 2, 2]   ← can now use 2s on top of 1s

→ dp[3] = 2 : {1,1,1}, {1,2}           ← {2,1} NOT separately counted ✓


# Permutations (amount outer):
Initial:           dp = [1, 0, 0, 0]
i=1: coin=1 → dp[1]+=dp[0]=1          dp = [1, 1, 0, 0]
i=2: coin=1 → dp[2]+=dp[1]=1
     coin=2 → dp[2]+=dp[0]=1          dp = [1, 1, 2, 0]
i=3: coin=1 → dp[3]+=dp[2]=2
     coin=2 → dp[3]+=dp[1]=1          dp = [1, 1, 2, 3]

→ dp[3] = 3 : {1,1,1}, {1,2}, {2,1}   ← {2,1} counted separately ✓

# python — Combinations (LC 518): coins outer
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:                    # coin fixed first → combinations
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

# python — Permutations (LC 377): amount outer
def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for i in range(1, target + 1):        # amount first → permutations
        for num in nums:
            if i >= num:
                dp[i] += dp[i - num]
    return dp[target]

Coins outer: "I decide to use coin-1 first, then optionally add coin-2 on top."
             → Sequence is forced: coin-1 always before coin-2 → no duplicates.

Amount outer: "To reach amount i, which coin did I place LAST?"
             → Each last-coin choice is a distinct path → all orderings counted.

2-D (classic):
  dp[i][w] = max value using first i items with capacity w

  dp[i][w] = dp[i-1][w]                              # skip item i
  if w >= weight[i]:
      dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i]] + value[i])   # take item i

1-D (space-optimized):
  Observe that dp[i][...] depends ONLY on dp[i-1][...].
  Collapse to one array, iterate w BACKWARD so dp[w-weight[i]]
  still holds dp[i-1][w-weight[i]] when we need it.

  dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
  (backward w: W → weight[i])

for each item:
    for j = W down to weight:          # ※ j 要倒著跑
        dp[j] = max(dp[j], dp[j - weight] + value)

def knapsack_01(weights, values, capacity):
    # time = O(n * W), space = O(n * W)
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]                                    # skip
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])  # take
    return dp[n][capacity]

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;

    // First column prefix sum
    for (int i = 1; i < m; i++)
        grid[i][0] += grid[i - 1][0];

    // First row prefix sum
    for (int j = 1; j < n; j++)
        grid[0][j] += grid[0][j - 1];

    // Fill rest in-place
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);

    return grid[m - 1][n - 1];
}

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;

    // cur[i] = min cost to reach current column at row i
    int[] cur = new int[m];
    cur[0] = grid[0][0];

    // Initialize first column
    for (int i = 1; i < m; i++)
        cur[i] = cur[i - 1] + grid[i][0];

    // Process column by column
    for (int j = 1; j < n; j++) {
        cur[0] += grid[0][j];  // First row: only from left
        for (int i = 1; i < m; i++)
            cur[i] = Math.min(cur[i - 1], cur[i]) + grid[i][j];
            //                ↑ from above    ↑ current row, previous column
    }

    return cur[m - 1];
}

public int minPathSum(int[][] grid) {
    int m = grid.length - 1;
    int n = grid[0].length - 1;
    int[][] dp = new int[m + 1][n + 1];
    for (int[] row : dp)
        Arrays.fill(row, -1);
    return helper(grid, m, n, dp);
}

// helper(m, n) = min path sum from (0,0) to (m,n)
private int helper(int[][] grid, int m, int n, int[][] dp) {
    if (m == 0 && n == 0) return grid[0][0];
    if (m == 0) {
        dp[m][n] = grid[m][n] + helper(grid, m, n - 1, dp);
        return dp[m][n];
    }
    if (n == 0) {
        dp[m][n] = grid[m][n] + helper(grid, m - 1, n, dp);
        return dp[m][n];
    }
    if (dp[m][n] != -1) return dp[m][n];
    // DP equation: min(come from left, come from above) + current cell
    dp[m][n] = grid[m][n] + Math.min(helper(grid, m, n - 1, dp), helper(grid, m - 1, n, dp));
    return dp[m][n];
}

grid = [[1,3,1],
        [1,5,1],
        [4,2,1]]

After DP:
dp = [[1, 4, 5],
      [2, 7, 6],
      [6, 8, 7]]

Path: 1→3→1→1→1 = 7

# Python equivalent
def grid_dp(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[m-1][n-1]

def grid_dp_optimized(grid):
    """Space-optimized 2D DP"""
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    # Only need previous row
    prev = [0] * n
    prev[0] = grid[0][0]

    # Initialize first row
    for j in range(1, n):
        prev[j] = prev[j-1] + grid[0][j]

    # Process remaining rows
    for i in range(1, m):
        curr = [0] * n
        curr[0] = prev[0] + grid[i][0]

        for j in range(1, n):
            curr[j] = min(prev[j], curr[j-1]) + grid[i][j]

        prev = curr

    return prev[n-1]

state : (r1, c1, r2)     with   c2 = r1 + c1 - r2      # both walkers took r1+c1 steps
moves : each walker independently goes DOWN or RIGHT   -> 4 combinations
pick  : grid[r1][c1] + grid[r2][c2],  but ONCE if the two walkers are on the same cell
block : a -1 under either walker kills the whole state
answer: max(0, dfs(0, 0, 0))    # -inf means "no legal round trip at all"

// java
// LC 741 - Cherry Pickup
// IDEA: down-and-back == two simultaneous down-right walks. Both have taken r1+c1 steps,
//       so the second walker's column is implied: c2 = r1 + c1 - r2.
// time = O(n^3), space = O(n^3)
private static final int NEG = Integer.MIN_VALUE;

public int cherryPickup(int[][] grid) {
    int n = grid.length;
    Integer[][][] memo = new Integer[n][n][n];
    return Math.max(0, dfs(grid, 0, 0, 0, memo));   // NEG means every round trip is blocked
}

private int dfs(int[][] grid, int r1, int c1, int r2, Integer[][][] memo) {
    int n = grid.length;
    int c2 = r1 + c1 - r2;             // the invariant that removes the 4th dimension
    if (r1 >= n || c1 >= n || r2 >= n || c2 >= n) return NEG;
    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) return NEG;
    if (r1 == n - 1 && c1 == n - 1) return grid[r1][c1];   // both are forced onto (n-1, n-1)
    if (memo[r1][c1][r2] != null) return memo[r1][c1][r2];

    // NOTE !!! same cell -> the cherry is taken once, not twice
    int got = grid[r1][c1] + (r1 == r2 ? 0 : grid[r2][c2]);

    int rest = Math.max(
        Math.max(dfs(grid, r1 + 1, c1, r2 + 1, memo),      // down , down
                 dfs(grid, r1 + 1, c1, r2,     memo)),     // down , right
        Math.max(dfs(grid, r1, c1 + 1, r2 + 1, memo),      // right, down
                 dfs(grid, r1, c1 + 1, r2,     memo)));    // right, right

    int res = (rest == NEG) ? NEG : got + rest;
    memo[r1][c1][r2] = res;
    return res;
}

# python
# LC 741 - Cherry Pickup
# IDEA: two walkers, both r+c steps in; c2 is derived, so memoise on (r1, c1, r2)
# time = O(n^3), space = O(n^3)
from functools import lru_cache

def cherryPickup(grid):
    n = len(grid)
    NEG = float('-inf')

    @lru_cache(maxsize=None)
    def dfs(r1, c1, r2):
        c2 = r1 + c1 - r2
        if r1 >= n or c1 >= n or r2 >= n or c2 >= n:
            return NEG
        if grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return NEG
        if r1 == c1 == n - 1:
            return grid[r1][c1]

        got = grid[r1][c1] + (0 if r1 == r2 else grid[r2][c2])
        rest = max(dfs(r1 + 1, c1, r2 + 1), dfs(r1 + 1, c1, r2),
                   dfs(r1, c1 + 1, r2 + 1), dfs(r1, c1 + 1, r2))
        return NEG if rest == NEG else got + rest

    return max(0, dfs(0, 0, 0))

    ┌─────────────────────────────────────────┐
    │         State Machine Flow              │
    └─────────────────────────────────────────┘

         buy            sell          cooldown
    REST ────→ HOLD ────→ SOLD ─────→ REST
     ↑                                   │
     └───────────────────────────────────┘

    Transitions:
    • REST → HOLD: Buy stock (rest - price)
    • HOLD → SOLD: Sell stock (hold + price)
    • SOLD → REST: Cooldown (no transaction)
    • REST → REST: Do nothing (rest)
    • HOLD → HOLD: Keep holding (hold)

At position (i, j):
  - If chars match: No cost, take solution from (i-1, j-1)
  - If they don't:
      Delete from word1:   dp[i-1][j] + 1
      Insert into word1:   dp[i][j-1] + 1
      Replace in word1:    dp[i-1][j-1] + 1
      → Take the minimum of these three

private int[][] memo;

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    memo = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            memo[i][j] = -1;
        }
    }
    return dfs(0, 0, word1, word2, m, n);
}

private int dfs(int i, int j, String word1, String word2, int m, int n) {
    // Base cases
    if (i == m) return n - j;
    if (j == n) return m - i;
    
    // Check memo
    if (memo[i][j] != -1) return memo[i][j];

    int res;
    if (word1.charAt(i) == word2.charAt(j)) {
        res = dfs(i + 1, j + 1, word1, word2, m, n);
    } else {
        res = 1 + Math.min(
            dfs(i + 1, j, word1, word2, m, n),      // Delete
            Math.min(
                dfs(i, j + 1, word1, word2, m, n),  // Insert
                dfs(i + 1, j + 1, word1, word2, m, n) // Replace
            )
        );
    }

    memo[i][j] = res;
    return res;
}

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    // Use 1D array instead of 2D (only need previous row)
    int[] prev = new int[n + 1];
    for (int j = 0; j <= n; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= m; i++) {
        int[] curr = new int[n + 1];
        curr[0] = i;
        
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = 1 + Math.min(
                    prev[j],        // Delete
                    Math.min(
                        curr[j - 1],    // Insert
                        prev[j - 1]     // Replace
                    )
                );
            }
        }
        
        prev = curr;
    }

    return prev[n];
}

Input: word1 = "horse", word2 = "ros"

       ""  r   o   s
    "" 0   1   2   3
    h  1   1   2   3
    o  2   2   1   2
    r  3   2   2   2
    s  4   3   3   2
    e  5   4   4   3

Result: dp[5][3] = 3 operations
Explanation: 
  - Replace 'h' → 'r': "rorse"
  - Delete 'r': "rose"
  - Delete 'e': "ros"

Three cases at first mismatch position i:
  len(s) == len(t) → Replace s[i]:  check s[i+1..] == t[i+1..]
  len(s) <  len(t) → Insert into s: check s[i..]   == t[i+1..]
  len(s) >  len(t) → Delete from s: check s[i+1..] == t[i..]

// LC 161 - One Edit Distance  O(n) time, O(1) space
public boolean isOneEditDistance(String s, String t) {
    int ns = s.length(), nt = t.length();
    if (ns > nt) return isOneEditDistance(t, s); // ensure s is shorter
    if (nt - ns > 1) return false;               // gap > 1 → impossible

    for (int i = 0; i < ns; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            if (ns == nt) {
                // Replace: rest of both strings must match
                return s.substring(i + 1).equals(t.substring(i + 1));
            } else {
                // Insert into s (skip one char in t)
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
    }
    // No mismatch in s — valid only if t has one trailing extra char
    return ns + 1 == nt;
}

// LC 161 - DP approach
public boolean isOneEditDistance(String s, String t) {
    int ns = s.length(), nt = t.length();
    if (Math.abs(ns - nt) > 1) return false;

    int[][] dp = new int[ns + 1][nt + 1];
    for (int i = 0; i <= ns; i++) dp[i][0] = i;
    for (int j = 0; j <= nt; j++) dp[0][j] = j;

    for (int i = 1; i <= ns; i++) {
        for (int j = 1; j <= nt; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                               Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[ns][nt] == 1;
}

| Operation | DP Cell Used  | Meaning                                      |
|-----------|---------------|----------------------------------------------|
| Insert    | dp[i][j-1]    | Already matched s[0..i] to t[0..j-1], then insert t[j] |
| Delete    | dp[i-1][j]    | Already matched s[0..i-1] to t[0..j], then delete s[i] |
| Replace   | dp[i-1][j-1]  | Already matched s[0..i-1] to t[0..j-1], then swap s[i]→t[j] |

       ""   a    c    b
  ""  [ 0][ 1][ 2][ 3]
  a   [ 1][ 0][ 1][ 2]
  b   [ 2][ 1][ 1][ 1]

s[1] = 'b',  t[2] = 'b'   → chars MATCH → dp[2][3] = dp[1][2] = 1  ✓

Option 1 — INSERT 'c' into s after "a":
    We already know it takes dp[1][1] = 0 ops to match "a"→"a",
    then we insert 'c' → dp[1][1] + 1 = 1
    → uses dp[i][j-1]  (same row, one column back = t is one char shorter)

Option 2 — DELETE s[0]='a' from s:
    We already know it takes dp[0][2] = 2 ops to match ""→"ac",
    then we delete 'a' → dp[0][2] + 1 = 3
    → uses dp[i-1][j]  (one row up = s is one char shorter)

Option 3 — REPLACE s[0]='a' with t[1]='c':
    We already know it takes dp[0][1] = 1 op to match ""→"a",
    then swap 'a'→'c' → dp[0][1] + 1 = 2
    → uses dp[i-1][j-1]  (diagonal = both strings one char shorter)

→ dp[1][2] = min(1, 3, 2) = 1

dp[i-1][j-1]  dp[i-1][j]
     ↘              ↓
dp[i][j-1]  →   dp[i][j]

  ↘ Replace      ↓ Delete (from s)
  → Insert (into s, advance t only)

# IDEA: build dp table by increasing substring length
# dp[i][j] = True if s[i:j+1] is palindrome
def countSubstrings_dp_length(s):
    # time = O(n^2), space = O(n^2)
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    for length in range(1, n + 1):          # outer: substring length
        for i in range(n - length + 1):     # inner: start index
            j = i + length - 1              # end index

            if length == 1:
                dp[i][j] = True
            elif length == 2:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])

            if dp[i][j]:
                count += 1

    return count

# IDEA: reuse previously computed palindrome radii to skip redundant checks
def countSubstrings_manacher(s):
    # time = O(n), space = O(n)
    def manacher(s):
        # transform: "abc" → "^#a#b#c#$"
        t = '^#' + '#'.join(s) + '#$'
        P = [0] * len(t)
        C = R = 0
        for i in range(1, len(t) - 1):
            mirror = 2 * C - i
            if R > i:
                P[i] = min(R - i, P[mirror])
            while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
                P[i] += 1
            if i + P[i] > R:
                C, R = i, i + P[i]
        return P

    return sum((r + 1) // 2 for r in manacher(s))

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]     # Tribonacci (same shape as LC 1137)

dp[0] = 1   # one way to eat nothing (the empty sequence of bites)
dp[1] = 1   # (1)
dp[2] = 2   # (1,1) (2)
dp[3] = 4   # (1,1,1) (1,2) (2,1) (3)

# python
# IDEA: keep a sliding window of the last 3 dp values instead of a dp array
# time = O(n), space = O(1)
def get_ways(n):
    # 1. Base / edge cases
    if n == 0:
        return 0          # "no way to eat a bar that doesn't exist"
    if n <= 2:
        return n          # dp[1] = 1, dp[2] = 2
    if n == 3:
        return 4

    # 2. Seed: p1, p2, p3 = dp[i-3], dp[i-2], dp[i-1] for the first i we compute (i = 4)
    p1, p2, p3 = 1, 2, 4  # dp[1], dp[2], dp[3]

    # 3. Transition + update
    for i in range(4, n + 1):
        dp = p1 + p2 + p3   # dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        # update: slide the window right by one
        p1 = p2             # new dp[i-3] is the old dp[i-2]
        p2 = p3             # new dp[i-2] is the old dp[i-1]
        p3 = dp             # new dp[i-1] is the dp[i] we just computed

    return dp

at the top of iteration i:   p1 = dp[i-3],  p2 = dp[i-2],  p3 = dp[i-1]

i        p1      p2      p3      dp = p1+p2+p3
----------------------------------------------
(seed)  dp1=1   dp2=2   dp3=4        -
4         1       2       4        7      <- dp[4] = 1+2+4
  update: p1<-2, p2<-4, p3<-7
5         2       4       7       13      <- dp[5] = 2+4+7
  update: p1<-4, p2<-7, p3<-13
6         4       7      13       24      <- dp[6] = 4+7+13

answer = 24

window slides right one slot per iteration:
dp:  [1] [2] [4]  7   13   24
      ^p1 ^p2 ^p3            i=4
          ^p1 ^p2 ^p3        i=5
              ^p1 ^p2 ^p3    i=6

# python
# ❌ WRONG — p3 is clobbered before p2 reads it
p3 = dp     # p3 destroyed
p2 = p3     # p2 gets dp[i], not dp[i-1]
p1 = p2     # p1 gets dp[i] too — all three collapse to the same value

# ✅ RIGHT — each read happens before its target is overwritten
p1 = p2
p2 = p3
p3 = dp

# ✅ ALSO RIGHT — tuple assignment evaluates the whole RHS first, so order is irrelevant
p1, p2, p3 = p2, p3, dp

// java
// IDEA: same 3-variable rolling window; shift oldest -> newest
// time = O(n), space = O(1)
public int getWays(int n) {
    if (n == 0) return 0;
    if (n <= 2) return n;
    if (n == 3) return 4;

    int p1 = 1, p2 = 2, p3 = 4;   // dp[1], dp[2], dp[3]
    int dp = p3;
    for (int i = 4; i <= n; i++) {
        dp = p1 + p2 + p3;
        p1 = p2;                  // must go oldest -> newest
        p2 = p3;
        p3 = dp;
    }
    return dp;
}

# python
if n == 0:
    return 0        # answer for the caller
p0 = 1              # seed for the recurrence — a different number on purpose

# python
# IDEA: k-step rolling window with a deque — O(k) space instead of O(n)
#       returns the recurrence value, so ways_k(0, k) == dp[0] == 1
# time = O(n), space = O(k)
from collections import deque

def ways_k(n, k):
    window = deque([1])            # dp[0] = 1
    total = 1                      # running sum of the window
    for i in range(1, n + 1):
        cur = total
        window.append(cur)
        total += cur
        if len(window) > k:        # drop dp[i-k], it's out of range now
            total -= window.popleft()
    return window[-1]

# python
# IDEA: circular buffer — dp[i] lives at index i % k, no shifting at all
# time = O(n * k), space = O(k)
def ways_k_mod(n, k):
    dp = [0] * k
    dp[0] = 1                      # dp[0] = 1
    for i in range(1, n + 1):
        dp[i % k] = sum(dp[(i - j) % k] for j in range(1, min(k, i) + 1))
    return dp[n % k]

def state_compression_dp(graph):
    """Traveling Salesman Problem using bitmask DP"""
    n = len(graph)
    # dp[mask][i] = min cost to visit all cities in mask, ending at city i
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at city 0

    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue

            for v in range(n):
                if mask & (1 << v):
                    continue

                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v],
                                    dp[mask][u] + graph[u][v])

    # Return to starting city
    return min(dp[(1 << n) - 1][i] + graph[i][0] for i in range(1, n))

words = ["a","b","ba","bca","bda","bdca"]
Sorted: ["a","b","ba","bca","bda","bdca"]

dp["a"]    = 1  (no predecessors)
dp["b"]    = 1  (no predecessors)
dp["ba"]   = 2  (remove 'b' → "a" exists, remove 'a' → "b" exists → max(dp["a"], dp["b"]) + 1 = 2)
dp["bca"]  = 3  (remove 'c' → "ba" exists → dp["ba"] + 1 = 3)
dp["bda"]  = 3  (remove 'd' → "ba" exists → dp["ba"] + 1 = 3)
dp["bdca"] = 4  (remove 'c' → "bda" exists → dp["bda"] + 1 = 4)

Answer: 4

public int longestStrChain(String[] words) {
    // Step 1: Sort by word length (process predecessors before successors)
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    // Step 2: dp[word] = longest chain ending at this word
    Map<String, Integer> dp = new HashMap<>();
    int maxChain = 1;

    for (String word : words) {
        int best = 1;

        // Step 3: Try removing each character to generate all predecessors
        for (int i = 0; i < word.length(); i++) {
            String prev = word.substring(0, i) + word.substring(i + 1);
            // If predecessor exists, extend its chain
            best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
        }

        dp.put(word, best);
        maxChain = Math.max(maxChain, best);
    }

    return maxChain;
}

private Map<Integer, List<String>> wordLengthMap;
private Map<String, Integer> memo;

public int longestStrChain(String[] words) {
    // Group words by length for O(1) lookup of next-length candidates
    wordLengthMap = new HashMap<>();
    for (String word : words) {
        wordLengthMap.putIfAbsent(word.length(), new ArrayList<>());
        wordLengthMap.get(word.length()).add(word);
    }

    int maxPath = 1;
    memo = new HashMap<>();
    for (String word : words)
        maxPath = Math.max(maxPath, dfs(word));

    return maxPath;
}

private int dfs(String word) {
    // Base case: no words of next length exist
    if (!wordLengthMap.containsKey(word.length() + 1)) return 1;
    if (memo.containsKey(word)) return memo.get(word);

    int maxPath = 0;
    // Try all words of length+1 as potential successors
    for (String nextWord : wordLengthMap.get(word.length() + 1)) {
        if (isOneOff(word, nextWord))
            maxPath = Math.max(maxPath, dfs(nextWord));
    }

    memo.put(word, maxPath + 1);
    return memo.get(word);
}

// Two-pointer: returns true if b has exactly one more char than a
private boolean isOneOff(String a, String b) {
    int count = 0;
    for (int i = 0, j = 0; i < b.length() && j < a.length() && count <= 1; i++) {
        if (a.charAt(j) != b.charAt(i)) count++;
        else j++;
    }
    return count <= 1;
}

sort jobs by endTime
dp[i] = max profit using the first i jobs (sorted order)

take    : profit[i] + dp[p(i)]     where p(i) = # of jobs whose end <= start[i]
skip    : dp[i-1]
dp[i]   = max(take, skip)

p(i) is found by binary search over the (sorted) end times already in dp.

// java
// LC 1235 - Maximum Profit in Job Scheduling
// IDEA: sort by end time; dp[i] = best profit among first i jobs;
//       binary search the last job that finishes at or before job i's start.
// time = O(n log n), space = O(n)
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    int[][] jobs = new int[n][3];
    for (int i = 0; i < n; i++) {
        jobs[i] = new int[]{endTime[i], startTime[i], profit[i]};
    }
    Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0])); // by end time

    int[] ends = new int[n + 1];   // ends[0] = 0  (sentinel "no job")
    int[] dp = new int[n + 1];     // dp[0]   = 0

    for (int i = 1; i <= n; i++) {
        int s = jobs[i - 1][1], p = jobs[i - 1][2];

        /** NOTE !!! binary search on ends[0..i-1] :
         *  largest idx with ends[idx] <= s  ->  dp[idx] is the compatible prefix
         */
        int lo = 0, hi = i - 1, idx = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (ends[mid] <= s) { idx = mid; lo = mid + 1; }
            else { hi = mid - 1; }
        }

        dp[i] = Math.max(dp[i - 1], dp[idx] + p);  // skip vs take
        ends[i] = jobs[i - 1][0];
    }
    return dp[n];
}

# python
# LC 1235 - Maximum Profit in Job Scheduling
# IDEA: sort by end time, dp is non-decreasing, so bisect over the end-time list
# time = O(n log n), space = O(n)
import bisect

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(endTime, startTime, profit))   # sort by end time
    ends = [0]      # sentinel: "no job taken"
    dp = [0]

    for e, s, p in jobs:
        # last job whose end <= s  (compatible predecessor)
        i = bisect.bisect_right(ends, s) - 1
        dp.append(max(dp[-1], dp[i] + p))            # skip vs take
        ends.append(e)

    return dp[-1]

# python
# LC 1751 - Maximum Number of Events That Can Be Attended II
# IDEA: LC 1235 + a "how many picks left" dimension; dp[i][t] = best value using
#       first i events (sorted by end) while attending at most t of them.
# time = O(n * k * log n), space = O(n * k)
import bisect

def maxValue(events, k):
    events.sort(key=lambda e: e[1])                   # by end day
    n = len(events)
    ends = [0] + [e[1] for e in events]
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        s, e, v = events[i - 1]
        # last event ending strictly before s (days are inclusive)
        j = bisect.bisect_right(ends, s - 1, 0, i) - 1
        for t in range(1, k + 1):
            dp[i][t] = max(dp[i - 1][t],              # skip event i
                           dp[j][t - 1] + v)          # take event i
    return dp[n][k]

dp[k][i] = best cost to cover jobs[i:] using exactly k blocks

dp[k][i] = min over j in [i, n-k] of ( cost(i..j) + dp[k-1][j+1] )
                                       ^ this block   ^ the rest

base: dp[0][n] = 0, dp[0][i<n] = INF   (0 blocks must consume 0 jobs)
answer: dp[d][0];  impossible when n < d

// java
// LC 1335 - Minimum Difficulty of a Job Schedule
// IDEA: dp[day][i] = min total difficulty to finish jobs[i:] in `day` days;
//       inner loop grows the current day's block, tracking its running max.
// time = O(d * n^2), space = O(n)  (rolling over the day dimension)
public int minDifficulty(int[] jobDifficulty, int d) {
    int n = jobDifficulty.length;
    if (n < d) return -1;                 // not enough jobs: each day needs >= 1

    final int INF = Integer.MAX_VALUE / 2;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, INF);
    dp[n] = 0;                            // 0 jobs left with 0 days left

    for (int day = 1; day <= d; day++) {
        int[] ndp = new int[n + 1];
        Arrays.fill(ndp, INF);
        // i can start at most at n-day, leaving >= 1 job per remaining day
        for (int i = 0; i <= n - day; i++) {
            int mx = 0;
            for (int j = i; j <= n - day; j++) {   // today handles jobs[i..j]
                mx = Math.max(mx, jobDifficulty[j]);
                ndp[i] = Math.min(ndp[i], mx + dp[j + 1]);
            }
        }
        dp = ndp;
    }
    return dp[0];
}

# python
# LC 1335 - Minimum Difficulty of a Job Schedule
# IDEA: same recurrence, rolling 1D array over the "day" dimension
# time = O(d * n^2), space = O(n)
def minDifficulty(jobDifficulty, d):
    n = len(jobDifficulty)
    if n < d:
        return -1

    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[n] = 0                                   # 0 jobs left, 0 days left

    for day in range(1, d + 1):
        ndp = [INF] * (n + 1)
        for i in range(n - day + 1):            # start of today's block
            mx = 0
            for j in range(i, n - day + 1):     # end of today's block
                mx = max(mx, jobDifficulty[j])
                if dp[j + 1] < INF:
                    ndp[i] = min(ndp[i], mx + dp[j + 1])
        dp = ndp

    return dp[0]

# python
# LC 410 - Split Array Largest Sum
# IDEA: dp[t][i] = min possible "largest subarray sum" when splitting nums[:i] into t parts
# time = O(k * n^2), space = O(k * n)
def splitArray(nums, k):
    n = len(nums)
    pre = [0] * (n + 1)
    for i, v in enumerate(nums):
        pre[i + 1] = pre[i] + v

    INF = float('inf')
    dp = [[INF] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 0

    for t in range(1, k + 1):
        for i in range(1, n + 1):
            for j in range(t - 1, i):           # last part = nums[j:i]
                dp[t][i] = min(dp[t][i], max(dp[t - 1][j], pre[i] - pre[j]))

    return dp[k][n]

state  : (stone index i, jump size k that landed on i)
init   : (0, 0)
move   : from (i, k) you may jump k-1, k or k+1 (must be > 0)
         land on stone at position stones[i] + nk  ->  state (j, nk)
answer : any state on the last stone is reachable

dp[i] = set of jump sizes that can land ON stone i

// java
// LC 403 - Frog Jump
// IDEA: dp.get(i) = set of jump sizes that can land on stone i;
//       push forward to stones[i] + (k-1 | k | k+1) via a position -> index map.
// time = O(n^2), space = O(n^2)
public boolean canCross(int[] stones) {
    int n = stones.length;
    Map<Integer, Integer> pos = new HashMap<>();   // stone position -> index
    for (int i = 0; i < n; i++) pos.put(stones[i], i);

    List<Set<Integer>> dp = new ArrayList<>();
    for (int i = 0; i < n; i++) dp.add(new HashSet<>());
    dp.get(0).add(0);                              // start: landed with jump 0

    for (int i = 0; i < n; i++) {
        for (int k : dp.get(i)) {
            for (int nk = k - 1; nk <= k + 1; nk++) {
                if (nk <= 0) continue;             // jump must move forward
                Integer j = pos.get(stones[i] + nk);
                /** NOTE !!! j > i guarantees we only write to FUTURE stones,
                 *  so mutating dp while scanning is safe. */
                if (j != null && j > i) dp.get(j).add(nk);
            }
        }
    }
    return !dp.get(n - 1).isEmpty();
}

# python
# LC 403 - Frog Jump
# IDEA: dp[i] = set of jump sizes that can land on stone i (forward propagation)
# time = O(n^2), space = O(n^2)
def canCross(stones):
    n = len(stones)
    pos = {s: i for i, s in enumerate(stones)}     # position -> index
    dp = [set() for _ in range(n)]
    dp[0].add(0)                                   # start with jump size 0

    for i in range(n):
        for k in dp[i]:
            for nk in (k - 1, k, k + 1):
                if nk <= 0:
                    continue
                j = pos.get(stones[i] + nk)
                if j is not None and j > i:        # only forward
                    dp[j].add(nk)

    return len(dp[n - 1]) > 0

dp[i][d] = number of subsequences of length >= 2 ending at i with common difference d

for each j < i, d = nums[i] - nums[j]:
    cnt = dp[j][d]           # each of these has length >= 2 ...
    ans += cnt               # ... so appending i makes it length >= 3  -> a real answer
    dp[i][d] += cnt + 1      # cnt extended subsequences, plus the new pair (j, i)

// java
// LC 446 - Arithmetic Slices II - Subsequence
// IDEA: dp.get(i) maps a common difference -> how many length>=2 subsequences end at i
//       with that difference. Each one becomes a length>=3 answer when i extends it.
// time = O(n^2), space = O(n^2)
public int numberOfArithmeticSlices(int[] nums) {
    int n = nums.length, ans = 0;
    List<Map<Long, Integer>> dp = new ArrayList<>();
    for (int i = 0; i < n; i++) dp.add(new HashMap<>());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // NOTE !!! (long) cast — nums[i] - nums[j] overflows int on the real test data
            long d = (long) nums[i] - nums[j];
            int cnt = dp.get(j).getOrDefault(d, 0);
            ans += cnt;                       // only length>=3 chains are answers
            dp.get(i).merge(d, cnt + 1, Integer::sum);   // +1 = the new pair (j, i)
        }
    }
    return ans;
}

# python
# LC 446 - Arithmetic Slices II - Subsequence
# IDEA: same table, one defaultdict per index; report cnt (length>=3) but store cnt+1
# time = O(n^2), space = O(n^2)
from collections import defaultdict

def numberOfArithmeticSlices(nums):
    n = len(nums)
    dp = [defaultdict(int) for _ in range(n)]
    ans = 0
    for i in range(n):
        for j in range(i):
            d = nums[i] - nums[j]
            cnt = dp[j].get(d, 0)             # .get, not [d] — [d] would insert a 0 entry
            ans += cnt
            dp[i][d] += cnt + 1
    return ans

dp[k][m] = dp[k-1][m-1]      floors BELOW the drop  (egg broke:      k-1 eggs, m-1 moves)
         + dp[k][m-1]        floors ABOVE the drop  (egg survived:   k   eggs, m-1 moves)
         + 1                 the floor you dropped from

answer = the smallest m with dp[k][m] >= n

// java
// LC 887 - Super Egg Drop
// IDEA: invert the table — dp[j] = how many floors j eggs can resolve in the moves so far.
//       Grow `m` until k eggs cover n floors; that m is the answer.
// time = O(k * m) with m = the answer (m <= n, and far smaller in practice)
// space = O(k)
public int superEggDrop(int k, int n) {
    int[] dp = new int[k + 1];        // dp[j] = floors resolvable with j eggs in m moves
    int m = 0;
    while (dp[k] < n) {
        m++;
        // NOTE !!! descending j, so dp[j - 1] still holds the value for m - 1 moves
        for (int j = k; j >= 1; j--) {
            dp[j] = dp[j] + dp[j - 1] + 1;
        }
    }
    return m;
}

# python
# LC 887 - Super Egg Drop
# IDEA: dp[j] = floors coverable with j eggs and the current number of moves
# time = O(k * m), space = O(k)
def superEggDrop(k, n):
    dp = [0] * (k + 1)
    m = 0
    while dp[k] < n:
        m += 1
        for j in range(k, 0, -1):     # descending: dp[j - 1] is still the m-1 value
            dp[j] = dp[j] + dp[j - 1] + 1
    return m

m=1 : dp = [0, 1, 1]     2 eggs, 1 move  -> 1 floor
m=2 : dp = [0, 2, 3]     2 eggs, 2 moves -> 3 floors
m=3 : dp = [0, 3, 6]     2 eggs, 3 moves -> 6 floors  >= 6  ->  answer 3

dp[t][v] = ways (or probability) to be at state v after t steps
dp[t][v] = sum over u with edge u -> v of dp[t-1][u]

counting     -> take everything mod 1e9+7
probability  -> divide each contribution by the out-degree

// java
// LC 935 - Knight Dialer
// IDEA: dp[d] = # of distinct numbers of current length ending on digit d;
//       one layer per additional dialed digit.
// time = O(n * 10 * 3) = O(n), space = O(10) = O(1)
public int knightDialer(int n) {
    final int MOD = 1_000_000_007;
    // knight moves on the phone pad (5 is unreachable)
    int[][] moves = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{0,1,7},{2,6},{1,3},{2,4}};

    long[] dp = new long[10];
    Arrays.fill(dp, 1);                 // length-1 numbers: each digit once

    for (int step = 1; step < n; step++) {
        long[] ndp = new long[10];
        for (int d = 0; d < 10; d++) {
            for (int nxt : moves[d]) {
                ndp[nxt] = (ndp[nxt] + dp[d]) % MOD;
            }
        }
        dp = ndp;                       // roll the layer
    }

    long res = 0;
    for (long v : dp) res = (res + v) % MOD;
    return (int) res;
}

# python
# LC 935 - Knight Dialer
# IDEA: same layer-rolling; MOVES is the knight-move adjacency of the keypad
# time = O(n), space = O(1)
MOD = 10 ** 9 + 7
MOVES = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8], 4: [0, 3, 9],
         5: [],     6: [0, 1, 7], 7: [2, 6], 8: [1, 3], 9: [2, 4]}

def knightDialer(n):
    dp = [1] * 10                       # numbers of length 1
    for _ in range(n - 1):
        ndp = [0] * 10
        for d in range(10):
            for nxt in MOVES[d]:
                ndp[nxt] = (ndp[nxt] + dp[d]) % MOD
        dp = ndp
    return sum(dp) % MOD

# python
# LC 688 - Knight Probability in Chessboard
# IDEA: dp[r][c] = probability of standing on (r,c) after t moves; spread /8 each step
# time = O(k * n^2 * 8), space = O(n^2)
def knightProbability(n, k, row, column):
    dirs = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
    dp = [[0.0] * n for _ in range(n)]
    dp[row][column] = 1.0

    for _ in range(k):
        ndp = [[0.0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                if dp[r][c] == 0.0:
                    continue
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:   # off-board = fell off
                        ndp[nr][nc] += dp[r][c] / 8.0
        dp = ndp

    return sum(map(sum, dp))

# python
# LC 1269 - Number of Ways to Stay in the Same Place After Some Steps
# IDEA: dp[i] = ways to be at index i; each step move left / stay / right
# time = O(steps * min(arrLen, steps/2)), space = O(min(arrLen, steps/2))
def numWays(steps, arrLen):
    MOD = 10 ** 9 + 7
    m = min(arrLen, steps // 2 + 1)     # unreachable indices pruned away
    dp = [0] * m
    dp[0] = 1

    for _ in range(steps):
        ndp = [0] * m
        for i in range(m):
            if dp[i]:
                for j in (i - 1, i, i + 1):
                    if 0 <= j < m:
                        ndp[j] = (ndp[j] + dp[i]) % MOD
        dp = ndp

    return dp[0]                        # must end back at index 0

from collections import deque

# LC 1425 Constrained Subsequence Sum
def constrainedSubsetSum(nums, k):
    n = len(nums)
    dp = nums[:]       # dp[i] = max sum of subsequence ending at i
    dq = deque()       # decreasing deque of indices by dp value

    for i in range(n):
        # Best previous dp in window [i-k, i-1]
        if dq and dp[dq[0]] > 0:
            dp[i] = max(dp[i], dp[dq[0]] + nums[i])
        # Maintain decreasing order
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
        # Remove elements outside window
        if dq[0] == i - k:
            dq.popleft()

    return max(dp)

def largestRectangleArea(heights):
    stack = []   # increasing stack of indices
    max_area = 0
    heights.append(0)   # sentinel to flush stack

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

# LC 85 Maximal Rectangle in Matrix — apply LC 84 row by row
def maximalRectangle(matrix):
    if not matrix: return 0
    n = len(matrix[0])
    heights = [0] * n
    ans = 0
    for row in matrix:
        heights = [heights[j] + int(row[j]) if row[j] != '0' else 0 for j in range(n)]
        ans = max(ans, largestRectangleArea(heights[:]))
    return ans

START: What type of problem are you solving?
│
├─ Working with a SINGLE SEQUENCE/ARRAY?
│  │
│  ├─ Linear dependencies (dp[i] from dp[i-1]) → Category 1 (Linear DP)
│  │                                               Examples: LC 70, 198, 300
│  │
│  └─ Selection with constraints → Category 6 (Knapsack DP)
│                                    Examples: LC 416, 494, 518
│
├─ Working with a 2D GRID/MATRIX?
│  │
│  └─ Path counting, min/max path → Category 2 (Grid/2D DP)
│                                     Examples: LC 62, 64, 221
│
├─ Working with INTERVALS/SUBARRAYS?
│  │
│  └─ Optimal split, merge, or partition → Category 3 (Interval DP)
│                                           Examples: LC 312, 1000, 516
│
├─ Working with TREE structures?
│  │
│  ├─ State at node depends on children → Category 4 (Tree DP)
│  │                                       Examples: LC 337, 968, 124
│  │
│  └─ "For every node, compute ..." → Re-rooting DP (two-pass DFS)
│                                       Examples: LC 834, 2581
│
├─ Working with STRINGS?
│  │
│  ├─ Two strings (matching/alignment) → Category 7 (String DP)
│  │                                      Examples: LC 72, 1143, 583
│  │
│  └─ Single string (palindrome, split) → Also Category 7
│                                          Examples: LC 5, 131, 647
│
├─ Problem has MULTIPLE STATES with transitions?
│  │
│  └─ Stock trading, state machines → Category 5 (State Machine DP)
│                                      Examples: LC 122, 309, 714
│
└─ Need to track SUBSET/VISITED items efficiently?
   │
   └─ Use bitmask to compress state → Category 8 (State Compression DP)
                                       Examples: LC 691, 847, 1723

# Fibonacci-like
dp[i] = dp[i-1] + dp[i-2]

# Include/exclude current
dp[i] = dp[i-1] + (dp[i-2] + nums[i])

# Take or skip
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

# Best from all previous
dp[i] = max(dp[j] + score(j, i) for j < i)

# Path counting
dp[i][j] = dp[i-1][j] + dp[i][j-1]

# Min path
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

# From O(n²) to O(n)
# Instead of dp[i][j], use dp[2][j]
curr = [0] * n
prev = [0] * n
for i in range(m):
    curr, prev = prev, curr
    # Update curr based on prev

# From O(n) to O(1) for Fibonacci-like
prev2, prev1 = 0, 1
for i in range(2, n):
    curr = prev1 + prev2
    prev2, prev1 = prev1, curr

Stock/Transaction Problem?
├─ NO → Check other DP patterns
└─ YES → Continue below

Are there any constraints on transactions?
├─ NO constraints (unlimited) → 2 states (hold/cash) [LC 122]
├─ Cooldown period → 3 states (hold/sold/rest) [LC 309]
├─ Transaction fee → 2 states + fee deduction [LC 714]
├─ Limited k transactions → 2k states [LC 123, LC 188]
└─ Buy only once → Kadane's algorithm [LC 121]

Stock Problems State Transitions:
  held    = max(held,      rest - price)    # buy: rest → held
  sold    = held + price                    # sell: held → sold
  rest    = max(rest,      sold)            # cooldown: sold → rest

Variants:
  - No cooldown (LC 122):   held = max(held, rest - price); rest = max(rest, sold); sold = held_prev + price
  - With cooldown (LC 309): above with sold → rest (not directly back to held)
  - At most k tx (LC 188):  held[k] = max(held[k], rest[k-1] - price); sold[k] = held[k] + price
  - With fee (LC 714):      held = max(held, rest - price); rest = max(rest, held + price - fee)