def dp_solution(input_data):
    # Step 1: Define state
    # dp[i] represents...
    
    # Step 2: Initialize base cases
    dp = initialize_dp_array()
    dp[0] = base_value
    
    # Step 3: State transition
    for i in range(1, n):
        # Apply recurrence relation
        dp[i] = f(dp[i-1], dp[i-2], ...)
    
    # Step 4: Return answer
    return dp[n-1]

def linear_dp(nums):
    """Classic 1D DP for sequence problems"""
    n = len(nums)
    if n == 0:
        return 0

    # State: dp[i] = optimal value at position i
    dp = [0] * n
    dp[0] = nums[0]

    for i in range(1, n):
        # Transition: current vs previous
        dp[i] = max(dp[i-1], nums[i])
        # Or with skip: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[n-1]

# Approach 1: Array size = n (index-based)
def rob_v1(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):  # Loop to n
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[n-1]  # Answer at last index

# Approach 2: Array size = n+1 (count-based)
def rob_v2(nums):
    n = len(nums)
    dp = [0] * (n + 1)  # Extra space for "0 houses"
    dp[0] = 0  # Robbing 0 houses = 0
    dp[1] = nums[0] if n > 0 else 0

    for i in range(2, n + 1):  # Loop to n+1
        dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])  # Note: nums[i-1]

    return dp[n]  # Answer at position n

# 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

# LC 322: Coin Change
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)  # Need amount+1
    dp[0] = 0  # Base case: 0 coins needed for amount 0

    for i in range(1, amount + 1):  # Loop to amount+1
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

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];
}

# Style 1: Array size = n+1 (RECOMMENDED for this problem)
def climbStairs_v1(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Style 2: Array size = n (requires careful handling)
def climbStairs_v2(n):
    if n <= 2:
        return n

    dp = [0] * n
    dp[0] = 1  # 1 way to reach step 1
    dp[1] = 2  # 2 ways to reach step 2

    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n-1]

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

    // Base: starting cell
    dp[0][0] = grid[0][0];

    // Base: first column — only one way (from above)
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    // Base: first row — only one way (from left)
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];

    // Fill rest: min of coming from above vs left
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);

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

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    ↑ from left (prev col, same row)
    }

    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 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]

for length in [2, 3, ..., n+1]:        # Build from small to large intervals
    for left in [0, 1, ..., n-length]: # Try all possible left boundaries
        right = left + length           # Calculate right boundary
        for k in [left+1, ..., right-1]: # Try each element as LAST
            # dp[left][right] = combine(dp[left][k], dp[k][right], cost)

def maxCoins(nums):
    """LC 312: Burst Balloons - Classic Interval DP"""
    n = len(nums)

    # Step 1: Add boundary balloons with value 1
    balloons = [1] + nums + [1]

    # Step 2: dp[i][j] = max coins from bursting balloons between i and j (exclusive)
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    # Step 3: Build from small intervals to large
    for length in range(2, n + 2):  # length of interval
        for left in range(n + 2 - length):  # left boundary
            right = left + length  # right boundary

            # Step 4: Try each balloon k as the LAST to burst in (left, right)
            for k in range(left + 1, right):
                # Coins from bursting k last (only left, k, right remain)
                coins = balloons[left] * balloons[k] * balloons[right]
                # Add coins from left and right subproblems
                total = coins + dp[left][k] + dp[k][right]
                dp[left][right] = max(dp[left][right], total)

    # Answer: burst all balloons between boundaries 0 and n+1
    return dp[0][n + 1]

// LC 312: Burst Balloons
public int maxCoins(int[] nums) {
    int n = nums.length;

    // Add boundaries: [1, ...nums..., 1]
    int[] balloons = new int[n + 2];
    balloons[0] = 1;
    balloons[n + 1] = 1;
    for (int i = 0; i < n; i++) {
        balloons[i + 1] = nums[i];
    }

    // dp[i][j] = max coins from bursting balloons between i and j (exclusive)
    int[][] dp = new int[n + 2][n + 2];

    // Iterate over interval lengths (from 2 up to n+1)
    for (int len = 2; len <= n + 1; len++) {
        // i is the left boundary
        for (int i = 0; i <= n + 1 - len; i++) {
            int j = i + len; // j is the right boundary

            // Pick k as the LAST balloon to burst in interval (i, j)
            for (int k = i + 1; k < j; k++) {
                int currentCoins = balloons[i] * balloons[k] * balloons[j];
                int total = currentCoins + dp[i][k] + dp[k][j];
                dp[i][j] = Math.max(dp[i][j], total);
            }
        }
    }

    return dp[0][n + 1];
}

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 knapsack_01(weights, values, capacity):
    """0/1 Knapsack problem"""
    n = len(weights)
    # dp[i][w] = max value with first i items, capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Take item i-1 if possible
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

def state_machine_dp(prices, fee=0):
    """DP with multiple states (stock problems)"""
    if not prices:
        return 0

    n = len(prices)
    # States: hold stock, not hold stock
    hold = -prices[0]
    cash = 0

    for i in range(1, n):
        # Transition between states
        prev_hold = hold
        hold = max(hold, cash - prices[i])  # Buy
        cash = max(cash, prev_hold + prices[i] - fee)  # Sell

    return cash

def state_machine_with_cooldown(prices):
    """
    DP with 3 states for stock with cooldown

    State Definition:
    - hold: Currently holding a stock
    - sold: Just sold a stock today (enters cooldown)
    - rest: In cooldown or doing nothing (not holding stock)

    Key Constraint: After selling, must cooldown for 1 day before buying again
    """
    if not prices:
        return 0

    # Initialize states
    hold = -prices[0]  # Buy on day 0
    sold = 0           # Can't sell on day 0
    rest = 0           # Doing nothing

    for i in range(1, len(prices)):
        prev_sold = sold

        # State transitions
        # 1. SOLD: Sell today (must have held yesterday)
        sold = hold + prices[i]

        # 2. HOLD: Either continue holding OR buy today (after cooldown)
        hold = max(hold, rest - prices[i])

        # 3. REST: Either rest again OR just finished cooldown from yesterday's sale
        rest = max(rest, prev_sold)

    # Max profit when not holding stock
    return max(sold, rest)

    ┌─────────────────────────────────────────┐
    │         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)

