2-D Dynamic Programming

def unique_paths(m: int, n: int) -> int:
    """LC 62. Unique Paths.

    Count right/down paths to each cell: ways here = ways_above +
    ways_left. The first row and column are all ones (only one straight
    path reaches them). One rolling row of length n is enough: before
    the update, ways[c] still holds the row above, and ways[c - 1] is
    already this row. O(m*n) time, O(n) space.
    """
    ways = [1] * n  # top row: one path each, straight from the left
    for _ in range(1, m):
        for c in range(1, n):
            ways_above = ways[c]  # not yet overwritten: previous row
            ways_left = ways[c - 1]  # already overwritten: current row
            ways[c] = ways_above + ways_left
    return ways[-1]

// LC 62. Each cell's path count is the sum of the counts above and to the
// left, with the first row and column all ones. Sweep row by row reusing one
// rolling array of length n: dp[j] already holds the count from above, so
// dp[j] += dp[j-1] folds in the left neighbor. O(mn) time, O(n) space.
// (Closed form: choose(m+n-2, m-1).)
int uniquePaths(int m, int n) {
    vector<long long> dp(n, 1);  // first row: one path to every cell
    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j) dp[j] += dp[j - 1];  // above + left
    return static_cast<int>(dp[n - 1]);
}

/// LC 62. Paths into a cell = paths from above + paths from the left. One
/// rolling row of length n replaces the 2-D table: row[j] already holds the
/// value from above, so adding row[j - 1] in place completes the recurrence.
/// The all-ones initial row is the first-row base case.
pub fn unique_paths(m: i32, n: i32) -> i32 {
    let n = n as usize;
    let mut row = vec![1; n];
    for _ in 1..m {
        for j in 1..n {
            row[j] += row[j - 1];
        }
    }
    row[n - 1]
}

/** LC 62. Each cell is paths-from-above + paths-from-left; one rolling row of length n, seeded with the all-ones top row. */
export function uniquePaths(m: number, n: number): number {
  const dp: number[] = new Array(n).fill(1); // top row: a single straight path reaches each cell
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] += dp[c - 1]; // old dp[c] is "above", dp[c-1] is "left"; column 0 stays 1
    }
  }
  return dp[n - 1];
}

// LC 62. Each cell's path count is above + left, with the first row and
// column all ones; one rolling row, since dp[j] still holds the row above.
func uniquePaths(m, n int) int {
	dp := make([]int, n)
	for j := range dp {
		dp[j] = 1 // first row: one path to every cell
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[j] += dp[j-1] // above (old dp[j]) + left
		}
	}
	return dp[n-1]
}

// LC 62. Each cell's path count is above + left, first row and column all
// ones; one rolling row of length n carries the whole table.
func uniquePaths(_ m: Int, _ n: Int) -> Int {
    var dp = [Int](repeating: 1, count: n)  // first row: one path to every cell
    for _ in stride(from: 1, to: m, by: 1) {
        for j in 1..<n {
            dp[j] += dp[j - 1]  // above (old dp[j]) + left
        }
    }
    return dp[n - 1]
}

def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    """LC 63. Unique Paths II.

    Same above-plus-left counting as Unique Paths, but a cell holding an
    obstacle is forced to ZERO paths -- that single rule also handles
    the traps: an obstacle on the start zeroes everything, and an
    obstacle in the first row or column cuts off every cell beyond it
    because the zeros propagate. O(m*n) time, O(n) space.
    """
    cols = len(obstacle_grid[0])
    ways = [0] * cols
    ways[0] = 1 - obstacle_grid[0][0]  # blocked start: zero paths anywhere
    for row in obstacle_grid:
        for c in range(cols):
            if row[c] == 1:
                ways[c] = 0  # no path may stand on an obstacle
            elif c > 0:
                ways[c] += ways[c - 1]  # above (old ways[c]) + left
    return ways[-1]

// LC 63. Same right-or-down counting as Unique Paths, but an obstacle cell is
// forced to zero paths, which automatically cuts off everything past an
// obstacle in the first row or column. The rolling row starts from whether the
// start cell itself is free; a blocked start makes the whole answer zero.
int uniquePathsWithObstacles(vector<vector<int>> obstacleGrid) {
    int m = static_cast<int>(obstacleGrid.size());
    int n = static_cast<int>(obstacleGrid[0].size());
    vector<long long> dp(n, 0);
    dp[0] = (obstacleGrid[0][0] == 0) ? 1 : 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1)
                dp[j] = 0;  // obstacle: no path ends here
            else if (j > 0)
                dp[j] += dp[j - 1];  // above (old dp[j]) + left
        }
    return static_cast<int>(dp[n - 1]);
}

/// LC 63. Same rolling-row sum as LC 62, but an obstacle cell is forced to
/// zero paths. Seeding row[0] = 1 and zeroing it on the first sweep handles a
/// blocked start; a blocked first-row or first-column cell zeroes everything
/// past it because nothing ever adds back in.
pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
    let n = obstacle_grid[0].len();
    let mut row = vec![0i32; n];
    row[0] = 1;
    for grid_row in &obstacle_grid {
        for j in 0..n {
            if grid_row[j] == 1 {
                row[j] = 0;
            } else if j > 0 {
                row[j] += row[j - 1];
            }
        }
    }
    row[n - 1]
}

/** LC 63. Same rolling-row sum, but an obstacle forces its cell to ZERO paths; a blocked start zeroes everything. */
export function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const cols = obstacleGrid[0].length;
  const dp: number[] = new Array(cols).fill(0);
  dp[0] = obstacleGrid[0][0] === 1 ? 0 : 1; // obstacle on the start kills every path
  for (const row of obstacleGrid) {
    for (let c = 0; c < cols; c++) {
      if (row[c] === 1) dp[c] = 0; // no path may end on an obstacle
      else if (c > 0) dp[c] += dp[c - 1]; // above (old value) plus left; col 0 only inherits from above
    }
  }
  return dp[cols - 1];
}

// LC 63. Same above-plus-left counting, but an obstacle cell is forced to
// ZERO paths -- that single rule also cuts off everything past it.
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n := len(obstacleGrid[0])
	dp := make([]int, n)
	if obstacleGrid[0][0] == 0 {
		dp[0] = 1 // a blocked start zeroes everything
	}
	for _, row := range obstacleGrid {
		for j := 0; j < n; j++ {
			if row[j] == 1 {
				dp[j] = 0 // no path may stand on an obstacle
			} else if j > 0 {
				dp[j] += dp[j-1] // above (old dp[j]) + left
			}
		}
	}
	return dp[n-1]
}

// LC 63. Same above-plus-left counting, but an obstacle cell is forced to
// ZERO paths -- the zeros propagate and cut off everything past an obstacle.
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
    let n = obstacleGrid[0].count
    var dp = [Int](repeating: 0, count: n)
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0  // blocked start: zero paths anywhere
    for row in obstacleGrid {
        for j in 0..<n {
            if row[j] == 1 {
                dp[j] = 0  // no path may stand on an obstacle
            } else if j > 0 {
                dp[j] += dp[j - 1]  // above (old dp[j]) + left
            }
        }
    }
    return dp[n - 1]
}

def min_path_sum(grid: list[list[int]]) -> int:
    """LC 64. Minimum Path Sum.

    Cheapest right/down path: each cell costs its own value plus the
    cheaper of the cell above and the cell to the left; the first row
    and column are plain prefix sums. A rolling row seeded with inf
    (and 0 in slot 0 so the start cell pays only itself) makes both
    bases fall out of the same recurrence. The answer is the bottom
    right entry. O(m*n) time, O(n) space.
    """
    cols = len(grid[0])
    best = [float("inf")] * cols
    best[0] = 0  # so the start cell becomes 0 + grid[0][0]
    for row in grid:
        best[0] += row[0]  # first column: reachable only from above
        for c in range(1, cols):
            best[c] = row[c] + min(best[c], best[c - 1])  # above vs left
    return best[-1]

// LC 64. dp cell = its grid value plus the cheaper of the entries above and to
// the left, with the first row and column seeded as prefix sums (only one way
// in). A rolling row keeps O(n) extra space -- dp[j] is "above", dp[j-1] is
// "left" -- and the answer lands in the last cell after the final row.
int minPathSum(vector<vector<int>> grid) {
    int m = static_cast<int>(grid.size());
    int n = static_cast<int>(grid[0].size());
    vector<int> dp(n, 0);
    dp[0] = grid[0][0];
    for (int j = 1; j < n; ++j) dp[j] = dp[j - 1] + grid[0][j];  // first row prefix sums
    for (int i = 1; i < m; ++i) {
        dp[0] += grid[i][0];  // first column: only from above
        for (int j = 1; j < n; ++j) dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
    }
    return dp[n - 1];
}

/// LC 64. dp cell = its grid value + min(above, left), rolled into one row.
/// Seeding row[0] = 0 and the rest to i32::MAX makes the first sweep produce
/// the first-row prefix sums without a special case: the MAX always loses the
/// min to the left neighbor.
pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid[0].len();
    let mut row = vec![i32::MAX; n];
    row[0] = 0;
    for grid_row in &grid {
        row[0] += grid_row[0];
        for j in 1..n {
            row[j] = grid_row[j] + row[j].min(row[j - 1]);
        }
    }
    row[n - 1]
}