def top_down_dp(nums):
    """Top-down DP with memoization"""
    memo = {}

    def dp(i):
        # Base case
        if i < 0:
            return 0
        if i == 0:
            return nums[0]

        # Check memo
        if i in memo:
            return memo[i]

        # Recurrence relation
        result = max(dp(i-1), dp(i-2) + nums[i])
        memo[i] = result
        return result

    return dp(len(nums) - 1)

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;
}

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

If word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]  (no operation needed)
Else:
    dp[i][j] = 1 + min(
        dp[i-1][j],     # Delete from word1
        dp[i][j-1],     # Insert into word1
        dp[i-1][j-1]    # Replace in word1
    )

def minDistance(word1, word2):
    """LC 72: Edit Distance - Bottom-Up DP"""
    m, n = len(word1), len(word2)
    # dp[i][j] = min operations to convert word1[:i] to word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete
                    dp[i][j-1],    # Insert
                    dp[i-1][j-1]   # Replace
                )

    return dp[m][n]

// LC 72: Edit Distance - Standard approach
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();

    int[][] dp = new int[m + 1][n + 1];

    // Base cases
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;  // Delete all characters
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;  // Insert all characters
    }

    // Fill DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],    // Delete
                    Math.min(
                        dp[i][j - 1],    // Insert
                        dp[i - 1][j - 1] // Replace
                    )
                );
            }
        }
    }

    return dp[m][n];
}

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"

def lcs_dp(text1, text2):
    """LCS pattern for string matching"""
    m, n = len(text1), len(text2)
    # dp[i][j] = LCS length of text1[:i] and text2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

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))

def palindrome_dp(s):
    """Check palindromic substrings"""
    n = len(s)
    # dp[i][j] = True if s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]

    # Single characters are palindromes
    for i in range(n):
        dp[i][i] = True

    # Check 2-character palindromes
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True

    # Check longer palindromes
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True

    return dp

Core Transition Equation:
    dp[i][j] = true
       if:
           s[i] == s[j] AND
           (j - i <= 2 OR dp[i + 1][j - 1])

Explanation:
    - dp[i][j] represents whether substring s[i...j] is a palindrome
    - s[i] == s[j]: Characters at both ends must match
    - j - i <= 2: Handles base cases (length 1, 2, or 3 substrings)
    - dp[i + 1][j - 1]: Inner substring must also be a palindrome

Example: For "babad"
    - dp[0][2] = true because s[0]='b' == s[2]='b' AND j-i=2 (length 3)
    - dp[1][3] = true because s[1]='a' == s[3]='a' AND dp[2][2]=true

def fibonacci_variants():
    """Common Fibonacci-like patterns"""

    # 1. Classic Fibonacci
    def fibonacci(n):
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for _ in range(2, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

    # 2. Climbing Stairs
    def climbStairs(n):
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

    # 3. House Robber
    def rob(nums):
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)

        prev2, prev1 = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            current = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, current
        return prev1

def linear_dp_optimized(nums):
    """Space-optimized 1D DP"""
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    # Only need previous two states
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, n):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

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]

def knapsack_optimized(weights, values, capacity):
    """1D array knapsack"""
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        # Iterate backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

┌─────────────────────────────────────────────────────────────────────────┐
│                     DP KNAPSACK PATTERN MATRIX                          │
└─────────────────────────────────────────────────────────────────────────┘

                          COUNT WAYS              FIND MIN/MAX
                    ┌──────────────────┬──────────────────────────┐
                    │                  │                          │
ORDER MATTERS?      │  PERMUTATIONS    │   Not typically used     │
(Yes)              │  LC 377          │   (Use Permutations      │
                    │  Target→Item     │    for counting)         │
                    │  Forward         │                          │
                    ├──────────────────┼──────────────────────────┤
                    │                  │                          │
ORDER DOESN'T       │  COMBINATIONS    │   UNBOUNDED KNAPSACK     │
MATTER              │  LC 518          │   LC 322                 │
(No)                │  Item→Target     │   Item→Capacity          │
                    │  Forward         │   Forward                │
                    ├──────────────────┼──────────────────────────┤
                    │                  │                          │
USE EACH ONCE       │  Not typical     │   0/1 KNAPSACK           │
(Constraint)        │  (Can adapt      │   LC 416                 │
                    │   0/1 pattern)   │   Item→Capacity          │
                    │                  │   BACKWARD ⚠️            │
                    └──────────────────┴──────────────────────────┘

Legend:
  Item→Target     = Outer loop: items,    Inner loop: target
  Target→Item     = Outer loop: target,   Inner loop: items
  Forward         = Inner loop: i to target (allows reuse)
  BACKWARD ⚠️     = Inner loop: target to i (prevents reuse)

Start
  │
  ├─ Question asks "count ways"?
  │   │
  │   ├─ YES → Order matters?
  │   │         ├─ YES → Permutations (Target→Item) [LC 377]
  │   │         └─ NO  → Combinations (Item→Target) [LC 518]
  │   │
  │   └─ NO  → Question asks "min/max"?
  │             │
  │             ├─ Each item once?
  │             │   ├─ YES → 0/1 Knapsack (BACKWARD) [LC 416]
  │             │   └─ NO  → Unbounded (FORWARD) [LC 322]
  │             │
  │             └─ Unknown → Check problem constraints