/** LC 64. dp[c] = cell + min(above, left) over a rolling row; Infinity seeds make the first row take only "left". */
export function minPathSum(grid: number[][]): number {
  const cols = grid[0].length;
  const dp: number[] = new Array(cols).fill(Infinity); // "above" the top row costs Infinity
  dp[0] = 0; // so the start cell becomes grid[0][0] + 0
  for (const row of grid) {
    dp[0] += row[0]; // left edge: the only way in is straight down
    for (let c = 1; c < cols; c++) {
      dp[c] = row[c] + Math.min(dp[c], dp[c - 1]); // old dp[c] is above, dp[c-1] is left
    }
  }
  return dp[cols - 1];
}

// LC 64. Cell = its value + min(above, left), first row and column seeded as
// prefix sums; one rolling row where dp[j] is "above" and dp[j-1] is "left".
func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([]int, n)
	dp[0] = grid[0][0]
	for j := 1; j < n; j++ {
		dp[j] = dp[j-1] + grid[0][j] // first row: prefix sums
	}
	for i := 1; i < m; i++ {
		dp[0] += grid[i][0] // first column: only from above
		for j := 1; j < n; j++ {
			cheaper := dp[j] // above
			if dp[j-1] < cheaper {
				cheaper = dp[j-1] // left
			}
			dp[j] = grid[i][j] + cheaper
		}
	}
	return dp[n-1]
}

// LC 64. Each cell costs its own value plus the cheaper of above and left;
// the first row and column are plain prefix sums, one rolling row suffices.
func minPathSum(_ grid: [[Int]]) -> Int {
    let n = grid[0].count
    var dp = [Int](repeating: 0, count: n)
    dp[0] = grid[0][0]
    for j in 1..<n { dp[j] = dp[j - 1] + grid[0][j] }  // first row prefix sums
    for i in stride(from: 1, to: grid.count, by: 1) {
        dp[0] += grid[i][0]  // first column: reachable only from above
        for j in 1..<n {
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1])  // above vs left
        }
    }
    return dp[n - 1]
}

def longest_common_subsequence(text1: str, text2: str) -> int:
    """LC 1143. Longest Common Subsequence.

    dp[i][j] = length of the longest common subsequence of the first i
    characters of text1 and the first j characters of text2. When the
    two next characters match they extend the DIAGONAL value by one;
    otherwise the cell takes the max of dropping a character from
    either string (the cell above or to the left). Two rolling rows cut
    space to O(min(m, n)). O(m*n) time.
    """
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # roll over the shorter string
    prev = [0] * (len(text2) + 1)  # dp row for the empty text1 prefix
    for ch1 in text1:
        curr = [0]  # dp[i][0]: empty text2 prefix shares nothing
        for j, ch2 in enumerate(text2):
            if ch1 == ch2:
                curr.append(prev[j] + 1)  # match: extend the diagonal
            else:
                curr.append(max(prev[j + 1], curr[j]))  # drop from either
        prev = curr
    return prev[-1]

// LC 1143. Table over prefix pairs: matching characters extend the diagonal
// value by one, otherwise the cell takes the max of dropping a character from
// either string. That diagonal-on-match versus max-of-neighbors split is the
// whole recurrence; two rolling rows cut the space to O(n).
int longestCommonSubsequence(string text1, string text2) {
    int m = static_cast<int>(text1.size()), n = static_cast<int>(text2.size());
    vector<int> prev(n + 1, 0), cur(n + 1, 0);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j)
            cur[j] = (text1[i - 1] == text2[j - 1]) ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    return prev[n];
}

/// LC 1143. Table over prefix pairs: matching characters extend the DIAGONAL
/// by one, otherwise take the max of dropping a character from either string.
/// The diagonal-on-match versus max-of-neighbors split is the whole
/// recurrence; two rolling rows cut space to O(n).
pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
    let (a, b) = (text1.as_bytes(), text2.as_bytes());
    let mut prev = vec![0i32; b.len() + 1];
    let mut cur = vec![0i32; b.len() + 1];
    for &ca in a {
        for (j, &cb) in b.iter().enumerate() {
            cur[j + 1] = if ca == cb {
                prev[j] + 1
            } else {
                prev[j + 1].max(cur[j])
            };
        }
        std::mem::swap(&mut prev, &mut cur);
    }
    prev[b.len()]
}

/** LC 1143. Prefix-pair table: match extends the DIAGONAL by one, else max of dropping a char from either string; two rolling rows over the shorter string. */
export function longestCommonSubsequence(text1: string, text2: string): number {
  if (text1.length < text2.length) [text1, text2] = [text2, text1]; // roll over the shorter: O(min(m, n)) space
  const n = text2.length;
  let prev: number[] = new Array(n + 1).fill(0); // row i-1
  let curr: number[] = new Array(n + 1).fill(0); // row i
  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= n; j++) {
      curr[j] =
        text1[i - 1] === text2[j - 1]
          ? prev[j - 1] + 1 // diagonal on match
          : Math.max(prev[j], curr[j - 1]); // skip a char of text1 or of text2
    }
    [prev, curr] = [curr, prev]; // stale contents are fully overwritten next pass
  }
  return prev[n];
}

// LC 1143. Matching characters extend the DIAGONAL by one; otherwise take the
// max of dropping a character from either string. Two rolling rows.
func longestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	prev, cur := make([]int, n+1), make([]int, n+1)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				cur[j] = prev[j-1] + 1 // match: extend the diagonal
			} else if prev[j] > cur[j-1] {
				cur[j] = prev[j] // drop from text2
			} else {
				cur[j] = cur[j-1] // drop from text1
			}
		}
		prev, cur = cur, prev
	}
	return prev[n]
}

// LC 1143. Matching characters extend the DIAGONAL by one; otherwise take
// the max of dropping a character from either string. Two rolling rows.
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
    let a = Array(text1), b = Array(text2)
    var prev = [Int](repeating: 0, count: b.count + 1)
    var cur = prev
    for i in stride(from: 1, through: a.count, by: 1) {
        for j in stride(from: 1, through: b.count, by: 1) {
            cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] + 1 : max(prev[j], cur[j - 1])
        }
        swap(&prev, &cur)
    }
    return prev[b.count]
}

def last_stone_weight_ii(stones: list[int]) -> int:
    """LC 1049. Last Stone Weight II.

    THE REFRAME: every smash sequence effectively assigns a + or - sign
    to each stone, and the final weight is the absolute difference of
    the two sign groups -- total - 2 * (sum of the minus group). So the
    game is really: find a subset sum as close to total // 2 as
    possible (without exceeding it), exactly Partition Equal Subset Sum
    with a "closest" finish instead of an exact one. Sums iterate
    downward so each stone is used at most once.
    O(n * total/2) time, O(total) space.
    """
    total = sum(stones)
    half = total // 2
    reachable = [False] * (half + 1)
    reachable[0] = True  # the empty subset sums to zero
    for stone in stones:
        for s in range(half, stone - 1, -1):  # downward: stone used once
            if reachable[s - stone]:
                reachable[s] = True
    closest = max(s for s in range(half + 1) if reachable[s])
    return total - 2 * closest  # one group gets closest, the rest fights it

// LC 1049. Any smash sequence effectively assigns + or - signs to the stones,
// so the final weight is |sum of one group - sum of the other| and the goal is
// a subset sum as close to total/2 as possible. Subset-sum dp over reachable
// sums up to half the total (downward sweep so each stone is used once), then
// answer total - 2 * best. Seeing through the game disguise is the hard part.
int lastStoneWeightII(vector<int> stones) {
    int total = 0;
    for (int s : stones) total += s;
    int half = total / 2;
    vector<bool> reachable(half + 1, false);
    reachable[0] = true;
    for (int stone : stones)
        for (int s = half; s >= stone; --s)  // downward: each stone used once
            if (reachable[s - stone]) reachable[s] = true;
    int best = 0;
    for (int s = half; s >= 0; --s)
        if (reachable[s]) {
            best = s;
            break;
        }
    return total - 2 * best;
}

/// LC 1049. The smash game is a disguise: any sequence of smashes assigns +/-
/// signs to the stones, so minimize |total - 2 * subset|. Subset-sum dp over
/// sums up to total / 2 (downward sweep so each stone is used once), then the
/// answer is total minus twice the largest reachable sum.
pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
    let total: i32 = stones.iter().sum();
    let half = (total / 2) as usize;
    let mut dp = vec![false; half + 1];
    dp[0] = true;
    for &x in &stones {
        for s in (x as usize..=half).rev() {
            if dp[s - x as usize] {
                dp[s] = true;
            }
        }
    }
    let best = (0..=half).rev().find(|&s| dp[s]).unwrap() as i32;
    total - 2 * best
}

/** LC 1049. Smashing assigns +/- signs, so find a subset sum closest to total/2; downward subset-sum dp, answer total - 2*best. */
export function lastStoneWeightII(stones: number[]): number {
  const total = stones.reduce((a, b) => a + b, 0);
  const half = Math.floor(total / 2);
  const reachable: boolean[] = new Array(half + 1).fill(false);
  reachable[0] = true;
  for (const stone of stones) {
    for (let sum = half; sum >= stone; sum--) {
      // downward: reachable[sum - stone] still excludes this stone
      if (reachable[sum - stone]) reachable[sum] = true;
    }
  }
  for (let sum = half; sum >= 0; sum--) {
    if (reachable[sum]) return total - 2 * sum; // the minus-group sums to `sum`, the plus-group to total - sum
  }
  return total; // never reached: sum 0 is always reachable
}

// LC 1049. Smashes assign + or - signs to the stones, so answer total - 2 *
// (largest reachable subset sum <= total/2): subset-sum dp, swept downward.
func lastStoneWeightII(stones []int) int {
	total := 0
	for _, s := range stones {
		total += s
	}
	half := total / 2
	reachable := make([]bool, half+1)
	reachable[0] = true
	for _, stone := range stones {
		for s := half; s >= stone; s-- { // downward: each stone used once
			if reachable[s-stone] {
				reachable[s] = true
			}
		}
	}
	closest := 0
	for s := half; s >= 0; s-- {
		if reachable[s] {
			closest = s
			break
		}
	}
	return total - 2*closest // one group gets closest, the rest fights it
}