// ============================================
// PATTERN 1: COMBINATIONS (Item → Target)
// ============================================
// LC 518: Coin Change II
public int countCombinations(int target, int[] items) {
    int[] dp = new int[target + 1];
    dp[0] = 1;  // Base: one way to make 0

    // OUTER: Items/Coins
    for (int item : items) {
        // INNER: Target/Amount (forward)
        for (int i = item; i <= target; i++) {
            dp[i] += dp[i - item];  // ← Same transition
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 2: PERMUTATIONS (Target → Item)
// ============================================
// LC 377: Combination Sum IV
public int countPermutations(int target, int[] items) {
    int[] dp = new int[target + 1];
    dp[0] = 1;  // Base: one way to make 0

    // OUTER: Target/Amount
    for (int i = 1; i <= target; i++) {
        // INNER: Items/Coins
        for (int item : items) {
            if (i >= item) {
                dp[i] += dp[i - item];  // ← Same transition
            }
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 3: 0/1 KNAPSACK (Item → Capacity BACKWARDS)
// ============================================
// LC 416: Partition Equal Subset Sum
public boolean canPartition(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // Base: can make 0

    // OUTER: Items
    for (int num : nums) {
        // INNER: Capacity (BACKWARDS to prevent reuse)
        for (int w = target; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];  // ← Different transition (OR)
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 4: UNBOUNDED KNAPSACK (Item → Capacity FORWARDS)
// ============================================
// LC 322: Coin Change (minimum coins)
public int minCoins(int target, int[] coins) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, target + 1);  // Infinity
    dp[0] = 0;  // Base: 0 coins for 0 amount

    // OUTER: Items/Coins
    for (int coin : coins) {
        // INNER: Target (FORWARDS allows reuse)
        for (int i = coin; i <= target; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);  // ← Different transition (MIN)
        }
    }
    return dp[target] > target ? -1 : dp[target];
}

Question: What does the problem ask for?

├─ "Count number of ways/combinations to reach target"
│  ├─ Order matters? (e.g., [1,2] ≠ [2,1])
│  │  ├─ YES → Use PERMUTATIONS pattern (Target → Item)
│  │  │         Example: LC 377 Combination Sum IV
│  │  └─ NO  → Use COMBINATIONS pattern (Item → Target)
│  │            Example: LC 518 Coin Change II
│  │
│  └─ Can reuse items?
│     ├─ YES → Unbounded, iterate forwards
│     └─ NO  → 0/1 Knapsack, iterate backwards
│
└─ "Find minimum/maximum value"
   ├─ Can reuse items?
   │  ├─ YES → Unbounded Knapsack (forwards)
   │  │         Example: LC 322 Coin Change (min coins)
   │  └─ NO  → 0/1 Knapsack (backwards)
   │            Example: LC 416 Partition Equal Subset Sum
   │
   └─ Always use (Item → Capacity) order

Given: stones = [2, 7, 4, 1, 8, 1]
Total sum = 23

Goal: Split into two groups with min |sum1 - sum2|

Mathematical insight:
  Let sum1 = S (sum of group 1)
  Then sum2 = total - S (sum of group 2)
  
  Difference = |sum1 - sum2| = |S - (total - S)| = |2S - total|
  
  To minimize this: Maximize S such that S ≤ total/2
  
  Result = total - 2*S (where S is the largest achievable sum ≤ total/2)

public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int stone : stones) {
        total += stone;
    }

    int target = total / 2;
    
    // dp[j] = can we achieve sum j?
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // Base: always can make sum 0 (choose nothing)

    // For each stone
    for (int stone : stones) {
        // Iterate BACKWARDS to prevent using same stone twice
        for (int j = target; j >= stone; j--) {
            dp[j] = dp[j] || dp[j - stone];  // Can achieve j if:
                                              // (already could) OR (could make j-stone and add this stone)
        }
    }

    // Find largest achievable sum ≤ target
    for (int j = target; j >= 0; j--) {
        if (dp[j]) {
            return total - 2 * j;
        }
    }

    return 0;
}

public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int stone : stones) {
        total += stone;
    }

    int target = total / 2;
    
    // dp[j] = maximum sum we can achieve ≤ j
    int[] dp = new int[target + 1];
    dp[0] = 0;  // Base: can make sum 0

    // For each stone
    for (int stone : stones) {
        // Iterate BACKWARDS to prevent reuse
        for (int j = target; j >= stone; j--) {
            // Either skip this stone (dp[j])
            // Or include it and add to best we could do with j-stone (dp[j-stone] + stone)
            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
    }

    return total - 2 * dp[target];
}

❌ WRONG: Forward iteration (causes reuse)
for (int j = stone; j <= target; j++) {
    dp[j] = dp[j] || dp[j - stone];
}
Problem: When we update dp[j], we're using the NEW value of dp[j-stone]
         which might have already been updated by the same stone in this iteration.
         This allows using the same stone multiple times!

Example with stone=3, target=9:
  j=3: dp[3] = dp[0] = true ✓
  j=6: dp[6] = dp[3] = true ✓ BUT dp[3] was just updated by the same stone!
  j=9: dp[9] = dp[6] = true ✓ Again, using same stone multiple times!

✅ CORRECT: Backward iteration (prevents reuse)
for (int j = target; j >= stone; j--) {
    dp[j] = dp[j] || dp[j - stone];
}
Reason: We process from right to left, so dp[j-stone] is always from the PREVIOUS iteration
        (before this stone was considered). So we use each stone only once.

Example with stone=3, target=9:
  j=9: dp[9] = dp[6] (old value from previous stone) ✓
  j=6: dp[6] = dp[3] (old value from previous stone) ✓
  j=3: dp[3] = dp[0] (old value from previous stone) ✓

stones = [2, 7, 4, 1, 8, 1]
total = 23
target = 23 / 2 = 11

Initial: dp = [T, F, F, F, F, F, F, F, F, F, F, F]

After stone 2:
  dp[2] = T (can make sum 2)
  dp = [T, F, T, F, F, F, F, F, F, F, F, F]

After stone 7:
  dp[9] = T (can make 2+7)
  dp[7] = T
  dp[2] = T (unchanged)
  dp = [T, F, T, F, F, F, F, T, F, T, F, F]

After stone 4:
  dp[11] = T (can make 7+4)
  dp[9] = T (unchanged)
  dp[6] = T (can make 2+4)
  dp[4] = T
  dp = [T, F, T, F, T, F, T, T, F, T, F, T]

... continue for remaining stones ...

Final: Find largest j ≤ 11 where dp[j] = T
       Result = 23 - 2 * j

Question: Can we partition into two equal subsets?
Answer: Can we achieve sum = total/2?
DP: boolean[] dp where dp[j] = can we make sum j?
Return: dp[total/2]

Question: Assign +/- to reach target T
Transformation: Let sum1 = sum of items with +
                Let sum2 = sum of items with -
                sum1 - sum2 = T
                sum1 + sum2 = total (all items)
                
                Solving: sum1 = (total + T) / 2
                
So: This is 0/1 knapsack! Find count of subsets with sum = (total + T) / 2
DP: int[] dp where dp[j] = count of ways to make sum j
Return: dp[(total + T) / 2]

// LC 518: Coin Change II - Count combinations
// Example: [1,2] and [2,1] are the SAME combination
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // Base case: 1 way to make amount 0

    // OUTER LOOP: Iterate through each coin
    // This ensures we process all uses of one coin before moving to the next,
    // which prevents duplicate combinations like [1,2] and [2,1].
    for (int coin : coins) {
        // INNER LOOP: Update dp table for all amounts reachable by this coin
        for (int i = coin; i <= amount; i++) {
            // Number of ways to make amount 'i' is:
            // (Current ways) + (Ways to make 'i - coin')
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

After coin 1: dp = [1, 1, 1, 1]  // {}, {1}, {1,1}, {1,1,1}
After coin 2: dp = [1, 1, 2, 2]  // + {2}, {1,2}
Result: 2 combinations → {1,1,1}, {1,2}

// LC 377: Combination Sum IV - Count permutations
// Example: [1,2] and [2,1] are DIFFERENT permutations
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;

    // OUTER LOOP: Iterate through each amount
    // For each amount, try all coins to see which was "last added"
    for (int i = 1; i <= target; i++) {
        // INNER LOOP: Try each coin for current amount
        for (int num : nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];
}

dp[1]: Use 1 → [1] (1 way)
dp[2]: Use 1 → [1,1], Use 2 → [2] (2 ways)
dp[3]: From dp[2] add 1 → [1,1,1], [2,1]
       From dp[1] add 2 → [1,2]
Result: 3 permutations → {1,1,1}, {1,2}, {2,1}

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // Base: 1 way to make 0

    // CRITICAL: Coin outer loop = COMBINATIONS
    for (int coin : coins) {              // ← Process coins one by one
        for (int i = coin; i <= amount; i++) {  // ← Update all amounts for this coin
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

// Example: amount=3, coins=[1,2]
// Result: 2 combinations
// {1,1,1}, {1,2}  (Note: [1,2] and [2,1] counted as same)

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1; // Base: 1 way to make 0

    // CRITICAL: Amount outer loop = PERMUTATIONS
    for (int i = 1; i <= target; i++) {   // ← Process each amount
        for (int num : nums) {            // ← Try every number for this amount
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

// Example: target=3, nums=[1,2]
// Result: 3 permutations
// {1,1,1}, {1,2}, {2,1}  (Note: [1,2] and [2,1] are different)

Initialize: dp = [1, 0, 0, 0]

Process coin 1:
  i=1: dp[1] += dp[0] = 1    → [1, 1, 0, 0]  // ways: {1}
  i=2: dp[2] += dp[1] = 1    → [1, 1, 1, 0]  // ways: {1,1}
  i=3: dp[3] += dp[2] = 1    → [1, 1, 1, 1]  // ways: {1,1,1}

Process coin 2:
  i=2: dp[2] += dp[0] = 1+1=2 → [1, 1, 2, 1]  // ways: {1,1}, {2}
  i=3: dp[3] += dp[1] = 1+1=2 → [1, 1, 2, 2]  // ways: {1,1,1}, {1,2}
                                              // Note: Can't get {2,1} because
                                              // all coin-1 uses are done before coin-2

Final: dp[3] = 2  ✅ Only {1,1,1} and {1,2}

Initialize: dp = [1, 0, 0, 0]

i=1 (building sum 1):
  Try 1: dp[1] += dp[0] = 1   → [1, 1, 0, 0]  // ways: {1}
  Try 2: skip (2 > 1)

i=2 (building sum 2):
  Try 1: dp[2] += dp[1] = 1   → [1, 1, 1, 0]  // {1} + 1 = {1,1}
  Try 2: dp[2] += dp[0] = 1+1=2 → [1, 1, 2, 0]  // {} + 2 = {2}

i=3 (building sum 3):
  Try 1: dp[3] += dp[2] = 2   → [1, 1, 2, 2]  // {1,1} + 1 = {1,1,1}
                                              // {2} + 1 = {2,1}  ✅
  Try 2: dp[3] += dp[1] = 2+1=3 → [1, 1, 2, 3]  // {1} + 2 = {1,2}  ✅

Final: dp[3] = 3  ✅ All three: {1,1,1}, {1,2}, {2,1}

public int change(int amount, int[] coins) {
    // dp[i] = total number of combinations that make up amount i
    int[] dp = new int[amount + 1];

    // Base case: There is exactly 1 way to make 0 amount (empty set)
    dp[0] = 1;

    // CRITICAL: Coin outer loop = COMBINATIONS
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

Input: amount = 5, coins = [1,2,5]
Output: 4
Combinations: {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}

Input: amount = 3, coins = [2]
Output: 0
Explanation: Cannot make 3 with only coins of 2

// LC 518: Combinations
for (int coin : coins)              // ← ITEM OUTER
    for (int i = coin; i <= amount; i++)

// LC 377: Permutations
for (int i = 1; i <= target; i++)   // ← TARGET OUTER
    for (int num : nums)

public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;

    // dp[i] = min coins to make amount i
    int[] dp = new int[amount + 1];

    // Initialize with "Infinity" (amount + 1 is safe)
    Arrays.fill(dp, amount + 1);

    // Base case: 0 coins needed for 0 amount
    dp[0] = 0;

    // Iterate through every amount from 1 to amount
    for (int i = 1; i <= amount; i++) {
        // For each amount, try every coin
        for (int coin : coins) {
            // CRITICAL CONDITION: Check if coin fits
            if (i >= coin) {
                // DP equation: Min of (current value) OR
                // (1 coin + coins needed for remainder)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // If value is still "Infinity", we couldn't reach it
    return dp[amount] > amount ? -1 : dp[amount];
}

public int stringDP(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Step 1: Initialize base cases (empty string states)
    dp[0][0] = 0; // Both strings empty

    // Initialize first row (s1 is empty)
    for (int j = 1; j <= n; j++) {
        dp[0][j] = initValueForEmptyS1(j);
    }

    // Initialize first column (s2 is empty)
    for (int i = 1; i <= m; i++) {
        dp[i][0] = initValueForEmptyS2(i);
    }

    // Step 2: Fill the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // NOTE: Use i-1 and j-1 to access string characters
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                // Characters match
                dp[i][j] = transitionOnMatch(dp, i, j);
            } else {
                // Characters don't match
                dp[i][j] = transitionOnMismatch(dp, i, j);
            }
        }
    }

    return dp[m][n];
}

public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[] prev = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        int[] curr = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                curr[j] = prev[j-1] + 1; // Diagonal
            } else {
                curr[j] = Math.max(prev[j], curr[j-1]); // Top or left
            }
        }
        prev = curr; // Roll forward
    }

    return prev[n];
}

✅ CORRECT: 1-indexed approach
   dp[i][j] = answer for string1.substring(0, i) and string2.substring(0, j)
   - Row index i ∈ [0, m] where m = string1.length()
   - Col index j ∈ [0, n] where n = string2.length()
   - Character comparison: string1.charAt(i-1) vs string2.charAt(j-1)

❌ WRONG: 0-indexed approach (will cause boundary issues)
   - No room for "empty string" base case
   - First iteration accesses negative indices

Example: string1 = "abcde", string2 = "ace"

When i=3, j=2 (processing prefixes "abc" and "ac"):
  - DP state represents: LCS("abc", "ac")
  - We compare: string1.charAt(3-1) = 'c' with string2.charAt(2-1) = 'c'
  - The characters at POSITION (i-1) and (j-1) are what define the LAST character of each prefix

Index Mapping:
  i=0: prefix length 0 (empty string)
  i=1: prefix length 1 (first 1 char) → access string1[0]
  i=2: prefix length 2 (first 2 chars) → access string1[1]
  i=3: prefix length 3 (first 3 chars) → access string1[2]
  ...
  Therefore: when at dp[i][j], compare string1[i-1] with string2[j-1]

// Pattern: Two cases only
if (string1.charAt(i - 1) == string2.charAt(j - 1)) {
    // CASE 1: Characters match → extend previous best result
    // The matching characters contribute +1 to the LCS length
    dp[i][j] = 1 + dp[i - 1][j - 1];  // Diagonal: both strings move forward
} else {
    // CASE 2: Characters don't match → take best of skipping either string
    // We have two choices:
    //   Option A: Skip current char from string1 → dp[i-1][j]
    //   Option B: Skip current char from string2 → dp[i][j-1]
    // Take whichever gives the better result
    dp[i][j] = Math.max(dp[i - 1][j],    // Skip from string1
                       dp[i][j - 1]);    // Skip from string2
}

string1 = "abcde"
string2 = "ace"

DP Grid (showing values):
        ""  a   c   e
    ""  0   0   0   0
    a   0   1   1   1
    b   0   1   1   1
    c   0   1   2   2
    d   0   1   2   2
    e   0   1   2   3

How to read:
  dp[4][2] = 2 means LCS("abcd", "ac") has length 2
  dp[5][3] = 3 means LCS("abcde", "ace") has length 3 ✓

Key moments:
  - dp[1][1]: Compare 'a' with 'a' → match! → dp[0][0] + 1 = 1
  - dp[2][1]: Compare 'b' with 'a' → no match → max(dp[1][1], dp[2][0]) = 1
  - dp[3][2]: Compare 'c' with 'c' → match! → dp[2][1] + 1 = 2
  - dp[5][3]: Compare 'e' with 'e' → match! → dp[4][2] + 1 = 3

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();

    // Create (m+1) × (n+1) table to handle "empty string" base case
    int[][] dp = new int[m + 1][n + 1];
    // dp[0][j] and dp[i][0] are already 0 (empty string has LCS of 0)

    // Loop uses 1-based indices to represent prefix lengths
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // i represents prefix length in text1
            // j represents prefix length in text2
            // Compare character at position i-1 and j-1 (0-indexed)
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                // Characters match: extend the best previous result
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                // Characters don't match: choose best by skipping either string
                dp[i][j] = Math.max(dp[i - 1][j],    // Skip from text1
                                   dp[i][j - 1]);    // Skip from text2
            }
        }
    }

    return dp[m][n];  // Answer for full strings
}

dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1])   // take from s1
         || (dp[i][j-1] && s2[j-1] == s3[i+j-1])   // take from s2

public boolean checkValidString(String s) {
    int minParenCnt = 0; // minimum possible unmatched '('
    int maxParenCnt = 0; // maximum possible unmatched '('

    for (char c : s.toCharArray()) {
        if (c == '(') {
            minParenCnt++;
            maxParenCnt++;
        } else if (c == ')') {
            minParenCnt--;
            maxParenCnt--;
        } else { // '*' - wildcard
            minParenCnt--; // treat '*' as ')'
            maxParenCnt++; // treat '*' as '('
        }

        // If maxParenCnt < 0: too many unmatched ')'
        if (maxParenCnt < 0) return false;

        // If minParenCnt < 0: reset to 0 (can use '*' as empty)
        if (minParenCnt < 0) minParenCnt = 0;
    }

    // Valid if we can have 0 unmatched '('
    return minParenCnt == 0;
}

public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n + 1][n + 1];
    dp[0][0] = true; // empty string, 0 open parens

    for (int i = 1; i <= n; i++) {
        char c = s.charAt(i - 1);
        for (int j = 0; j <= n; j++) {
            if (c == '(') {
                // Add one open paren
                if (j > 0) dp[i][j] = dp[i - 1][j - 1];
            } else if (c == ')') {
                // Close one open paren
                if (j < n) dp[i][j] = dp[i - 1][j + 1];
            } else { // '*'
                // Option 1: treat '*' as empty
                dp[i][j] = dp[i - 1][j];
                // Option 2: treat '*' as '('
                if (j > 0) dp[i][j] |= dp[i - 1][j - 1];
                // Option 3: treat '*' as ')'
                if (j < n) dp[i][j] |= dp[i - 1][j + 1];
            }
        }
    }

    return dp[n][0]; // n chars processed, 0 open parens
}