// LC 1049. Smashes assign + or - signs to the stones, so the answer is
// total - 2 * (best subset sum <= total/2) -- subset-sum dp, swept downward.
func lastStoneWeightII(_ stones: [Int]) -> Int {
    let total = stones.reduce(0, +)
    let half = total / 2
    var reachable = [Bool](repeating: false, count: half + 1)
    reachable[0] = true
    for stone in stones {
        for s in stride(from: half, through: stone, by: -1) where reachable[s - stone] {
            reachable[s] = true
        }
    }
    var best = 0
    for s in stride(from: half, through: 0, by: -1) where reachable[s] {
        best = s
        break
    }
    return total - 2 * best  // one group gets best, the rest fights it
}

def max_profit_with_cooldown(prices: list[int]) -> int:
    """LC 309. Best Time to Buy and Sell Stock with Cooldown.

    Three states per day -- holding a share, sold today, resting with
    cash -- and the transitions ARE the solution:

        holding <- max(holding, resting - price)   keep, or buy after rest
        sold    <- holding + price                 sell what was held
        resting <- max(resting, sold)              idle, or cooldown clears

    Selling routes through `sold` for exactly one day before the cash
    becomes spendable in `resting` -- that one-day detour is the
    cooldown. Start holding at -inf (impossible before any buy) and
    end on a no-share state. O(n) time, O(1) space.
    """
    holding, sold, resting = float("-inf"), 0, 0
    for price in prices:
        holding, sold, resting = (
            max(holding, resting - price),  # keep the share, or buy out of rest
            holding + price,  # sell today: tomorrow is forced cooldown
            max(resting, sold),  # idle, or yesterday's sale finally clears
        )
    return max(sold, resting)  # never end still holding a share

// LC 309. Three states per day: holding a share, just sold (cooldown), and
// resting with cash. Transitions: hold from holding or buying after a rest,
// sold from holding plus today's price, rest from resting or yesterday's sold.
// Drawing the small state machine first prevents transition mistakes; rolling
// variables give O(1) space, and the answer never ends while holding.
int maxProfitWithCooldown(vector<int> prices) {
    int hold = -prices[0], sold = 0, rest = 0;
    for (int i = 1; i < static_cast<int>(prices.size()); ++i) {
        int price = prices[i];
        int newHold = max(hold, rest - price);  // keep holding, or buy after rest
        int newSold = hold + price;             // sell today, cooldown tomorrow
        int newRest = max(rest, sold);          // stay flat, or cooldown ends
        hold = newHold;
        sold = newSold;
        rest = newRest;
    }
    return max(sold, rest);  // never end holding a share
}

/// LC 309. Three-state machine per day: HOLD a share, just SOLD (cooldown),
/// or RESTING with cash. Transitions: sold = hold + price; hold = max(hold,
/// rest - price); rest = max(rest, previous sold). The i32::MIN / 2 sentinel
/// marks "holding before any buy" without overflowing when price is added.
pub fn max_profit_with_cooldown(prices: Vec<i32>) -> i32 {
    let (mut hold, mut sold, mut rest) = (i32::MIN / 2, 0, 0);
    for &price in &prices {
        let prev_sold = sold;
        sold = hold + price;
        hold = hold.max(rest - price);
        rest = rest.max(prev_sold);
    }
    sold.max(rest)
}

/** LC 309. Three-state machine per day (hold / just sold / resting); selling routes through a forced rest day. O(1) space. */
export function maxProfitWithCooldown(prices: number[]): number {
  let hold = -Infinity; // best cash while holding a share
  let sold = -Infinity; // best cash having sold TODAY (tomorrow is cooldown)
  let rest = 0; // best cash, free to buy
  for (const price of prices) {
    const prevSold = sold;
    sold = hold + price; // sell what we held yesterday
    hold = Math.max(hold, rest - price); // keep holding, or buy out of a rested state
    rest = Math.max(rest, prevSold); // stay idle, or yesterday's sale finishes its cooldown
  }
  return Math.max(rest, sold); // never end holding a share
}

// LC 309. Holding/sold/resting state machine: a sale parks in sold for one
// day before the cash clears into resting -- that detour IS the cooldown.
func maxProfitWithCooldown(prices []int) int {
	hold, sold, rest := -prices[0], 0, 0
	for _, price := range prices[1:] {
		newHold := hold // keep holding...
		if rest-price > newHold {
			newHold = rest - price // ...or buy after a rest
		}
		newSold := hold + price // sell today, cooldown tomorrow
		newRest := rest         // stay flat...
		if sold > newRest {
			newRest = sold // ...or the cooldown finally clears
		}
		hold, sold, rest = newHold, newSold, newRest
	}
	if sold > rest {
		return sold // never end still holding a share
	}
	return rest
}

// LC 309. Three states per day -- holding, just sold (cooldown), resting --
// and the transitions ARE the solution; never end the run still holding.
func maxProfitWithCooldown(_ prices: [Int]) -> Int {
    var hold = -prices[0], sold = 0, rest = 0
    for price in prices.dropFirst() {
        (hold, sold, rest) = (
            max(hold, rest - price),  // keep holding, or buy after rest
            hold + price,             // sell today, cooldown tomorrow
            max(rest, sold)           // stay flat, or cooldown ends
        )
    }
    return max(sold, rest)  // never end holding a share
}

def change(amount: int, coins: list[int]) -> int:
    """LC 518. Coin Change II.

    Count COMBINATIONS making the amount: combos[a] += combos[a - coin],
    seeded with combos[0] = 1. WHY coins sit in the OUTER loop: each
    coin is folded in completely before the next, so every combination
    is built in one fixed denomination order and counted once. LC 377
    (Combination Sum IV) flips the loops -- amount outer lets every coin
    be the LAST pick at every total, which counts orderings instead.
    Same recurrence, opposite loop nesting, different question.
    O(amount * len(coins)) time, O(amount) space.
    """
    combos = [0] * (amount + 1)
    combos[0] = 1  # the empty combination is the one way to make 0
    for coin in coins:  # coins OUTER: combinations, not permutations
        for a in range(coin, amount + 1):
            combos[a] += combos[a - coin]
    return combos[amount]

// LC 518. 1-D dp over amounts seeded dp[0] = 1, with the COINS in the outer
// loop and ascending amounts inside, adding dp[a - coin] to dp[a]. The
// coin-outer order collapses different orderings into one combination;
// flipping the loops, as in Combination Sum IV, would count permutations.
// unsigned cells make any intermediate wraparound defined behavior.
int change(int amount, vector<int> coins) {
    vector<unsigned> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins)  // coins OUTER: combinations, not permutations
        for (int a = coin; a <= amount; ++a) dp[a] += dp[a - coin];
    return static_cast<int>(dp[amount]);
}

/// LC 518. Unbounded knapsack counting COMBINATIONS: dp[a] += dp[a - coin]
/// with the coins in the OUTER loop and ascending amounts inside. Coin-outer
/// order is the entire point -- it fixes the order coins are considered, so
/// different orderings collapse into one combination; flipping the loops
/// (Combination Sum IV) would count permutations.
pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
    let amount = amount as usize;
    let mut dp = vec![0i32; amount + 1];
    dp[0] = 1;
    for &coin in &coins {
        for a in coin as usize..=amount {
            dp[a] += dp[a - coin as usize];
        }
    }
    dp[amount]
}

/** LC 518. Coins in the OUTER loop fix one build order per combination, counting combinations; flipped loops would count permutations. */
export function change(amount: number, coins: number[]): number {
  const dp: number[] = new Array(amount + 1).fill(0);
  dp[0] = 1; // one empty combination
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin]; // append this coin to every combination of a - coin
    }
  }
  return dp[amount];
}

// LC 518. Coins in the OUTER loop fold each coin in completely, building every
// combination in one fixed order; flipping the loops (LC 377) counts orderings.
func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1                    // the empty combination makes 0
	for _, coin := range coins { // coins OUTER: combinations, not permutations
		for a := coin; a <= amount; a++ {
			dp[a] += dp[a-coin]
		}
	}
	return dp[amount]
}

// LC 518. dp[a] += dp[a - coin] with the COINS in the outer loop: each coin
// folds in completely, so combinations are counted, not permutations.
func change(_ amount: Int, _ coins: [Int]) -> Int {
    var dp = [Int](repeating: 0, count: amount + 1)
    dp[0] = 1  // the empty combination is the one way to make 0
    for coin in coins {  // coins OUTER: combinations, not permutations
        for a in stride(from: coin, through: amount, by: 1) {
            dp[a] += dp[a - coin]
        }
    }
    return dp[amount]
}

def find_target_sum_ways(nums: list[int], target: int) -> int:
    """LC 494. Target Sum.

    THE DERIVATION: let P be the sum of the numbers given '+' and N the
    sum given '-'. Then P - N = target and P + N = total; adding the
    two equations gives 2P = total + target, so P = (total + target)/2.
    The problem collapses to counting subsets that sum to P -- a 1-D
    counting dp swept downward so each number joins at most once.
    THE GUARD: if total + target is odd no integer P exists, and if it
    is negative P would be below zero; both mean zero ways.
    O(n * P) time, O(P) space.
    """
    total = sum(nums)
    p, leftover = divmod(total + target, 2)
    if leftover or p < 0:
        return 0  # parity/negative guard: no '+' group can sum to P
    ways = [0] * (p + 1)
    ways[0] = 1  # the empty subset is the one way to reach 0
    for num in nums:
        for s in range(p, num - 1, -1):  # downward: num used at most once
            ways[s] += ways[s - num]
    return ways[p]