public boolean checkValidString(String s) {
    int n = s.length();
    if (n == 0) return true;

    boolean[][] dp = new boolean[n][n];

    // Base case: single character valid only if '*'
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '*') dp[i][i] = true;
    }

    // Fill table for increasing lengths
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            // Option A: s[i] and s[j] form a matching pair
            if ((s.charAt(i) == '(' || s.charAt(i) == '*') &&
                (s.charAt(j) == ')' || s.charAt(j) == '*')) {
                if (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }

            // Option B: Split at some point k
            if (!dp[i][j]) {
                for (int k = i; k < j; k++) {
                    if (dp[i][k] && dp[k + 1][j]) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][n - 1];
}

public boolean checkValidString(String s) {
    int n = s.length();
    Boolean[][] memo = new Boolean[n + 1][n + 1];
    return dfs(0, 0, s, memo);
}

private boolean dfs(int i, int open, String s, Boolean[][] memo) {
    // Too many closing parens
    if (open < 0) return false;

    // End of string: valid if all matched
    if (i == s.length()) return open == 0;

    // Memoization
    if (memo[i][open] != null) return memo[i][open];

    boolean result;
    if (s.charAt(i) == '(') {
        result = dfs(i + 1, open + 1, s, memo);
    } else if (s.charAt(i) == ')') {
        result = dfs(i + 1, open - 1, s, memo);
    } else { // '*'
        result = dfs(i + 1, open, s, memo) ||        // empty
                 dfs(i + 1, open + 1, s, memo) ||    // '('
                 dfs(i + 1, open - 1, s, memo);      // ')'
    }

    memo[i][open] = result;
    return result;
}

public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n + 1][n + 1];
    dp[n][0] = true; // base: end with 0 open parens

    for (int i = n - 1; i >= 0; i--) {
        for (int open = 0; open < n; open++) {
            boolean res = false;
            if (s.charAt(i) == '*') {
                res |= dp[i + 1][open + 1];           // treat as '('
                if (open > 0) res |= dp[i + 1][open - 1]; // treat as ')'
                res |= dp[i + 1][open];                // treat as empty
            } else {
                if (s.charAt(i) == '(') {
                    res |= dp[i + 1][open + 1];
                } else if (open > 0) {
                    res |= dp[i + 1][open - 1];
                }
            }
            dp[i][open] = res;
        }
    }
    return dp[0][0];
}