// LC 494. Let P be the sum of the positive group; algebra gives
// P = (total + target) / 2, so the problem becomes counting subsets that sum
// to P with a 1-D counting dp iterated downward. The transformation is the
// trick; if total + target is odd or negative, no assignment works and the
// answer is zero (the parity guard).
int findTargetSumWays(vector<int> nums, int target) {
    int total = 0;
    for (int num : nums) total += num;
    if ((total + target) % 2 != 0 || total + target < 0) return 0;  // parity guard
    int p = (total + target) / 2;
    vector<int> dp(p + 1, 0);
    dp[0] = 1;
    for (int num : nums)
        for (int s = p; s >= num; --s) dp[s] += dp[s - num];  // downward: 0/1 per number
    return dp[p];
}

/// LC 494. Algebra removes the signs: if P is the positive group, P =
/// (total + target) / 2, so count subsets summing to P with a downward 1-D
/// counting sweep. The parity guard is essential -- an odd or negative
/// total + target means no assignment exists, return 0. Zeros fall out
/// naturally: dp[s] += dp[s] doubles the ways, since 0 takes either sign.
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
    let total: i32 = nums.iter().sum();
    let shifted = total + target;
    if shifted < 0 || shifted % 2 != 0 {
        return 0;
    }
    let p = (shifted / 2) as usize;
    let mut dp = vec![0i32; p + 1];
    dp[0] = 1;
    for &x in &nums {
        for s in (x as usize..=p).rev() {
            dp[s] += dp[s - x as usize];
        }
    }
    dp[p]
}

/** LC 494. Plus-group P satisfies P = (total + target) / 2, so COUNT subsets summing to P; odd or negative total+target is an instant zero. */
export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  const shifted = total + target; // = 2 * (sum of the plus group)
  if (shifted < 0 || shifted % 2 !== 0) return 0; // parity / range guard: no valid split exists
  const positive = shifted / 2;
  const dp: number[] = new Array(positive + 1).fill(0); // dp[s] = subsets summing to s
  dp[0] = 1;
  for (const num of nums) {
    for (let s = positive; s >= num; s--) {
      dp[s] += dp[s - num]; // downward keeps each number single-use (zeros double, correctly: +0 and -0)
    }
  }
  return dp[positive];
}

// LC 494. P - N = target and P + N = total give P = (total+target)/2, so count
// subsets summing to P; an odd or negative total+target means zero ways.
func findTargetSumWays(nums []int, target int) int {
	total := 0
	for _, num := range nums {
		total += num
	}
	if (total+target)%2 != 0 || total+target < 0 {
		return 0 // parity/negative guard: no '+' group can sum to P
	}
	p := (total + target) / 2
	dp := make([]int, p+1)
	dp[0] = 1
	for _, num := range nums {
		for s := p; s >= num; s-- { // downward: each number used at most once
			dp[s] += dp[s-num]
		}
	}
	return dp[p]
}

// LC 494. Algebra: the '+' group must sum to P = (total + target) / 2, so
// count subsets reaching P; odd or negative total+target means zero ways.
func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
    let total = nums.reduce(0, +)
    if (total + target) % 2 != 0 || total + target < 0 { return 0 }  // parity guard
    let p = (total + target) / 2
    var dp = [Int](repeating: 0, count: p + 1)
    dp[0] = 1  // the empty subset is the one way to reach 0
    for num in nums {
        for s in stride(from: p, through: num, by: -1) {
            dp[s] += dp[s - num]  // downward: each number used at most once
        }
    }
    return dp[p]
}

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    """LC 97. Interleaving String.

    dp[i][j] = can the prefixes s1[:i] and s2[:j] interleave into the
    prefix of s3 -- whose index is always i + j, so no third dimension
    exists. A cell is True when the next s3 character matches the next
    character of s1 (extending dp[i-1][j]) or of s2 (extending
    dp[i][j-1]). Check the length sum first: unequal lengths fail
    immediately. One rolling row over s2 holds the table.
    O(m*n) time, O(min(m, n)) space.
    """
    if len(s1) + len(s2) != len(s3):
        return False
    if len(s2) > len(s1):
        s1, s2 = s2, s1  # interleaving is symmetric; roll the shorter
    weaves = [True] * (len(s2) + 1)
    for j in range(1, len(s2) + 1):
        weaves[j] = weaves[j - 1] and s2[j - 1] == s3[j - 1]  # s1 empty
    for i in range(1, len(s1) + 1):
        weaves[0] = weaves[0] and s1[i - 1] == s3[i - 1]  # s2 empty
        for j in range(1, len(s2) + 1):
            from_s1 = weaves[j] and s1[i - 1] == s3[i + j - 1]  # old row: above
            from_s2 = weaves[j - 1] and s2[j - 1] == s3[i + j - 1]  # left
            weaves[j] = from_s1 or from_s2
    return weaves[-1]

// LC 97. Boolean dp over prefix pairs (i, j): true when a matching character
// from s1 or from s2 extends a true predecessor. The index into s3 is always
// i + j, so no third dimension is needed, and unequal total lengths fail
// immediately. One rolling row over s2's prefixes gives O(n) space.
bool isInterleave(string s1, string s2, string s3) {
    int m = static_cast<int>(s1.size()), n = static_cast<int>(s2.size());
    if (m + n != static_cast<int>(s3.size())) return false;  // lengths must add up
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int j = 1; j <= n; ++j) dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
    for (int i = 1; i <= m; ++i) {
        dp[0] = dp[0] && s1[i - 1] == s3[i - 1];
        for (int j = 1; j <= n; ++j) {
            bool fromS1 = dp[j] && s1[i - 1] == s3[i + j - 1];      // consume from s1
            bool fromS2 = dp[j - 1] && s2[j - 1] == s3[i + j - 1];  // consume from s2
            dp[j] = fromS1 || fromS2;
        }
    }
    return dp[n];
}

/// LC 97. dp over prefix pairs (i, j): true when a matching character from s1
/// or s2 extends a true predecessor. The index into s3 is always i + j, so no
/// third dimension exists; a length-sum mismatch fails immediately. Rolled
/// over i, with dp[0] (the s2-only column) maintained inside the sweep.
pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
    let (a, b, c) = (s1.as_bytes(), s2.as_bytes(), s3.as_bytes());
    if a.len() + b.len() != c.len() {
        return false;
    }
    let mut dp = vec![false; b.len() + 1];
    dp[0] = true;
    for j in 1..=b.len() {
        dp[j] = dp[j - 1] && b[j - 1] == c[j - 1];
    }
    for i in 1..=a.len() {
        dp[0] = dp[0] && a[i - 1] == c[i - 1];
        for j in 1..=b.len() {
            dp[j] = (dp[j] && a[i - 1] == c[i + j - 1]) || (dp[j - 1] && b[j - 1] == c[i + j - 1]);
        }
    }
    dp[b.len()]
}

/** LC 97. dp over prefix pairs (i, j); s3's index is always i + j, so one rolling boolean row suffices. Length mismatch fails instantly. */
export function isInterleave(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  if (m + n !== s3.length) return false;
  const dp: boolean[] = new Array(n + 1).fill(false); // dp[j]: s1[0..i) and s2[0..j) weave s3[0..i+j)
  dp[0] = true;
  for (let j = 1; j <= n; j++) dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1]; // row i = 0: s2 alone
  for (let i = 1; i <= m; i++) {
    dp[0] = dp[0] && s1[i - 1] === s3[i - 1]; // column j = 0: s1 alone
    for (let j = 1; j <= n; j++) {
      dp[j] =
        (dp[j] && s1[i - 1] === s3[i + j - 1]) || // old dp[j] is row i-1: take a char from s1
        (dp[j - 1] && s2[j - 1] === s3[i + j - 1]); // take a char from s2
    }
  }
  return dp[n];
}

// LC 97. dp over prefix pairs (i, j); the s3 index is always i + j, so no
// third dimension exists, and unequal total lengths fail immediately.
func isInterleave(s1, s2, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false // lengths must add up
	}
	dp := make([]bool, n+1)
	dp[0] = true
	for j := 1; j <= n; j++ {
		dp[j] = dp[j-1] && s2[j-1] == s3[j-1] // s1 empty
	}
	for i := 1; i <= m; i++ {
		dp[0] = dp[0] && s1[i-1] == s3[i-1] // s2 empty
		for j := 1; j <= n; j++ {
			fromS1 := dp[j] && s1[i-1] == s3[i+j-1]   // old row: consume from s1
			fromS2 := dp[j-1] && s2[j-1] == s3[i+j-1] // left: consume from s2
			dp[j] = fromS1 || fromS2
		}
	}
	return dp[n]
}

// LC 97. dp over prefix pairs (i, j): the s3 index is always i + j, so no
// third dimension exists; unequal total lengths fail immediately.
func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
    let a = Array(s1), b = Array(s2), c = Array(s3)
    let m = a.count, n = b.count
    if m + n != c.count { return false }  // lengths must add up
    var dp = [Bool](repeating: false, count: n + 1)
    dp[0] = true
    for j in stride(from: 1, through: n, by: 1) {
        dp[j] = dp[j - 1] && b[j - 1] == c[j - 1]  // s1 empty
    }
    for i in stride(from: 1, through: m, by: 1) {
        dp[0] = dp[0] && a[i - 1] == c[i - 1]  // s2 empty
        for j in stride(from: 1, through: n, by: 1) {
            let fromS1 = dp[j] && a[i - 1] == c[i + j - 1]      // consume from s1
            let fromS2 = dp[j - 1] && b[j - 1] == c[i + j - 1]  // consume from s2
            dp[j] = fromS1 || fromS2
        }
    }
    return dp[n]
}

def stone_game(piles: list[int]) -> bool:
    """LC 877. Stone Game.

    Interval dp on the SCORE DIFFERENCE: best_lead(i, j) is (mover's
    score - opponent's score) with piles i..j remaining; the mover takes
    an end pile and SUBTRACTS the opponent's best on what is left,
    because the roles swap. Alice wins iff best_lead over the whole row
    is positive. NOTE: with an even pile count and an odd total the
    first player provably always wins (she can claim all even-indexed
    or all odd-indexed piles, whichever group is heavier), so `return
    True` passes LeetCode -- but compute the table anyway, because the
    interval pattern is what transfers to the harder variants. O(n^2)
    time and space.
    """

    @lru_cache(maxsize=None)
    def best_lead(i: int, j: int) -> int:
        if i > j:
            return 0  # no piles left, no lead either way
        take_left = piles[i] - best_lead(i + 1, j)  # minus: roles swap
        take_right = piles[j] - best_lead(i, j - 1)
        return max(take_left, take_right)

    return best_lead(0, len(piles) - 1) > 0

// LC 877. Interval dp on the score DIFFERENCE: dp over [i, j] is the mover's
// best lead on that interval, taking an end pile minus the opponent's lead on
// the rest. Growing intervals by length lets one rolling array work: dp[i]
// holds the previous length's value for [i, i+len-2]. (With an even pile count
// Alice always wins, so `return true` passes, but this pattern transfers.)
bool stoneGame(vector<int> piles) {
    int n = static_cast<int>(piles.size());
    vector<int> dp(piles);  // length-1 intervals: take the lone pile
    for (int len = 2; len <= n; ++len)
        for (int i = 0; i + len <= n; ++i)
            dp[i] = max(piles[i] - dp[i + 1],            // take left end
                        piles[i + len - 1] - dp[i]);     // take right end
    return dp[0] > 0;
}

/// LC 877. Interval dp on the score DIFFERENCE: dp[i][j] is the mover's best
/// lead on piles[i..=j], taking an end pile minus the opponent's lead on the
/// rest. Even pile count + odd total means Alice always wins (return true
/// would pass), but the interval pattern is what transfers to harder games.
pub fn stone_game(piles: Vec<i32>) -> bool {
    let n = piles.len();
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
        dp[i][i] = piles[i];
    }
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);
        }
    }
    dp[0][n - 1] > 0
}

/** LC 877. Interval dp on the score DIFFERENCE rolled by length: take an end pile minus the opponent's lead on the rest. (Alice provably always wins, but the pattern is the point.) */
export function stoneGame(piles: number[]): boolean {
  const n = piles.length;
  const dp = piles.slice(); // length-1 intervals: the mover takes the lone pile
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      // entering this step, dp[i] holds interval [i, i+len-2] and dp[i+1] holds [i+1, i+len-1]
      dp[i] = Math.max(piles[i] - dp[i + 1], piles[i + len - 1] - dp[i]);
    }
  }
  return dp[0] > 0; // Alice's best lead over the whole row
}

// LC 877. Interval dp on the score DIFFERENCE: take an end pile MINUS the
// opponent's lead on the rest; growing by length lets one rolling array work.
func stoneGame(piles []int) bool {
	n := len(piles)
	dp := make([]int, n)
	copy(dp, piles) // length-1 intervals: take the lone pile
	for length := 2; length <= n; length++ {
		for i := 0; i+length <= n; i++ {
			left := piles[i] - dp[i+1]         // take left end
			right := piles[i+length-1] - dp[i] // take right end
			if left > right {
				dp[i] = left
			} else {
				dp[i] = right
			}
		}
	}
	return dp[0] > 0
}

// LC 877. Interval dp on the score DIFFERENCE: take an end pile minus the
// opponent's lead on the rest; grow intervals by length over a rolling array.
func stoneGame(_ piles: [Int]) -> Bool {
    let n = piles.count
    var dp = piles  // length-1 intervals: take the lone pile
    for len in stride(from: 2, through: n, by: 1) {
        for i in 0...(n - len) {
            dp[i] = max(piles[i] - dp[i + 1],         // take left end
                        piles[i + len - 1] - dp[i])   // take right end
        }
    }
    return dp[0] > 0
}

def stone_game_ii(piles: list[int]) -> int:
    """LC 1140. Stone Game II.

    best(i, M) = the most stones the MOVER can collect from the suffix
    starting at pile i with limit M. The collapse to one score: the
    mover's haul is the whole suffix total MINUS whatever the opponent
    secures after the move, so never track two scores. For each allowed
    X in 1..2M the opponent faces best(i + X, max(M, X)); minimize the
    opponent. Precomputed suffix sums make every "total from i" O(1),
    and once 2M covers the remainder the mover simply takes everything.
    O(n^2) states, O(n) choices each: O(n^3) time, O(n^2) space.
    """
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def best(i: int, m: int) -> int:
        if 2 * m >= n - i:
            return suffix[i]  # the limit covers the rest: take it all
        # whole suffix minus the best the opponent can secure after X piles
        return suffix[i] - min(
            best(i + x, max(m, x)) for x in range(1, 2 * m + 1)
        )

    return best(0, 1)

// LC 1140. Memoize dp(i, M), the best total the mover collects from suffix i:
// the suffix sum minus the opponent's best over every allowed X in 1..2M, with
// M becoming max(M, X). Precomputing suffix sums turns each choice into
// "total minus opponent", avoiding tracking two scores; when 2M reaches the
// remaining pile count the mover simply takes everything.
int stoneGameII(vector<int> piles) {
    int n = static_cast<int>(piles.size());
    vector<int> suffix(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) suffix[i] = suffix[i + 1] + piles[i];
    vector<vector<int>> memo(n, vector<int>(n + 1, -1));
    auto dfs = [&](auto&& self, int i, int M) -> int {
        if (i >= n) return 0;
        if (i + 2 * M >= n) return suffix[i];  // take everything that remains
        int& cached = memo[i][M];
        if (cached != -1) return cached;
        int best = 0;
        for (int x = 1; x <= 2 * M; ++x)
            best = max(best, suffix[i] - self(self, i + x, max(M, x)));
        return cached = best;
    };
    return dfs(dfs, 0, 1);
}

/// LC 1140. Memoize dp(i, m) = best total the mover collects from suffix i
/// with bound m, maximizing suffix[i] - dp(i + x, max(m, x)) over x in
/// 1..=2m. Precomputed suffix sums turn each choice into total-minus-opponent
/// so only one score is tracked; when 2m covers the rest, take everything.
pub fn stone_game_ii(piles: Vec<i32>) -> i32 {
    fn solve(i: usize, m: usize, suffix: &[i32], memo: &mut Vec<Vec<i32>>) -> i32 {
        let n = suffix.len() - 1;
        if i + 2 * m >= n {
            return suffix[i]; // bound covers the suffix: take it all
        }
        if memo[i][m] != -1 {
            return memo[i][m];
        }
        let mut best = 0;
        for x in 1..=2 * m {
            best = best.max(suffix[i] - solve(i + x, m.max(x), suffix, memo));
        }
        memo[i][m] = best;
        best
    }
    let n = piles.len();
    let mut suffix = vec![0i32; n + 1];
    for i in (0..n).rev() {
        suffix[i] = suffix[i + 1] + piles[i];
    }
    let mut memo = vec![vec![-1i32; n + 1]; n];
    solve(0, 1, &suffix, &mut memo)
}

/** LC 1140. Memoized dp(i, M) = mover's best total from suffix i = suffixSum[i] - opponent's best over X in 1..2M; take everything once 2M covers the rest. */
export function stoneGameII(piles: number[]): number {
  const n = piles.length;
  const suffix: number[] = new Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];
  const memo = new Map<number, number>();
  function best(i: number, m: number): number {
    if (i + 2 * m >= n) return suffix[i]; // allowed to take every remaining pile
    const key = i * (n + 1) + m;
    const cached = memo.get(key);
    if (cached !== undefined) return cached;
    let opponentBest = Infinity;
    for (let x = 1; x <= 2 * m; x++) {
      opponentBest = Math.min(opponentBest, best(i + x, Math.max(m, x)));
    }
    const result = suffix[i] - opponentBest; // the mover keeps whatever the opponent cannot claim
    memo.set(key, result);
    return result;
  }
  return best(0, 1);
}

// LC 1140. dp(i, M) = suffix total MINUS the opponent's best over X in 1..2M
// with M -> max(M, X); once 2M covers the rest the mover takes everything.
func stoneGameII(piles []int) int {
	n := len(piles)
	suffix := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		suffix[i] = suffix[i+1] + piles[i]
	}
	memo := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, n+1)
		for m := range memo[i] {
			memo[i][m] = -1
		}
	}
	var best func(i, m int) int
	best = func(i, m int) int {
		if i >= n {
			return 0
		}
		if i+2*m >= n {
			return suffix[i] // the limit covers the rest: take it all
		}
		if memo[i][m] != -1 {
			return memo[i][m]
		}
		res := 0
		for x := 1; x <= 2*m; x++ {
			nextM := m
			if x > nextM {
				nextM = x
			}
			// whole suffix minus the best the opponent secures after X piles
			if v := suffix[i] - best(i+x, nextM); v > res {
				res = v
			}
		}
		memo[i][m] = res
		return res
	}
	return best(0, 1)
}