public boolean checkValidString(String s) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = n - 1; i >= 0; i--) {
        boolean[] newDp = new boolean[n + 1];
        for (int open = 0; open < n; open++) {
            if (s.charAt(i) == '*') {
                newDp[open] = dp[open + 1] ||
                              (open > 0 && dp[open - 1]) ||
                              dp[open];
            } else if (s.charAt(i) == '(') {
                newDp[open] = dp[open + 1];
            } else if (open > 0) {
                newDp[open] = dp[open - 1];
            }
        }
        dp = newDp;
    }
    return dp[0];
}

public boolean checkValidString(String s) {
    Stack<Integer> leftStack = new Stack<>();  // indices of '('
    Stack<Integer> starStack = new Stack<>();  // indices of '*'

    // First pass: match ')' with '(' or '*'
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '(') {
            leftStack.push(i);
        } else if (ch == '*') {
            starStack.push(i);
        } else { // ')'
            if (!leftStack.isEmpty()) {
                leftStack.pop();
            } else if (!starStack.isEmpty()) {
                starStack.pop();
            } else {
                return false; // unmatched ')'
            }
        }
    }

    // Second pass: match remaining '(' with '*'
    while (!leftStack.isEmpty() && !starStack.isEmpty()) {
        // '*' must come after '(' to be valid
        if (leftStack.pop() > starStack.pop()) {
            return false;
        }
    }

    return leftStack.isEmpty();
}

# Check if i-th bit is set
if mask & (1 << i):
    pass

# Set i-th bit
new_mask = mask | (1 << i)

# Unset i-th bit
new_mask = mask & ~(1 << i)

# Iterate through all submasks
submask = mask
while submask:
    # Process submask
    submask = (submask - 1) & mask

// Check if i-th bit is set
if ((mask & (1 << i)) != 0) {
    // i-th item is included
}

// Set i-th bit
int newMask = mask | (1 << i);

// Unset i-th bit
int newMask = mask & ~(1 << i);

// Toggle i-th bit
int newMask = mask ^ (1 << i);

// Count number of set bits
int count = Integer.bitCount(mask);

// Get lowest set bit
int lowestBit = mask & (-mask);

// Iterate through all subsets
for (int mask = 0; mask < (1 << n); mask++) {
    // Process mask
}

// Iterate through all submasks of mask
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
    // Process submask
}

// Java Implementation
public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int[][] dp = new int[1 << n][n];
    Queue<int[]> queue = new LinkedList<>();

    // Initialize: start from any node
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[1 << i], Integer.MAX_VALUE);
        dp[1 << i][i] = 0;
        queue.offer(new int[]{1 << i, i});
    }

    int target = (1 << n) - 1;

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int mask = curr[0], node = curr[1];
        int dist = dp[mask][node];

        if (mask == target) {
            return dist;
        }

        for (int next : graph[node]) {
            int nextMask = mask | (1 << next);
            if (dp[nextMask][next] > dist + 1) {
                dp[nextMask][next] = dist + 1;
                queue.offer(new int[]{nextMask, next});
            }
        }
    }

    return -1;
}