// LC 1140. Memoized dp(i, M): the mover's haul is the suffix total MINUS the
// opponent's best over X in 1..2M; once 2M covers the rest, take everything.
func stoneGameII(_ piles: [Int]) -> Int {
    let n = piles.count
    var suffix = [Int](repeating: 0, count: n + 1)
    for i in stride(from: n - 1, through: 0, by: -1) {
        suffix[i] = suffix[i + 1] + piles[i]
    }
    var memo = [[Int]](repeating: [Int](repeating: -1, count: n + 1), count: n)
    func best(_ i: Int, _ m: Int) -> Int {
        if i >= n { return 0 }
        if i + 2 * m >= n { return suffix[i] }  // take everything that remains
        if memo[i][m] != -1 { return memo[i][m] }
        var haul = 0
        for x in 1...(2 * m) {
            haul = max(haul, suffix[i] - best(i + x, max(m, x)))
        }
        memo[i][m] = haul
        return haul
    }
    return best(0, 1)
}

def longest_increasing_path(matrix: list[list[int]]) -> int:
    """LC 329. Longest Increasing Path in a Matrix.

    DFS from every cell with memoization: memo[(r, c)] caches the
    longest strictly increasing path STARTING at (r, c), built from the
    four neighbors holding larger values. WHY no visited set: edges
    only ever point from a smaller value to a larger one, so the
    implicit graph is a DAG -- no path can revisit a cell -- and each
    cell's answer finalizes after one resolution. O(m*n) time and
    space.
    """
    rows, cols = len(matrix), len(matrix[0])
    memo: dict[tuple[int, int], int] = {}

    def longest_from(r: int, c: int) -> int:
        if (r, c) not in memo:
            best = 1  # the cell alone is a path of length one
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + longest_from(nr, nc))
            memo[(r, c)] = best
        return memo[(r, c)]

    return max(longest_from(r, c) for r in range(rows) for c in range(cols))

// LC 329. DFS from every cell with memoization: memo[r][c] caches the longest
// strictly increasing path starting there, built from neighbors holding larger
// values. The strict increase makes the implicit graph a DAG, so no visited
// set is needed and each cell resolves exactly once -- O(mn) time.
int longestIncreasingPath(vector<vector<int>> matrix) {
    int m = static_cast<int>(matrix.size());
    int n = static_cast<int>(matrix[0].size());
    vector<vector<int>> memo(m, vector<int>(n, 0));
    const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    auto dfs = [&](auto&& self, int r, int c) -> int {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
                best = max(best, 1 + self(self, nr, nc));
        }
        return memo[r][c] = best;
    };
    int answer = 0;
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c) answer = max(answer, dfs(dfs, r, c));
    return answer;
}

/// LC 329. DFS from every cell with memo[r][c] = longest increasing path
/// starting there, built from strictly larger neighbors. Strict increase
/// makes the implicit graph a DAG, so no visited set is needed and each cell
/// resolves exactly once: O(mn). Zero doubles as the "uncomputed" marker
/// since every real path has length >= 1.
pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
    fn dfs(r: usize, c: usize, matrix: &[Vec<i32>], memo: &mut Vec<Vec<i32>>) -> i32 {
        if memo[r][c] != 0 {
            return memo[r][c];
        }
        let (rows, cols) = (matrix.len() as i32, matrix[0].len() as i32);
        let mut best = 1;
        for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
            let (nr, nc) = (r as i32 + dr, c as i32 + dc);
            if (0..rows).contains(&nr)
                && (0..cols).contains(&nc)
                && matrix[nr as usize][nc as usize] > matrix[r][c]
            {
                best = best.max(1 + dfs(nr as usize, nc as usize, matrix, memo));
            }
        }
        memo[r][c] = best;
        best
    }
    let mut memo = vec![vec![0; matrix[0].len()]; matrix.len()];
    let mut longest = 0;
    for r in 0..matrix.len() {
        for c in 0..matrix[0].len() {
            longest = longest.max(dfs(r, c, &matrix, &mut memo));
        }
    }
    longest
}

/** LC 329. DFS + memo from every cell; strict increase makes the graph a DAG, so no visited set and each cell resolves once: O(mn). */
export function longestIncreasingPath(matrix: number[][]): number {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const memo: number[][] = Array.from({ length: rows }, () => new Array<number>(cols).fill(0));
  const deltas = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  function dfs(r: number, c: number): number {
    if (memo[r][c] !== 0) return memo[r][c]; // 0 doubles as "uncomputed": real answers are >= 1
    let best = 1; // the cell by itself
    for (const [dr, dc] of deltas) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }
    memo[r][c] = best;
    return best;
  }
  let longest = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      longest = Math.max(longest, dfs(r, c));
    }
  }
  return longest;
}

// LC 329. DFS + memo on the increasing DAG: strictly increasing edges mean no
// path can revisit a cell, so no visited set is needed; each cell resolves once.
func longestIncreasingPath(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
	}
	dr := [4]int{1, -1, 0, 0}
	dc := [4]int{0, 0, 1, -1}
	var longestFrom func(r, c int) int
	longestFrom = func(r, c int) int {
		if memo[r][c] != 0 {
			return memo[r][c]
		}
		best := 1 // the cell alone is a path of length one
		for d := 0; d < 4; d++ {
			nr, nc := r+dr[d], c+dc[d]
			if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c] {
				if v := 1 + longestFrom(nr, nc); v > best {
					best = v
				}
			}
		}
		memo[r][c] = best
		return best
	}
	answer := 0
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if v := longestFrom(r, c); v > answer {
				answer = v
			}
		}
	}
	return answer
}

// LC 329. DFS + memo on the longest increasing path STARTING at each cell;
// strict increase makes the graph a DAG, so no visited set is needed.
func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
    let m = matrix.count, n = matrix[0].count
    var memo = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
    func longestFrom(_ r: Int, _ c: Int) -> Int {
        if memo[r][c] != 0 { return memo[r][c] }
        var best = 1  // the cell alone is a path of length one
        for (nr, nc) in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] {
            if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c] {
                best = max(best, 1 + longestFrom(nr, nc))
            }
        }
        memo[r][c] = best
        return best
    }
    var answer = 0
    for r in 0..<m {
        for c in 0..<n {
            answer = max(answer, longestFrom(r, c))
        }
    }
    return answer
}

def num_distinct(s: str, t: str) -> int:
    """LC 115. Distinct Subsequences.

    Count table over prefix pairs: ways[j] = how many distinct
    subsequences of the s-prefix seen so far spell t[:j]. When the new
    s character matches t[j - 1], the count is USE-THE-MATCH (the
    diagonal, old ways[j - 1]) PLUS SKIP this s character (old
    ways[j]); on a mismatch the skip value alone carries down. Sweeping
    j downward keeps the old row readable in place. Base: empty t is
    produced exactly one way. Python ints never overflow, so the
    "counts grow enormous" warning costs nothing here.
    O(len(s) * len(t)) time, O(len(t)) space.
    """
    ways = [1] + [0] * len(t)  # ways[0] = 1: delete all of s to spell ""
    for ch in s:
        for j in range(len(t), 0, -1):  # downward: ways[j-1] is still old
            if ch == t[j - 1]:
                ways[j] += ways[j - 1]  # use the match + existing skips
    return ways[-1]

// LC 115. Count table over prefix pairs: on a character match, add the ways
// that use the match (diagonal) to the ways that skip this character of s
// (above); otherwise carry the skip value alone. Empty t gives one way as the
// base case. A single row swept DOWNWARD per character of s preserves the
// diagonal; counts explode, so the cells are unsigned long long.
int numDistinct(string s, string t) {
    int n = static_cast<int>(t.size());
    vector<unsigned long long> dp(n + 1, 0);
    dp[0] = 1;  // empty t: one way (delete everything)
    for (char c : s)
        for (int j = n; j >= 1; --j)  // downward keeps dp[j-1] from the previous row
            if (t[j - 1] == c) dp[j] += dp[j - 1];
    return static_cast<int>(dp[n]);
}

/// LC 115. Count table over prefix pairs, rolled to one row indexed by t's
/// prefix length: on a match add the diagonal (use the match) to the value
/// already there (skip this s character). Sweeping j DOWNWARD keeps the
/// diagonal from the previous row alive. dp[0] = 1 is the empty-t base case;
/// counts explode, so the cells are u64.
pub fn num_distinct(s: String, t: String) -> i32 {
    let (sb, tb) = (s.as_bytes(), t.as_bytes());
    let mut dp = vec![0u64; tb.len() + 1];
    dp[0] = 1;
    for &cs in sb {
        for j in (0..tb.len()).rev() {
            if tb[j] == cs {
                dp[j + 1] += dp[j];
            }
        }
    }
    dp[tb.len()] as i32
}

/** LC 115. Count table over prefix pairs: on a match add use-it (diagonal) to skip-it (above); one rolling row swept DOWNWARD per char of s. */
export function numDistinct(s: string, t: string): number {
  const n = t.length;
  const dp: number[] = new Array(n + 1).fill(0); // dp[j]: ways the scanned prefix of s spells t[0..j)
  dp[0] = 1; // the empty t is matched exactly once: delete everything
  for (const ch of s) {
    for (let j = n; j >= 1; j--) {
      // downward: dp[j-1] still excludes ch, so the match is not reused
      if (t[j - 1] === ch) dp[j] += dp[j - 1];
    }
  }
  return dp[n];
}

// LC 115. Count table: on a match add USE-THE-MATCH (the diagonal) to SKIP
// (above); sweeping j downward keeps the previous row's diagonal readable.
func numDistinct(s, t string) int {
	n := len(t)
	dp := make([]int, n+1)
	dp[0] = 1 // empty t: one way (delete everything)
	for i := 0; i < len(s); i++ {
		for j := n; j >= 1; j-- { // downward keeps dp[j-1] from the previous row
			if t[j-1] == s[i] {
				dp[j] += dp[j-1] // use the match + existing skips
			}
		}
	}
	return dp[n]
}

// LC 115. On a match, add the ways that USE it (diagonal) to the ways that
// SKIP this s character; sweeping j downward keeps the old row readable.
func numDistinct(_ s: String, _ t: String) -> Int {
    let tChars = Array(t)
    let n = tChars.count
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 1  // empty t: one way (delete everything)
    for c in s {
        for j in stride(from: n, through: 1, by: -1) where tChars[j - 1] == c {
            dp[j] += dp[j - 1]  // use the match + existing skips
        }
    }
    return dp[n]
}

def min_distance(word1: str, word2: str) -> int:
    """LC 72. Edit Distance.

    edits[i][j] = fewest operations turning word1[:i] into word2[:j].
    Matching characters copy the diagonal for free; otherwise pay one
    plus the minimum of the three neighbors -- WHICH OP EACH BRANCH IS:

        diagonal (i-1, j-1)  REPLACE word1's char with word2's
        left     (i,   j-1)  INSERT word2's char into word1
        above    (i-1, j  )  DELETE word1's char

    Bases: an empty prefix costs the other prefix's full length. Two
    rolling rows give O(min(m, n)) space; O(m*n) time.
    """
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # distance is symmetric; roll the shorter
    prev = list(range(len(word2) + 1))  # "" -> word2[:j] is j inserts
    for i, ch1 in enumerate(word1, start=1):
        curr = [i]  # word1[:i] -> "" is i deletes
        for j, ch2 in enumerate(word2, start=1):
            if ch1 == ch2:
                curr.append(prev[j - 1])  # match: diagonal, no cost
            else:
                curr.append(
                    1
                    + min(
                        prev[j - 1],  # replace ch1 with ch2
                        curr[j - 1],  # insert ch2 after the prefix
                        prev[j],  # delete ch1
                    )
                )
        prev = curr
    return prev[-1]

// LC 72. Table over prefix pairs: matching characters copy the diagonal for
// free, otherwise one plus the minimum of the three neighbors -- above is
// delete, left is insert, diagonal is replace. Base cases are the empty
// prefixes costing i or j outright. One rolling row plus a saved diagonal
// variable gives O(n) space.
int minDistance(string word1, string word2) {
    int m = static_cast<int>(word1.size()), n = static_cast<int>(word2.size());
    vector<int> dp(n + 1);
    for (int j = 0; j <= n; ++j) dp[j] = j;  // empty word1: j insertions
    for (int i = 1; i <= m; ++i) {
        int diag = dp[0];  // dp[i-1][j-1] before it is overwritten
        dp[0] = i;         // empty word2: i deletions
        for (int j = 1; j <= n; ++j) {
            int above = dp[j];
            dp[j] = (word1[i - 1] == word2[j - 1])
                        ? diag                                   // match: free
                        : 1 + min({dp[j], dp[j - 1], diag});     // delete/insert/replace
            diag = above;
        }
    }
    return dp[n];
}

/// LC 72. Table over prefix pairs: matching characters copy the diagonal for
/// free, otherwise 1 + min(diagonal, above, left) -- replace, delete from
/// word1, insert into word1. Base cases are the empty prefixes costing i or j
/// outright (the seeded 0..=n first row); two rolling rows hold the state.
pub fn min_distance(word1: String, word2: String) -> i32 {
    let (a, b) = (word1.as_bytes(), word2.as_bytes());
    let mut prev: Vec<i32> = (0..=b.len() as i32).collect();
    let mut cur = vec![0i32; b.len() + 1];
    for (i, &ca) in a.iter().enumerate() {
        cur[0] = i as i32 + 1;
        for (j, &cb) in b.iter().enumerate() {
            cur[j + 1] = if ca == cb {
                prev[j]
            } else {
                1 + prev[j].min(prev[j + 1]).min(cur[j])
            };
        }
        std::mem::swap(&mut prev, &mut cur);
    }
    prev[b.len()]
}

/** LC 72. Prefix-pair table: match copies the diagonal free, else 1 + min(replace=diagonal, delete=above, insert=left); empty prefixes cost their length. */
export function minDistance(word1: string, word2: string): number {
  const n = word2.length;
  const dp: number[] = Array.from({ length: n + 1 }, (_, j) => j); // from empty word1: j inserts
  for (let i = 1; i <= word1.length; i++) {
    let diagonal = dp[0]; // dp[i-1][j-1], saved before this row overwrites it
    dp[0] = i; // to empty word2: i deletes
    for (let j = 1; j <= n; j++) {
      const above = dp[j]; // dp[i-1][j]
      dp[j] =
        word1[i - 1] === word2[j - 1]
          ? diagonal // characters agree: no operation
          : 1 + Math.min(diagonal, above, dp[j - 1]); // replace / delete / insert
      diagonal = above;
    }
  }
  return dp[n];
}

// LC 72. A match copies the diagonal free; otherwise 1 + min of above (delete),
// left (insert), diagonal (replace). One rolling row plus a saved diagonal.
func minDistance(word1, word2 string) int {
	n := len(word2)
	dp := make([]int, n+1)
	for j := 0; j <= n; j++ {
		dp[j] = j // empty word1: j insertions
	}
	for i := 1; i <= len(word1); i++ {
		diag := dp[0] // dp[i-1][j-1] before it is overwritten
		dp[0] = i     // empty word2: i deletions
		for j := 1; j <= n; j++ {
			above := dp[j]
			if word1[i-1] == word2[j-1] {
				dp[j] = diag // match: free
			} else {
				cheapest := diag // replace
				if dp[j] < cheapest {
					cheapest = dp[j] // delete
				}
				if dp[j-1] < cheapest {
					cheapest = dp[j-1] // insert
				}
				dp[j] = 1 + cheapest
			}
			diag = above
		}
	}
	return dp[n]
}

// LC 72. Matching characters copy the diagonal for free; otherwise pay one
// plus the min of three neighbors: above = delete, left = insert, diagonal = replace.
func minDistance(_ word1: String, _ word2: String) -> Int {
    let a = Array(word1), b = Array(word2)
    let n = b.count
    var dp = Array(0...n)  // empty word1: j insertions
    for i in stride(from: 1, through: a.count, by: 1) {
        var diag = dp[0]  // dp[i-1][j-1] before it is overwritten
        dp[0] = i         // empty word2: i deletions
        for j in stride(from: 1, through: n, by: 1) {
            let above = dp[j]
            dp[j] = a[i - 1] == b[j - 1]
                ? diag                                // match: free
                : 1 + min(dp[j], dp[j - 1], diag)     // delete/insert/replace
            diag = above
        }
    }
    return dp[n]
}

def max_coins(nums: list[int]) -> int:
    """LC 312. Burst Balloons.

    Pad the row with virtual 1-balloons, then interval dp: coins(l, r)
    is the best haul from bursting everything STRICTLY between walls l
    and r. Choose which balloon k pops LAST in that open interval.
    WHY LAST, NOT FIRST: when k is last, everything between the walls
    is already gone, so k's neighbors at pop time are exactly the walls
    -- its score is pinned at padded[l] * padded[k] * padded[r], and
    the two sides (l, k) and (k, r) can never interact through it.
    Popping first leaves the halves coupled by shifting neighbors, and
    the subproblems stop being independent. O(n^3) time, O(n^2) space.
    """
    padded = [1] + nums + [1]  # virtual walls; out-of-range neighbors count as 1

    @lru_cache(maxsize=None)
    def coins(l: int, r: int) -> int:
        if r - l < 2:
            return 0  # no balloon strictly between the walls
        return max(
            coins(l, k) + padded[l] * padded[k] * padded[r] + coins(k, r)
            for k in range(l + 1, r)  # k is the LAST pop inside (l, r)
        )

    return coins(0, len(padded) - 1)

// LC 312. Pad the array with 1s and run interval dp on OPEN intervals (l, r):
// maximize over the balloon k popped LAST inside, scoring a[l]*a[k]*a[r] plus
// the two subintervals. Choosing the last pop rather than the first is the
// insight -- it fixes k's neighbors as the interval borders, decoupling the
// halves. O(n^3) time, O(n^2) space.
int maxCoins(vector<int> nums) {
    int n = static_cast<int>(nums.size());
    vector<int> a(n + 2, 1);  // virtual 1-balloons on both ends
    for (int i = 0; i < n; ++i) a[i + 1] = nums[i];
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 2; len <= n + 1; ++len)  // len = r - l
        for (int l = 0; l + len <= n + 1; ++l) {
            int r = l + len;
            for (int k = l + 1; k < r; ++k)  // k bursts last in (l, r)
                dp[l][r] = max(dp[l][r], a[l] * a[k] * a[r] + dp[l][k] + dp[k][r]);
        }
    return dp[0][n + 1];
}