// Java Implementation
public int minimumTimeRequired(int[] jobs, int k) {
    int n = jobs.length;
    int[] dp = new int[1 << n];
    int[] subsetSum = new int[1 << n];

    // Precompute sum for each subset
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subsetSum[mask] += jobs[i];
            }
        }
    }

    // dp[mask] = min time to finish jobs in mask
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        // Try all submasks
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            dp[mask] = Math.min(dp[mask],
                               Math.max(dp[mask ^ submask], subsetSum[submask]));
        }
    }

    return dp[(1 << n) - 1];
}

// Java Implementation - Subset DP
public int minStickers(String[] stickers, String target) {
    int n = target.length();
    int[] dp = new int[1 << n];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;

        for (String sticker : stickers) {
            int newMask = mask;
            int[] counts = new int[26];

            for (char c : sticker.toCharArray()) {
                counts[c - 'a']++;
            }

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    char c = target.charAt(i);
                    if (counts[c - 'a'] > 0) {
                        counts[c - 'a']--;
                        newMask |= (1 << i);
                    }
                }
            }

            if (dp[newMask] == -1 || dp[newMask] > dp[mask] + 1) {
                dp[newMask] = dp[mask] + 1;
            }
        }
    }

    return dp[(1 << n) - 1];
}

// Java Implementation
public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int num : nums) sum += num;

    if (sum % k != 0) return false;

    int target = sum / k;
    int n = nums.length;
    boolean[] dp = new boolean[1 << n];
    int[] total = new int[1 << n];
    dp[0] = true;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) continue;

            int newMask = mask | (1 << i);

            if (total[mask] % target + nums[i] <= target) {
                dp[newMask] = true;
                total[newMask] = total[mask] + nums[i];
            }
        }
    }

    return dp[(1 << n) - 1];
}

// Precompute sum for all subsets - O(2^n × n)
int[] subsetSum = new int[1 << n];
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            subsetSum[mask] += arr[i];
        }
    }
}

// For each mask, iterate through all its submasks
for (int mask = 0; mask < (1 << n); mask++) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // dp[mask] can be computed from dp[submask] and dp[mask ^ submask]
        dp[mask] = Math.min(dp[mask], dp[submask] + dp[mask ^ submask]);
    }
}

// For each mask, sum values of all its submasks
int[] dp = new int[1 << n];
// ... initialize dp ...

for (int i = 0; i < n; i++) {
    for (int mask = 0; mask < (1 << n); mask++) {
        if ((mask & (1 << i)) != 0) {
            dp[mask] += dp[mask ^ (1 << i)];
        }
    }
}

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 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
}

Count(L, R) = Count(0, R) - Count(0, L-1)

Build numbers digit-by-digit left to right:
For each position, try all valid digits (0-9 or constrained by upper bound)
Use memoization to avoid recalculating same states

# Universal Digit DP Template
def count_numbers(n):
    """
    Count numbers from 0 to n satisfying certain constraints.

    Time: O(digits × states × 10)
    Space: O(digits × states)
    """
    digits = [int(d) for d in str(n)]
    memo = {}

    def dp(pos, tight, started, state):
        """
        pos: current position (0-indexed from left)
        tight: if True, current digit is bounded by digits[pos]
        started: if True, we've placed a non-zero digit
        state: problem-specific state (sum, count, etc.)
        """
        # Base case: processed all digits
        if pos == len(digits):
            return 1 if check_valid(state) else 0

        # Check memo
        if (pos, tight, started, state) in memo:
            return memo[(pos, tight, started, state)]

        # Determine max digit we can place
        limit = digits[pos] if tight else 9

        result = 0
        for digit in range(0, limit + 1):
            # Handle leading zeros
            new_started = started or (digit > 0)

            # Update problem-specific state
            new_state = update_state(state, digit, new_started)

            # Recursively count
            result += dp(
                pos + 1,
                tight and (digit == limit),
                new_started,
                new_state
            )

        memo[(pos, tight, started, state)] = result
        return result

    return dp(0, True, False, initial_state)

def count_range(L, R):
    """Count numbers in range [L, R]."""
    return count_numbers(R) - count_numbers(L - 1)

# LC 902 - Numbers At Most N Given Digit Set
def atMostNGivenDigitSet(digits, n):
    """
    Count numbers using only digits from set, at most n.

    Time: O(log n × |D|) where D is digit set
    Space: O(log n)
    """
    str_n = str(n)
    n_digits = len(str_n)
    digit_set = set(digits)

    # Count numbers with fewer digits (always valid)
    count = sum(len(digits) ** i for i in range(1, n_digits))

    # DP for numbers with exactly n_digits digits
    @lru_cache(None)
    def dp(pos, tight):
        # Base case: formed complete number
        if pos == n_digits:
            return 1

        # Determine max digit
        limit = int(str_n[pos]) if tight else 9

        result = 0
        for d in digits:
            digit_val = int(d)
            if digit_val > limit:
                break  # Can't use this digit

            # Continue building
            result += dp(pos + 1, tight and (digit_val == limit))

        return result

    return count + dp(0, True)

// Java - LC 902
/**
 * time = O(log N × |D|)
 * space = O(log N)
 */
class Solution {
    private String strN;
    private String[] digits;
    private Map<String, Integer> memo;

    public int atMostNGivenDigitSet(String[] digits, int n) {
        this.strN = String.valueOf(n);
        this.digits = digits;
        this.memo = new HashMap<>();

        int nDigits = strN.length();
        int count = 0;

        // Count numbers with fewer digits
        int base = digits.length;
        for (int i = 1; i < nDigits; i++) {
            count += Math.pow(base, i);
        }

        // Add numbers with exactly nDigits digits
        count += dp(0, true);

        return count;
    }