/// LC 312. Pad with 1s, then interval dp choosing which balloon pops LAST in
/// the open interval (l, r): popping k last fixes its neighbors as the
/// borders, scoring padded[l] * padded[k] * padded[r] plus both decoupled
/// halves. Choosing the first pop instead would entangle the halves -- the
/// last-balloon flip is the entire insight.
pub fn max_coins(nums: Vec<i32>) -> i32 {
    let mut padded = vec![1i32];
    padded.extend(&nums);
    padded.push(1);
    let n = padded.len();
    let mut dp = vec![vec![0i32; n]; n];
    for len in 2..n {
        for l in 0..n - len {
            let r = l + len;
            for k in l + 1..r {
                dp[l][r] =
                    dp[l][r].max(padded[l] * padded[k] * padded[r] + dp[l][k] + dp[k][r]);
            }
        }
    }
    dp[0][n - 1]
}

/** LC 312. Pad with 1s; interval dp where k is the LAST balloon popped in (l, r), so its neighbors are exactly the borders and the halves decouple. */
export function maxCoins(nums: number[]): number {
  const balloons = [1, ...nums, 1]; // phantom 1s give edge bursts real neighbors
  const n = balloons.length;
  const dp: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  // dp[l][r] = best coins from bursting everything STRICTLY between l and r
  for (let l = n - 3; l >= 0; l--) {
    for (let r = l + 2; r < n; r++) {
      for (let k = l + 1; k < r; k++) {
        // popped last, k sees l and r still standing on either side
        dp[l][r] = Math.max(dp[l][r], balloons[l] * balloons[k] * balloons[r] + dp[l][k] + dp[k][r]);
      }
    }
  }
  return dp[0][n - 1];
}

// LC 312. Pad with 1s and pick the balloon popped LAST in each open interval:
// its neighbors are then pinned to the walls, decoupling the two sides.
func maxCoins(nums []int) int {
	n := len(nums)
	a := make([]int, n+2)
	a[0], a[n+1] = 1, 1 // virtual 1-balloons on both ends
	copy(a[1:], nums)
	dp := make([][]int, n+2)
	for i := range dp {
		dp[i] = make([]int, n+2)
	}
	for length := 2; length <= n+1; length++ { // length = r - l
		for l := 0; l+length <= n+1; l++ {
			r := l + length
			for k := l + 1; k < r; k++ { // k bursts last in (l, r)
				if v := a[l]*a[k]*a[r] + dp[l][k] + dp[k][r]; v > dp[l][r] {
					dp[l][r] = v
				}
			}
		}
	}
	return dp[0][n+1]
}

// LC 312. Pad with virtual 1-balloons and pick which balloon pops LAST in
// each open interval: its neighbors are then pinned to the interval walls.
func maxCoins(_ nums: [Int]) -> Int {
    let n = nums.count
    var a = [Int](repeating: 1, count: n + 2)  // virtual 1-balloons on both ends
    for i in 0..<n { a[i + 1] = nums[i] }
    var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 2), count: n + 2)
    for len in stride(from: 2, through: n + 1, by: 1) {  // len = r - l
        for l in 0...(n + 1 - len) {
            let r = l + len
            for k in (l + 1)..<r {  // k bursts last in (l, r)
                dp[l][r] = max(dp[l][r], a[l] * a[k] * a[r] + dp[l][k] + dp[k][r])
            }
        }
    }
    return dp[0][n + 1]
}

def is_match(s: str, p: str) -> bool:
    """LC 10. Regular Expression Matching.

    matches[i][j] = does p[:j] match ALL of s[:i], where '.' matches
    any character and '*' means zero or more of the element it follows
    (a star is always glued to p[j - 2]). BOTH STAR BRANCHES:

        zero copies  -- drop the element and its star: matches[i][j-2]
        one more     -- if p[j - 2] fits s[i - 1], consume that s
                        character and KEEP the star live: matches[i-1][j]

    A plain character (or '.') consumes one from each on a fit, taking
    the diagonal. Seed the empty-string ROW too, so patterns like
    "a*b*" still match "" through the zero-copies branch.
    O(m*n) time and space.
    """
    m, n = len(s), len(p)
    matches = [[False] * (n + 1) for _ in range(m + 1)]
    matches[0][0] = True  # empty pattern matches empty string
    for j in range(2, n + 1):
        if p[j - 1] == "*":
            matches[0][j] = matches[0][j - 2]  # "" matches "a*b*..." via zero copies
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                zero_copies = matches[i][j - 2]  # skip element + star outright
                element_fits = p[j - 2] in (s[i - 1], ".")
                one_more = element_fits and matches[i - 1][j]  # star stays live
                matches[i][j] = zero_copies or one_more
            else:
                fits = p[j - 1] in (s[i - 1], ".")
                matches[i][j] = fits and matches[i - 1][j - 1]  # diagonal
    return matches[m][n]

// LC 10. Boolean dp over prefix pairs where '.' matches any character and '*'
// gives two branches: zero copies (skip the element and its star, dp[i][j-2])
// or one more copy when the preceding element matches s's current character
// (dp[i-1][j]). Initializing the empty-string row for patterns like a*b* and
// tying each '*' to its PRECEDING element are the usual failure points.
bool isMatch(string s, string p) {
    int n = static_cast<int>(s.size()), m = static_cast<int>(p.size());
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int j = 2; j <= m; ++j)  // empty s vs a*, a*b*, ...
        if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (p[j - 1] == '*') {
                bool zero = (j >= 2) && dp[i][j - 2];  // drop "x*" entirely
                bool more = (j >= 2) && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) &&
                            dp[i - 1][j];  // one more copy of the element
                dp[i][j] = zero || more;
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == '.' || p[j - 1] == s[i - 1]);
            }
        }
    return dp[n][m];
}

/// LC 10. Boolean dp over byte-prefix pairs. A '*' (always bound to the
/// element before it) branches two ways: zero copies via dp[i][j - 2], or one
/// more copy via dp[i - 1][j] when the preceding element matches s[i - 1].
/// Plain characters and '.' need the diagonal plus a match. The empty-string
/// row must be seeded so patterns like a*b* match "" -- the classic miss.
pub fn is_match(s: String, p: String) -> bool {
    let (sb, pb) = (s.as_bytes(), p.as_bytes());
    let (m, n) = (sb.len(), pb.len());
    let mut dp = vec![vec![false; n + 1]; m + 1];
    dp[0][0] = true;
    for j in 1..=n {
        if pb[j - 1] == b'*' {
            dp[0][j] = dp[0][j - 2];
        }
    }
    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if pb[j - 1] == b'*' {
                dp[i][j - 2] || ((pb[j - 2] == sb[i - 1] || pb[j - 2] == b'.') && dp[i - 1][j])
            } else {
                (pb[j - 1] == sb[i - 1] || pb[j - 1] == b'.') && dp[i - 1][j - 1]
            };
        }
    }
    dp[m][n]
}

/** LC 10. Boolean dp over prefix pairs; '*' branches into zero copies (skip element+star) or one more copy (consume s[i-1], stay at j). Seed the empty-s row for a*b* prefixes. */
export function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;
  const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array<boolean>(n + 1).fill(false));
  dp[0][0] = true;
  function single(i: number, j: number): boolean {
    // does s[i-1] match the lone pattern element p[j-1]?
    return p[j - 1] === "." || p[j - 1] === s[i - 1];
  }
  for (let j = 2; j <= n; j++) {
    // patterns like a*b*c* can match the empty string by zeroing every starred element
    if (p[j - 1] === "*") dp[0][j] = dp[0][j - 2];
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        // a star binds to p[j-2]: drop the pair entirely, or absorb one more matching character
        dp[i][j] = dp[i][j - 2] || (single(i, j - 1) && dp[i - 1][j]);
      } else {
        dp[i][j] = single(i, j) && dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

// LC 10. A star gives two branches: zero copies (drop "x*", dp[i][j-2]) or one
// more copy when the preceding element fits (dp[i-1][j]); seed the empty row.
func isMatch(s, p string) bool {
	n, m := len(s), len(p)
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, m+1)
	}
	dp[0][0] = true           // empty pattern matches empty string
	for j := 2; j <= m; j++ { // empty s vs a*, a*b*, ...
		if p[j-1] == '*' {
			dp[0][j] = dp[0][j-2]
		}
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if p[j-1] == '*' {
				zero := j >= 2 && dp[i][j-2] // drop "x*" entirely
				more := j >= 2 && (p[j-2] == '.' || p[j-2] == s[i-1]) &&
					dp[i-1][j] // one more copy: the star stays live
				dp[i][j] = zero || more
			} else {
				dp[i][j] = dp[i-1][j-1] && (p[j-1] == '.' || p[j-1] == s[i-1])
			}
		}
	}
	return dp[n][m]
}

// LC 10. '*' gives two branches: ZERO copies (drop the element and its star)
// or ONE MORE (element fits, star stays live); '.' matches any character.
func isMatch(_ s: String, _ p: String) -> Bool {
    let sc = Array(s), pc = Array(p)
    let n = sc.count, m = pc.count
    var dp = [[Bool]](repeating: [Bool](repeating: false, count: m + 1), count: n + 1)
    dp[0][0] = true  // empty pattern matches empty string
    for j in stride(from: 2, through: m, by: 1) where pc[j - 1] == "*" {
        dp[0][j] = dp[0][j - 2]  // empty s vs a*, a*b*, ... via zero copies
    }
    for i in stride(from: 1, through: n, by: 1) {
        for j in stride(from: 1, through: m, by: 1) {
            if pc[j - 1] == "*" {
                let zero = j >= 2 && dp[i][j - 2]  // drop "x*" entirely
                let more = j >= 2 && (pc[j - 2] == "." || pc[j - 2] == sc[i - 1])
                    && dp[i - 1][j]  // one more copy of the element
                dp[i][j] = zero || more
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == "." || pc[j - 1] == sc[i - 1])
            }
        }
    }
    return dp[n][m]
}