    private int dp(int pos, boolean tight) {
        if (pos == strN.length()) {
            return 1;
        }

        String key = pos + "," + tight;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int limit = tight ? strN.charAt(pos) - '0' : 9;
        int result = 0;

        for (String d : digits) {
            int digit = Integer.parseInt(d);
            if (digit > limit) break;

            result += dp(pos + 1, tight && (digit == limit));
        }

        memo.put(key, result);
        return result;
    }
}

# Count numbers with digit sum = K
def count_digit_sum_k(n, k):
    """
    Count numbers from 1 to n where digit sum = k.

    State: (pos, tight, sum)
    """
    digits = [int(d) for d in str(n)]
    memo = {}

    def dp(pos, tight, current_sum):
        # Base case
        if pos == len(digits):
            return 1 if current_sum == k else 0

        # Memo check
        if (pos, tight, current_sum) in memo:
            return memo[(pos, tight, current_sum)]

        # Determine limit
        limit = digits[pos] if tight else 9

        result = 0
        for digit in range(0, limit + 1):
            # Pruning: skip if sum will exceed k
            if current_sum + digit > k:
                break

            result += dp(
                pos + 1,
                tight and (digit == limit),
                current_sum + digit
            )

        memo[(pos, tight, current_sum)] = result
        return result

    # Subtract 1 to exclude 0
    return dp(0, True, 0) - 1

# Example: count_digit_sum_k(100, 5)
# Numbers: 5, 14, 23, 32, 41, 50 → 6 numbers

# LC 233 - Number of Digit One
def countDigitOne(n):
    """
    Count occurrences of digit 1 in range [1, n].

    State: (pos, tight, count_of_ones)
    """
    digits = [int(d) for d in str(n)]
    memo = {}

    def dp(pos, tight, started, count_ones):
        if pos == len(digits):
            return count_ones

        if (pos, tight, started, count_ones) in memo:
            return memo[(pos, tight, started, count_ones)]

        limit = digits[pos] if tight else 9
        result = 0

        for digit in range(0, limit + 1):
            new_started = started or (digit > 0)

            # Count this digit if it's 1 and we've started
            new_count = count_ones + (1 if digit == 1 and new_started else 0)

            result += dp(
                pos + 1,
                tight and (digit == limit),
                new_started,
                new_count
            )

        memo[(pos, tight, started, count_ones)] = result
        return result

    return dp(0, True, False, 0)

// Java - LC 233
/**
 * time = O(log N × log N)
 * space = O(log N × log N)
 */
class Solution {
    private int[] digits;
    private Map<String, Integer> memo;

    public int countDigitOne(int n) {
        String strN = String.valueOf(n);
        digits = new int[strN.length()];
        for (int i = 0; i < strN.length(); i++) {
            digits[i] = strN.charAt(i) - '0';
        }

        memo = new HashMap<>();
        return dp(0, true, false, 0);
    }

    private int dp(int pos, boolean tight, boolean started, int countOnes) {
        if (pos == digits.length) {
            return countOnes;
        }

        String key = pos + "," + tight + "," + started + "," + countOnes;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int limit = tight ? digits[pos] : 9;
        int result = 0;

        for (int digit = 0; digit <= limit; digit++) {
            boolean newStarted = started || (digit > 0);
            int newCount = countOnes + ((digit == 1 && newStarted) ? 1 : 0);

            result += dp(
                pos + 1,
                tight && (digit == limit),
                newStarted,
                newCount
            );
        }

        memo.put(key, result);
        return result;
    }
}

# Count numbers without consecutive same digits
def count_no_consecutive(n):
    """
    Count numbers from 1 to n with no two adjacent identical digits.

    State: (pos, tight, prev_digit)
    """
    digits = [int(d) for d in str(n)]
    memo = {}

    def dp(pos, tight, prev_digit):
        if pos == len(digits):
            return 1

        if (pos, tight, prev_digit) in memo:
            return memo[(pos, tight, prev_digit)]

        limit = digits[pos] if tight else 9
        result = 0

        for digit in range(0, limit + 1):
            # Skip if same as previous digit
            if digit == prev_digit:
                continue

            result += dp(
                pos + 1,
                tight and (digit == limit),
                digit
            )

        memo[(pos, tight, prev_digit)] = result
        return result

    return dp(0, True, -1) - 1  # -1 to exclude 0

# Example: count_no_consecutive(100)
# Valid: 10, 12, 13, 14, ..., 21, 23, 24, ... (exclude 11, 22, ...)

Problem: Count numbers ≤ 523 with digit sum = 10

Digits of 523: [5, 2, 3]

Decision Tree (simplified):

Position 0: Can use 0-5
├─ Use 0: sum=0, tight=False → dp(1, False, 0)
│  ├─ Next positions have limit=9
│  └─ Count all with sum=10
│
├─ Use 1: sum=1, tight=False → dp(1, False, 1)
│  └─ Count numbers 1XX with digit sum = 10
│
├─ Use 2: sum=2, tight=False → dp(1, False, 2)
│  └─ Count numbers 2XX with digit sum = 10
│
├─ Use 3: sum=3, tight=False → dp(1, False, 3)
│  └─ Count numbers 3XX with digit sum = 10
│
├─ Use 4: sum=4, tight=False → dp(1, False, 4)
│  └─ Count numbers 4XX with digit sum = 10
│
└─ Use 5: sum=5, tight=True → dp(1, True, 5)
   ├─ Position 1: Can use 0-2 (tight bound)
   │  ├─ Use 0: sum=5, tight=False
   │  ├─ Use 1: sum=6, tight=False
   │  └─ Use 2: sum=7, tight=True
   │     └─ Position 2: Can use 0-3 (tight)
   │        ├─ Use 3: sum=10 ✓ (523 included!)
   │        └─ ...

Valid numbers: 109, 118, 127, ..., 505, 514, 523

"Count numbers in range with..."
"How many numbers from L to R satisfy..."
"Numbers where digits..."
→ Think Digit DP

Keywords: "digit sum", "consecutive digits", "distinct digits",
         "digit constraints", "count numbers"