1-D Dynamic Programming

def climb_stairs(n: int) -> int:
    """LC 70. Climbing Stairs.

    The ways to reach step i equal the ways to reach i - 1 plus the
    ways to reach i - 2 (the last move was a single or a double), which
    is Fibonacci in disguise. Iterate up from the base cases keeping
    only two rolling variables -- no memo table needed. O(n) time,
    O(1) space.
    """
    ways_prev, ways_here = 1, 1  # ways to stand on step 0 and step 1
    for _ in range(n - 1):
        ways_prev, ways_here = ways_here, ways_prev + ways_here
    return ways_here

// LC 70. The ways to reach step i equal the ways to reach i-1 plus the ways
// to reach i-2 (the last move was either one or two steps), so this is
// Fibonacci in disguise. Iterate up from the base cases with two rolling
// variables: O(n) time, O(1) space, no memo table needed.
int climbStairs(int n) {
    int prev = 1, cur = 1;  // ways to stand on steps 0 and 1
    for (int i = 2; i <= n; ++i) {
        int next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

/// LC 70. Ways to reach step i = ways(i - 1) + ways(i - 2): Fibonacci in
/// disguise. Two rolling variables replace the table for O(n)/O(1).
pub fn climb_stairs(n: i32) -> i32 {
    let (mut two_back, mut one_back) = (1, 1); // ways to stand on steps 0 and 1
    for _ in 2..=n {
        let cur = one_back + two_back;
        two_back = one_back;
        one_back = cur;
    }
    one_back
}

/** LC 70. Fibonacci in disguise: ways(i) = ways(i-1) + ways(i-2); two rolling variables, O(1) space. */
export function climbStairs(n: number): number {
  let twoBack = 1; // ways to stand on step i-2 (step 0: one way, do nothing)
  let oneBack = 1; // ways to stand on step i-1 (step 1: one way)
  for (let i = 2; i <= n; i++) {
    [twoBack, oneBack] = [oneBack, twoBack + oneBack];
  }
  return oneBack;
}

// LC 70. Each step lands from one or two below, so the count is Fibonacci in
// disguise; two rolling variables, no memo table needed.
func climbStairs(n int) int {
	prev, cur := 1, 1 // ways to stand on steps 0 and 1
	for i := 2; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

// LC 70. Each step lands from one or two below; Fibonacci in disguise,
// iterated up with two rolling variables.
func climbStairs(_ n: Int) -> Int {
    var prev = 1, cur = 1  // ways to stand on steps 0 and 1
    for _ in stride(from: 2, through: n, by: 1) {
        (prev, cur) = (cur, prev + cur)
    }
    return cur
}

def min_cost_climbing_stairs(cost: list[int]) -> int:
    """LC 746. Min Cost Climbing Stairs.

    best_from[i] = cost[i] + min(best of the two stairs below); the
    climb may start on stair 0 or 1, so both bases are just their own
    cost. The subtlety: the top is one step PAST the array, so either
    of the last two stairs can finish the climb -- answer with the
    smaller of the final two values. O(n) time, O(1) space.
    """
    two_back, one_back = cost[0], cost[1]
    for stair_cost in cost[2:]:
        two_back, one_back = one_back, stair_cost + min(two_back, one_back)
    return min(two_back, one_back)  # the top is reachable from either one

// LC 746. dp[i] = cost[i] + min(dp[i-1], dp[i-2]) is the cheapest way to be
// standing ON stair i having paid its cost. The subtlety: the top sits one
// PAST the array, so either of the last two stairs can finish the climb and
// the answer is the smaller of the final two dp values.
int minCostClimbingStairs(vector<int> cost) {
    int two = cost[0], one = cost[1];  // dp[i-2], dp[i-1]
    for (int i = 2; i < static_cast<int>(cost.size()); ++i) {
        int cur = cost[i] + min(one, two);
        two = one;
        one = cur;
    }
    return min(one, two);  // step off from either of the last two stairs
}

/// LC 746. dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]). The subtlety: the top
/// sits one PAST the array, so either of the last two stairs can finish the
/// climb and the answer is the min of the final two rolling values.
pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
    let (mut two_back, mut one_back) = (cost[0], cost[1]);
    for &c in &cost[2..] {
        let cur = c + one_back.min(two_back);
        two_back = one_back;
        one_back = cur;
    }
    one_back.min(two_back)
}

/** LC 746. dp[i] = cost[i] + min(prev two); the top sits one PAST the array, so answer min of the last two. */
export function minCostClimbingStairs(cost: number[]): number {
  let twoBack = cost[0]; // cheapest total ending on stair i-2
  let oneBack = cost[1]; // cheapest total ending on stair i-1
  for (let i = 2; i < cost.length; i++) {
    [twoBack, oneBack] = [oneBack, cost[i] + Math.min(twoBack, oneBack)];
  }
  return Math.min(twoBack, oneBack); // either of the last two stairs can finish the climb
}

// LC 746. dp[i] = cost[i] + min of the two stairs below; the top sits one
// PAST the array, so either of the last two stairs can finish the climb.
func minCostClimbingStairs(cost []int) int {
	two, one := cost[0], cost[1] // dp[i-2], dp[i-1]
	for i := 2; i < len(cost); i++ {
		cheaper := one
		if two < one {
			cheaper = two
		}
		two, one = one, cost[i]+cheaper
	}
	if two < one {
		return two // step off from either of the last two stairs
	}
	return one
}

// LC 746. dp[i] = cost[i] + min of the two stairs below; the top sits one
// PAST the array, so answer with the smaller of the final two values.
func minCostClimbingStairs(_ cost: [Int]) -> Int {
    var two = cost[0], one = cost[1]  // dp[i-2], dp[i-1]
    for i in stride(from: 2, to: cost.count, by: 1) {
        (two, one) = (one, cost[i] + min(one, two))
    }
    return min(one, two)  // step off from either of the last two stairs
}

def tribonacci(n: int) -> int:
    """LC 1137. N-th Tribonacci Number.

    T0 = 0, T1 = T2 = 1, and each later term sums the previous three.
    Return the bases directly for n < 3, then shift three rolling
    variables forward; the only care point is keeping the rotation
    order straight. O(n) time, O(1) space.
    """
    if n == 0:
        return 0
    if n < 3:
        return 1
    three_back, two_back, one_back = 0, 1, 1
    for _ in range(n - 2):
        three_back, two_back, one_back = (
            two_back,
            one_back,
            three_back + two_back + one_back,
        )
    return one_back

// LC 1137. T0 = 0, T1 = T2 = 1, each later term sums the previous three.
// Return the base cases directly for n < 3, then rotate three rolling
// variables forward; the only care point is keeping the rotation order
// straight. O(n) time, O(1) space.
int tribonacci(int n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;
    int a = 0, b = 1, c = 1;  // T(i-3), T(i-2), T(i-1)
    for (int i = 3; i <= n; ++i) {
        int next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    return c;
}

/// LC 1137. Fibonacci with three rolling variables: T0 = 0, T1 = T2 = 1, each
/// later term sums the previous three. Return base cases directly for n < 3
/// and keep the rotation order straight.
pub fn tribonacci(n: i32) -> i32 {
    if n == 0 {
        return 0;
    }
    let (mut a, mut b, mut c) = (0, 1, 1); // T0, T1, T2
    for _ in 3..=n {
        let next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    c
}

/** LC 1137. Three rolling variables summing forward; return the base cases directly for n < 3. */
export function tribonacci(n: number): number {
  if (n === 0) return 0;
  if (n < 3) return 1;
  let a = 0;
  let b = 1;
  let c = 1;
  for (let i = 3; i <= n; i++) {
    [a, b, c] = [b, c, a + b + c];
  }
  return c;
}

// LC 1137. T0 = 0, T1 = T2 = 1, each later term sums the previous three;
// rotate three rolling variables forward, keeping the order straight.
func tribonacci(n int) int {
	if n == 0 {
		return 0
	}
	if n <= 2 {
		return 1
	}
	a, b, c := 0, 1, 1 // T(i-3), T(i-2), T(i-1)
	for i := 3; i <= n; i++ {
		a, b, c = b, c, a+b+c
	}
	return c
}

// LC 1137. T0 = 0, T1 = T2 = 1, each later term sums the previous three;
// rotate three rolling variables and keep the order straight.
func tribonacci(_ n: Int) -> Int {
    if n == 0 { return 0 }
    if n <= 2 { return 1 }
    var a = 0, b = 1, c = 1  // T(i-3), T(i-2), T(i-1)
    for _ in 3...n {
        (a, b, c) = (b, c, a + b + c)
    }
    return c
}

def rob(nums: list[int]) -> int:
    """LC 198. House Robber.

    Sweep once with a rolling rob/skip pair: robbed_here is the best
    haul that takes the current house (so the previous one was
    skipped), skipped_here is the best that leaves it (carry the better
    of the two previous states forward). No two adjacent houses are
    ever both taken because robbing always builds on skipped_here.
    O(n) time, O(1) space.
    """
    robbed_here, skipped_here = 0, 0
    for value in nums:
        robbed_here, skipped_here = (
            skipped_here + value,  # rob it: forced to have skipped the last one
            max(robbed_here, skipped_here),  # skip it: keep the better history
        )
    return max(robbed_here, skipped_here)

// LC 198. For each house take the better of skipping it (keep the previous
// best) or robbing it (its value plus the best from two houses back). Two
// rolling variables carry the whole state; the invariant is that prev1 is the
// optimal answer for the prefix ending at the previous house.
int rob(vector<int> nums) {
    int prev2 = 0, prev1 = 0;  // best for prefixes ending 2 back / 1 back
    for (int value : nums) {
        int cur = max(prev1, prev2 + value);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

/// LC 198. At each house choose the better of skipping it (previous best) or
/// robbing it (its value plus the best from two back). Two rolling variables
/// hold the whole state; each step stores the optimal answer for that prefix.
pub fn rob(nums: Vec<i32>) -> i32 {
    let (mut two_back, mut one_back) = (0, 0);
    for &x in &nums {
        let cur = one_back.max(two_back + x);
        two_back = one_back;
        one_back = cur;
    }
    one_back
}

/** LC 198. Per house: skip (keep previous best) or rob (value + best from two back); two rolling variables. */
export function rob(nums: number[]): number {
  let twoBack = 0; // optimal loot for the prefix ending two houses ago
  let oneBack = 0; // optimal loot for the prefix ending one house ago
  for (const value of nums) {
    [twoBack, oneBack] = [oneBack, Math.max(oneBack, twoBack + value)];
  }
  return oneBack;
}

// LC 198. Rolling rob/skip pair: take the better of skipping the house (keep
// the previous best) or robbing it (its value plus the best two houses back).
func rob(nums []int) int {
	prev2, prev1 := 0, 0 // best for prefixes ending 2 back / 1 back
	for _, value := range nums {
		cur := prev2 + value // rob it
		if prev1 > cur {
			cur = prev1 // skip it: keep the better history
		}
		prev2, prev1 = prev1, cur
	}
	return prev1
}

// LC 198. Per house: skip it (keep the previous best) or rob it (its value
// plus the best from two back); two rolling variables carry the state.
func rob(_ nums: [Int]) -> Int {
    var prev2 = 0, prev1 = 0  // best for prefixes ending 2 back / 1 back
    for value in nums {
        (prev2, prev1) = (prev1, max(prev1, prev2 + value))
    }
    return prev1
}

def rob_circle(nums: list[int]) -> int:
    """LC 213. House Robber II.

    House Robber on a circle: the first and last houses are now
    adjacent, so they cannot both be robbed. WHY the circle splits into
    two cases: every valid plan either skips house 0 or skips the last
    house (it cannot take both), and once one of them is excluded the
    wraparound constraint disappears -- what remains is an ordinary
    straight street. Run linear rob on nums without the first house and
    on nums without the last, and take the larger. The single-house
    array is the special case neither slice covers. O(n) time, O(n)
    space for the slices.
    """
    if len(nums) == 1:
        return nums[0]  # both slices below would be empty otherwise
    return max(rob(nums[1:]), rob(nums[:-1]))

// LC 213. The houses form a circle, so the first and last are adjacent and
// cannot both be taken. Run the linear House Robber routine twice -- once
// without the first house, once without the last -- and return the larger;
// splitting the circle into two overlapping lines removes the wraparound
// constraint. A single house is the special case neither line covers.
int robCircle(vector<int> nums) {
    int n = static_cast<int>(nums.size());
    if (n == 1) return nums[0];
    auto linear = [&](int lo, int hi) -> int {  // rob houses in [lo, hi]
        int prev2 = 0, prev1 = 0;
        for (int i = lo; i <= hi; ++i) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    };
    return max(linear(0, n - 2), linear(1, n - 1));
}

/// LC 213. Circular street: house 0 and house n-1 can never both be taken, so
/// run the linear LC 198 sweep twice -- once without the first house, once
/// without the last -- and keep the larger. A single house is the special case
/// both slices would miss.
pub fn rob_circle(nums: Vec<i32>) -> i32 {
    fn linear(houses: &[i32]) -> i32 {
        let (mut two_back, mut one_back) = (0, 0);
        for &x in houses {
            let cur = one_back.max(two_back + x);
            two_back = one_back;
            one_back = cur;
        }
        one_back
    }
    if nums.len() == 1 {
        return nums[0];
    }
    linear(&nums[1..]).max(linear(&nums[..nums.len() - 1]))
}

/** LC 213. Circle = max of two LINEAR runs: drop the first house, then drop the last; one house is special. */
export function robCircle(nums: number[]): number {
  if (nums.length === 1) return nums[0]; // both linear runs would be empty otherwise
  function linear(lo: number, hi: number): number {
    let twoBack = 0;
    let oneBack = 0;
    for (let i = lo; i < hi; i++) {
      [twoBack, oneBack] = [oneBack, Math.max(oneBack, twoBack + nums[i])];
    }
    return oneBack;
  }
  // first and last are adjacent on the circle, so no optimal plan uses both
  return Math.max(linear(0, nums.length - 1), linear(1, nums.length));
}

// LC 213. Circle = max of two straight streets: run linear rob without the
// first house and without the last; excluding one end removes the wraparound.
func robCircle(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0] // neither line below covers the lone house
	}
	linear := func(lo, hi int) int { // rob houses in [lo, hi]
		prev2, prev1 := 0, 0
		for i := lo; i <= hi; i++ {
			cur := prev2 + nums[i]
			if prev1 > cur {
				cur = prev1
			}
			prev2, prev1 = prev1, cur
		}
		return prev1
	}
	withoutLast, withoutFirst := linear(0, n-2), linear(1, n-1)
	if withoutLast > withoutFirst {
		return withoutLast
	}
	return withoutFirst
}

// LC 213. The circle makes the first and last houses adjacent: run linear
// House Robber without the first house and without the last, take the larger.
func robCircle(_ nums: [Int]) -> Int {
    let n = nums.count
    if n == 1 { return nums[0] }  // the special case neither line covers
    func linear(_ lo: Int, _ hi: Int) -> Int {  // rob houses in [lo, hi]
        var prev2 = 0, prev1 = 0
        for i in lo...hi {
            (prev2, prev1) = (prev1, max(prev1, prev2 + nums[i]))
        }
        return prev1
    }
    return max(linear(0, n - 2), linear(1, n - 1))
}

def longest_palindrome(s: str) -> str:
    """LC 5. Longest Palindromic Substring.

    For each of the 2n - 1 centers, expand outward while the two ends
    match and remember the widest span. Odd-length palindromes center
    on a character, even-length ones on the gap BETWEEN characters --
    forgetting the gap centers is the classic miss. O(n^2) time, O(1)
    extra space.
    """
    best_lo, best_hi = 0, 0  # inclusive bounds of the widest palindrome seen

    def expand(lo: int, hi: int) -> None:
        nonlocal best_lo, best_hi
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        lo += 1  # the loop overshot by one step on each side; back off
        hi -= 1
        if hi - lo > best_hi - best_lo:
            best_lo, best_hi = lo, hi

    for center in range(len(s)):
        expand(center, center)  # odd length: center on s[center]
        expand(center, center + 1)  # even length: center in the gap after it
    return s[best_lo : best_hi + 1]

// LC 5. For each of the 2n-1 centers -- every character and every gap between
// characters -- expand outward while the two ends match, tracking the longest
// span seen. The between-character centers are what catch even-length
// palindromes, the part people forget. O(n^2) time, O(1) extra space.
string longestPalindrome(string s) {
    int n = static_cast<int>(s.size());
    int bestStart = 0, bestLen = 1;
    auto expand = [&](int lo, int hi) -> void {
        while (lo >= 0 && hi < n && s[lo] == s[hi]) {
            --lo;
            ++hi;
        }
        if (hi - lo - 1 > bestLen) {  // (lo, hi) is now one past each end
            bestLen = hi - lo - 1;
            bestStart = lo + 1;
        }
    };
    for (int center = 0; center < n; ++center) {
        expand(center, center);      // odd length
        expand(center, center + 1);  // even length
    }
    return s.substr(bestStart, bestLen);
}

/// LC 5. Expand around each of the 2n - 1 centers on the byte slice: every
/// index (odd lengths) and every gap between indices (even lengths -- the
/// centers people forget). Track the longest half-open range seen. O(n^2)
/// time, O(1) extra space.
pub fn longest_palindrome(s: String) -> String {
    fn expand(b: &[u8], left: usize, right: usize) -> (usize, usize) {
        let (mut l, mut r) = (left as isize, right as isize);
        while l >= 0 && (r as usize) < b.len() && b[l as usize] == b[r as usize] {
            l -= 1;
            r += 1;
        }
        ((l + 1) as usize, r as usize) // half-open [start, end)
    }
    let b = s.as_bytes();
    let (mut best_start, mut best_len) = (0, 0);
    for center in 0..b.len() {
        for (l, r) in [(center, center), (center, center + 1)] {
            let (start, end) = expand(b, l, r);
            if end - start > best_len {
                best_start = start;
                best_len = end - start;
            }
        }
    }
    s[best_start..best_start + best_len].to_string()
}

/** LC 5. Expand around all 2n-1 centers (chars AND gaps for even lengths), tracking the widest window. */
export function longestPalindrome(s: string): string {
  let bestStart = 0;
  let bestLen = 0;
  function expand(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    const len = right - left - 1; // the loop overshot by one on each side
    if (len > bestLen) {
      bestLen = len;
      bestStart = left + 1;
    }
  }
  for (let center = 0; center < s.length; center++) {
    expand(center, center); // odd length: center is a character
    expand(center, center + 1); // even length: center is the gap after it
  }
  return s.slice(bestStart, bestStart + bestLen);
}

// LC 5. Expand around all 2n-1 centers -- every character and every gap
// between characters; the gap centers catch the even-length palindromes.
func longestPalindrome(s string) string {
	n := len(s)
	bestStart, bestLen := 0, 0
	expand := func(lo, hi int) {
		for lo >= 0 && hi < n && s[lo] == s[hi] {
			lo--
			hi++
		}
		if hi-lo-1 > bestLen { // (lo, hi) is now one past each end
			bestLen = hi - lo - 1
			bestStart = lo + 1
		}
	}
	for center := 0; center < n; center++ {
		expand(center, center)   // odd length
		expand(center, center+1) // even length
	}
	return s[bestStart : bestStart+bestLen]
}

// LC 5. Expand around all 2n-1 centers -- characters AND the gaps between
// them (the gaps catch even-length palindromes) -- tracking the widest span.
func longestPalindrome(_ s: String) -> String {
    let chars = Array(s)
    let n = chars.count
    var bestStart = 0, bestLen = 1
    func expand(_ from: Int, _ to: Int) {
        var lo = from, hi = to
        while lo >= 0 && hi < n && chars[lo] == chars[hi] {
            lo -= 1
            hi += 1
        }
        if hi - lo - 1 > bestLen {  // (lo, hi) is now one past each end
            bestLen = hi - lo - 1
            bestStart = lo + 1
        }
    }
    for center in 0..<n {
        expand(center, center)      // odd length
        expand(center, center + 1)  // even length
    }
    return String(chars[bestStart..<(bestStart + bestLen)])
}

def count_substrings(s: str) -> int:
    """LC 647. Palindromic Substrings.

    Same center expansion as Longest Palindromic Substring, but count
    INSIDE the loop: every successful widening from any of the 2n - 1
    centers is itself one distinct palindromic substring, so adding one
    per step gives the exact total with nothing double-counted (each
    substring has exactly one center). O(n^2) time, O(1) space.
    """
    palindromes = 0

    def expand(lo: int, hi: int) -> None:
        nonlocal palindromes
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            palindromes += 1  # each widening is one new palindrome
            lo -= 1
            hi += 1

    for center in range(len(s)):
        expand(center, center)  # odd-length palindromes
        expand(center, center + 1)  # even-length palindromes
    return palindromes

// LC 647. Same center expansion as Longest Palindromic Substring, but every
// successful expansion step is itself a distinct palindrome, so count one
// INSIDE the loop per step rather than measuring after it. Summing over all
// 2n-1 odd and even centers gives the exact total in O(n^2).
int countSubstrings(string s) {
    int n = static_cast<int>(s.size());
    int count = 0;
    auto expand = [&](int lo, int hi) -> void {
        while (lo >= 0 && hi < n && s[lo] == s[hi]) {
            ++count;  // each step outward is one more palindrome
            --lo;
            ++hi;
        }
    };
    for (int center = 0; center < n; ++center) {
        expand(center, center);      // odd length
        expand(center, center + 1);  // even length
    }
    return count;
}

/// LC 647. Same center expansion as LC 5, but every successful expansion step
/// IS a distinct palindrome, so count one per matching step inside the loop
/// instead of measuring at the end.
pub fn count_substrings(s: String) -> i32 {
    fn expand(b: &[u8], left: usize, right: usize) -> i32 {
        let (mut l, mut r) = (left as isize, right as isize);
        let mut count = 0;
        while l >= 0 && (r as usize) < b.len() && b[l as usize] == b[r as usize] {
            count += 1;
            l -= 1;
            r += 1;
        }
        count
    }
    let mut total = 0;
    for center in 0..s.len() {
        total += expand(s.as_bytes(), center, center);
        total += expand(s.as_bytes(), center, center + 1);
    }
    total
}

/** LC 647. Same 2n-1 center expansion; every successful widening step IS a distinct palindrome, so count inside the loop. */
export function countSubstrings(s: string): number {
  let count = 0;
  function expand(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++; // each step outward is one more palindromic substring
      left--;
      right++;
    }
  }
  for (let center = 0; center < s.length; center++) {
    expand(center, center);
    expand(center, center + 1);
  }
  return count;
}

// LC 647. Same center expansion, but count INSIDE the loop: every successful
// widening from any of the 2n-1 centers is itself one distinct palindrome.
func countSubstrings(s string) int {
	n := len(s)
	count := 0
	expand := func(lo, hi int) {
		for lo >= 0 && hi < n && s[lo] == s[hi] {
			count++ // each step outward is one more palindrome
			lo--
			hi++
		}
	}
	for center := 0; center < n; center++ {
		expand(center, center)   // odd length
		expand(center, center+1) // even length
	}
	return count
}

// LC 647. Same center expansion as Longest Palindromic Substring, but every
// successful widening IS one distinct palindrome -- count inside the loop.
func countSubstrings(_ s: String) -> Int {
    let chars = Array(s)
    let n = chars.count
    var count = 0
    func expand(_ from: Int, _ to: Int) {
        var lo = from, hi = to
        while lo >= 0 && hi < n && chars[lo] == chars[hi] {
            count += 1  // each step outward is one more palindrome
            lo -= 1
            hi += 1
        }
    }
    for center in 0..<n {
        expand(center, center)      // odd length
        expand(center, center + 1)  // even length
    }
    return count
}

def num_decodings(s: str) -> int:
    """LC 91. Decode Ways.

    Walk left to right with ways[i] for the prefix of length i: add
    ways[i - 1] when the current digit alone is valid (nonzero), and
    add ways[i - 2] when the two-digit number sits in 10..26. Zeros are
    the whole difficulty -- '0' decodes nothing alone and only rides
    inside 10 or 20, so a stranded zero kills every decoding. Two
    rolling variables hold the table. O(n) time, O(1) space.
    """
    if s[0] == "0":
        return 0  # a leading zero can never be decoded
    two_back, one_back = 1, 1  # ways for the empty prefix and prefix of length 1
    for i in range(1, len(s)):
        ways = 0
        if s[i] != "0":
            ways += one_back  # take one digit: '1'..'9'
        if 10 <= int(s[i - 1 : i + 1]) <= 26:
            ways += two_back  # take two digits: '10'..'26' ('06' fails here)
        if ways == 0:
            return 0  # stranded zero (or dead prefix): no decoding survives
        two_back, one_back = one_back, ways
    return one_back

// LC 91. dp over prefix lengths: take dp[i-1] when the current digit is
// nonzero, add dp[i-2] when the two-digit number lies in 10..26. Zeros are
// the whole difficulty -- a leading or stranded '0' ("06", "100") has no
// decoding and kills the branch, which the two guards encode. Two rolling
// variables give O(1) space.
int numDecodings(string s) {
    if (s.empty() || s[0] == '0') return 0;
    int prev2 = 1, prev1 = 1;  // dp[0] = empty prefix, dp[1] = first digit
    for (int i = 2; i <= static_cast<int>(s.size()); ++i) {
        int cur = 0;
        if (s[i - 1] != '0') cur += prev1;  // single digit 1..9
        int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (two >= 10 && two <= 26) cur += prev2;  // pair 10..26
        if (cur == 0) return 0;                    // stranded zero: no branch survives
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

/// LC 91. dp[i] over prefix length i: add dp[i - 1] when the current digit is
/// nonzero, add dp[i - 2] when the two-digit number lands in 10..=26. Zeros
/// are the whole difficulty -- a lone or invalid '0' kills every branch, so a
/// prefix that hits zero ways can return 0 immediately.
pub fn num_decodings(s: String) -> i32 {
    let b = s.as_bytes();
    if b[0] == b'0' {
        return 0;
    }
    let (mut two_back, mut one_back) = (1, 1); // dp[0] = dp[1] = 1
    for i in 1..b.len() {
        let mut cur = 0;
        if b[i] != b'0' {
            cur += one_back;
        }
        let two_digit = (b[i - 1] - b'0') * 10 + (b[i] - b'0');
        if (10..=26).contains(&two_digit) {
            cur += two_back;
        }
        if cur == 0 {
            return 0; // zero trap: '0' with no valid 10/20 pairing
        }
        two_back = one_back;
        one_back = cur;
    }
    one_back
}

/** LC 91. dp over prefix lengths: add dp[i-1] for a nonzero digit, dp[i-2] for a pair in 10..26; zeros kill branches. */
export function numDecodings(s: string): number {
  if (s[0] === "0") return 0; // no letter starts with 0
  let twoBack = 1; // ways for the prefix two shorter (empty prefix decodes one way)
  let oneBack = 1; // ways for the prefix one shorter
  for (let i = 1; i < s.length; i++) {
    let curr = 0;
    if (s[i] !== "0") curr += oneBack; // single digit 1..9
    const pair = Number(s[i - 1]) * 10 + Number(s[i]);
    if (pair >= 10 && pair <= 26) curr += twoBack; // two digits 10..26 ("06" is NOT "6")
    if (curr === 0) return 0; // a stranded or invalid 0 strands every decoding
    [twoBack, oneBack] = [oneBack, curr];
  }
  return oneBack;
}

// LC 91. Add dp[i-1] when the digit alone is nonzero and dp[i-2] when the
// pair is 10..26; zeros are the trap -- a stranded '0' kills every decoding.
func numDecodings(s string) int {
	if len(s) == 0 || s[0] == '0' {
		return 0
	}
	prev2, prev1 := 1, 1 // empty prefix and prefix of length 1
	for i := 2; i <= len(s); i++ {
		cur := 0
		if s[i-1] != '0' {
			cur += prev1 // single digit 1..9
		}
		two := int(s[i-2]-'0')*10 + int(s[i-1]-'0')
		if two >= 10 && two <= 26 {
			cur += prev2 // pair 10..26 ("06" fails here)
		}
		if cur == 0 {
			return 0 // stranded zero: no branch survives
		}
		prev2, prev1 = prev1, cur
	}
	return prev1
}

// LC 91. Take one digit (nonzero) or two digits (10..26); zeros are the
// trap -- a leading or stranded '0' kills every decoding.
func numDecodings(_ s: String) -> Int {
    let digits = Array(s)
    if digits.isEmpty || digits[0] == "0" { return 0 }
    var prev2 = 1, prev1 = 1  // dp[0] = empty prefix, dp[1] = first digit
    for i in stride(from: 2, through: digits.count, by: 1) {
        var cur = 0
        if digits[i - 1] != "0" { cur += prev1 }  // single digit 1..9
        let two = digits[i - 2].wholeNumberValue! * 10 + digits[i - 1].wholeNumberValue!
        if two >= 10 && two <= 26 { cur += prev2 }  // pair 10..26
        if cur == 0 { return 0 }  // stranded zero: no branch survives
        (prev2, prev1) = (prev1, cur)
    }
    return prev1
}

def coin_change(coins: list[int], amount: int) -> int:
    """LC 322. Coin Change.

    Unbounded min-coins table: fewest[a] is one plus the minimum of
    fewest[a - coin] over every coin that fits. Initialize entries to
    the sentinel amount + 1 -- larger than any real answer -- so
    unreachable amounts never win the min, and translate a surviving
    sentinel into -1 at the end. O(amount * len(coins)) time,
    O(amount) space.
    """
    unreachable = amount + 1  # sentinel: beats any real coin count
    fewest = [unreachable] * (amount + 1)
    fewest[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                fewest[a] = min(fewest[a], fewest[a - coin] + 1)
    return fewest[amount] if fewest[amount] != unreachable else -1

// LC 322. Unbounded knapsack over amounts: dp[a] = 1 + min(dp[a - coin]) over
// every coin that fits, with dp[0] = 0. Initialize entries to the sentinel
// amount+1 so unreachable values never win the min, then translate a
// surviving sentinel into -1 at the end. O(amount * coins).
int coinChange(vector<int> coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);  // sentinel: more coins than possible
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int coin : coins)
            if (coin <= a) dp[a] = min(dp[a], 1 + dp[a - coin]);
    return dp[amount] > amount ? -1 : dp[amount];
}

/// LC 322. Unbounded knapsack over amounts: dp[a] = 1 + min(dp[a - coin]).
/// Initialize to the sentinel amount + 1 so unreachable values never win the
/// min, then translate a surviving sentinel into -1.
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let amount = amount as usize;
    let sentinel = amount as i32 + 1;
    let mut dp = vec![sentinel; amount + 1];
    dp[0] = 0;
    for a in 1..=amount {
        for &coin in &coins {
            if coin as usize <= a {
                dp[a] = dp[a].min(dp[a - coin as usize] + 1);
            }
        }
    }
    if dp[amount] == sentinel { -1 } else { dp[amount] }
}

/** LC 322. dp over amounts: dp[a] = 1 + min(dp[a-coin]); the amount+1 sentinel never wins a min and maps to -1. */
export function coinChange(coins: number[], amount: number): number {
  const UNREACHABLE = amount + 1; // more than any real answer can ever use
  const dp: number[] = new Array(amount + 1).fill(UNREACHABLE);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === UNREACHABLE ? -1 : dp[amount];
}

// LC 322. Unbounded min-coins table: dp[a] = 1 + min(dp[a-coin]), seeded with
// the sentinel amount+1 so unreachable amounts never win; sentinel becomes -1.
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		dp[a] = amount + 1 // sentinel: more coins than possible
	}
	for a := 1; a <= amount; a++ {
		for _, coin := range coins {
			if coin <= a && dp[a-coin]+1 < dp[a] {
				dp[a] = dp[a-coin] + 1
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

// LC 322. Unbounded min-coins table: dp[a] = 1 + min(dp[a - coin]); seed
// entries with the sentinel amount+1, translate a surviving sentinel to -1.
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    var dp = [Int](repeating: amount + 1, count: amount + 1)  // sentinel
    dp[0] = 0
    for a in stride(from: 1, through: amount, by: 1) {
        for coin in coins where coin <= a {
            dp[a] = min(dp[a], 1 + dp[a - coin])
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]
}

def max_product(nums: list[int]) -> int:
    """LC 152. Maximum Product Subarray.

    Sweep once tracking BOTH the maximum and minimum product of a
    subarray ending at the current index, each recomputed from the
    element alone or the element times the previous max or min. The
    minimum matters because a negative element swaps the extremes: the
    most negative product times a negative becomes the most positive.
    A zero collapses both trackers to zero, restarting naturally.
    O(n) time, O(1) space.
    """
    best = nums[0]
    max_ending_here, min_ending_here = nums[0], nums[0]
    for num in nums[1:]:
        # num < 0 swaps the roles, so compute both from the OLD pair at once
        candidates = (num, num * max_ending_here, num * min_ending_here)
        max_ending_here, min_ending_here = max(candidates), min(candidates)
        best = max(best, max_ending_here)
    return best

// LC 152. Sweep once tracking BOTH the maximum and minimum product of a
// subarray ending here, each recomputed from the element alone or the element
// times the previous max or min. The minimum matters because a negative
// element flips the most negative product into the most positive one; a zero
// resets both trackers to 0 naturally.
int maxProduct(vector<int> nums) {
    int best = nums[0], hi = nums[0], lo = nums[0];
    for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
        int x = nums[i];
        int newHi = max({x, hi * x, lo * x});
        int newLo = min({x, hi * x, lo * x});
        hi = newHi;
        lo = newLo;
        best = max(best, hi);
    }
    return best;
}

/// LC 152. Track the maximum AND minimum product ending at each index, each
/// recomputed from the element alone or the element times the previous max or
/// min. The min matters because a negative element flips the most negative
/// product into the most positive one; a zero resets both trackers naturally.
pub fn max_product(nums: Vec<i32>) -> i32 {
    let (mut max_end, mut min_end) = (nums[0], nums[0]);
    let mut best = nums[0];
    for &x in &nums[1..] {
        let candidates = [x, max_end * x, min_end * x];
        max_end = *candidates.iter().max().unwrap();
        min_end = *candidates.iter().min().unwrap();
        best = best.max(max_end);
    }
    best
}

/** LC 152. Track the running max AND min product ending here; a negative flips the most negative into the most positive. */
export function maxProduct(nums: number[]): number {
  let best = nums[0];
  let maxEnding = nums[0]; // largest product of a subarray ending at i
  let minEnding = nums[0]; // smallest (most negative) product ending at i
  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    const high = Math.max(n, n * maxEnding, n * minEnding); // start fresh or extend either tracker
    const low = Math.min(n, n * maxEnding, n * minEnding); // a zero resets both naturally
    maxEnding = high;
    minEnding = low;
    best = Math.max(best, maxEnding);
  }
  return best;
}

// LC 152. Track BOTH the max and min product ending here: a negative element
// swaps the extremes, and a zero collapses both trackers, restarting naturally.
func maxProduct(nums []int) int {
	best, hi, lo := nums[0], nums[0], nums[0]
	for _, x := range nums[1:] {
		viaHi, viaLo := hi*x, lo*x // compute both from the OLD pair at once
		hi, lo = x, x
		if viaHi > hi {
			hi = viaHi
		}
		if viaLo > hi {
			hi = viaLo
		}
		if viaHi < lo {
			lo = viaHi
		}
		if viaLo < lo {
			lo = viaLo
		}
		if hi > best {
			best = hi
		}
	}
	return best
}

// LC 152. Track the max AND min product ending here: a negative element
// swaps the extremes, and a zero resets both trackers naturally.
func maxProduct(_ nums: [Int]) -> Int {
    var best = nums[0], hi = nums[0], lo = nums[0]
    for x in nums.dropFirst() {
        (hi, lo) = (max(x, hi * x, lo * x), min(x, hi * x, lo * x))
        best = max(best, hi)
    }
    return best
}

def word_break(s: str, word_dict: list[str]) -> bool:
    """LC 139. Word Break.

    breakable[i] is True when the prefix of length i splits into
    dictionary words: dp[i] = any dp[j] and s[j:i] in dict. Seed
    breakable[0] (the empty prefix needs no words), store the words in
    a hash set, and bound j by the longest word so the inner scan never
    tests hopeless pieces. O(n^2) time worst case, O(n) space.
    """
    words = set(word_dict)
    longest = max(map(len, words), default=0)  # no piece can beat the longest word
    breakable = [False] * (len(s) + 1)
    breakable[0] = True
    for i in range(1, len(s) + 1):
        for j in range(max(0, i - longest), i):
            if breakable[j] and s[j:i] in words:
                breakable[i] = True
                break  # one valid split point is enough
    return breakable[len(s)]

// LC 139. dp[i] is true when the prefix of length i can be segmented: some
// earlier true dp[j] with s[j..i) in the dictionary, seeded with dp[0] true.
// The dictionary lives in a hash set for O(1) lookups, and bounding the
// lookback by the longest word's length trims the O(n^2) scan.
bool wordBreak(string s, vector<string> wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int maxLen = 0;
    for (const string& word : wordDict) maxLen = max(maxLen, static_cast<int>(word.size()));
    int n = static_cast<int>(s.size());
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i)
        for (int j = max(0, i - maxLen); j < i; ++j)  // lookback capped by longest word
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
    return dp[n];
}

/// LC 139. dp[i] is true when some dp[j] is true and s[j..i] is a dictionary
/// word, seeded with dp[0] = true. A hash set makes lookups O(1) and bounding
/// j by the longest word length keeps the O(n^2) scan fast.
pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let words: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
    let max_len = word_dict.iter().map(|w| w.len()).max().unwrap_or(0);
    let mut dp = vec![false; s.len() + 1];
    dp[0] = true;
    for i in 1..=s.len() {
        for j in i.saturating_sub(max_len)..i {
            if dp[j] && words.contains(&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[s.len()]
}

/** LC 139. dp[i] = some dp[j] is true and s[j..i) is a word; bound j by the longest word so the scan stays tight. */
export function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map((w) => w.length));
  const dp: boolean[] = new Array(s.length + 1).fill(false);
  dp[0] = true; // the empty prefix segments trivially
  for (let i = 1; i <= s.length; i++) {
    for (let j = Math.max(0, i - maxLen); j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

// LC 139. dp[i] = some true dp[j] with s[j:i] in the dictionary; capping the
// lookback by the longest word keeps the inner scan from hopeless pieces.
func wordBreak(s string, wordDict []string) bool {
	dict := make(map[string]bool, len(wordDict))
	maxLen := 0
	for _, word := range wordDict {
		dict[word] = true
		if len(word) > maxLen {
			maxLen = len(word)
		}
	}
	n := len(s)
	dp := make([]bool, n+1)
	dp[0] = true // the empty prefix needs no words
	for i := 1; i <= n; i++ {
		lo := i - maxLen
		if lo < 0 {
			lo = 0
		}
		for j := lo; j < i; j++ {
			if dp[j] && dict[s[j:i]] {
				dp[i] = true
				break // one valid split point is enough
			}
		}
	}
	return dp[n]
}

// LC 139. dp[i] = some earlier true dp[j] with s[j..<i] in the dictionary;
// hash-set lookups, lookback capped by the longest word's length.
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    let chars = Array(s)
    let words = Set(wordDict)
    let maxLen = wordDict.map { $0.count }.max() ?? 0
    let n = chars.count
    var dp = [Bool](repeating: false, count: n + 1)
    dp[0] = true  // the empty prefix needs no words
    for i in stride(from: 1, through: n, by: 1) {
        for j in max(0, i - maxLen)..<i where dp[j] && words.contains(String(chars[j..<i])) {
            dp[i] = true
            break  // one valid split point is enough
        }
    }
    return dp[n]
}

def length_of_lis(nums: list[int]) -> int:
    """LC 300. Longest Increasing Subsequence.

    tails[k] = the smallest tail value of any strictly increasing
    subsequence of length k + 1 seen so far. For each number, binary
    search the first tail >= it: overwrite that slot (same length,
    better tail), or append when every tail is smaller (a new longest).
    tails stays sorted -- that justifies the binary search -- but it is
    NOT itself a valid subsequence, only its length is meaningful.
    O(n log n) time, O(n) space.
    """
    tails: list[int] = []
    for num in nums:
        # bisect_left finds the first tail >= num, so an equal value
        # REPLACES its slot instead of extending -- strictness enforced
        slot = bisect_left(tails, num)
        if slot == len(tails):
            tails.append(num)  # num extends the longest subsequence by one
        else:
            tails[slot] = num  # same length k+1 now ends on a smaller tail
    return len(tails)

// LC 300. Maintain tails, where tails[k] is the smallest tail of any strictly
// increasing subsequence of length k+1; for each number lower_bound the first
// tail >= it and overwrite, appending when none exists. tails stays sorted,
// which justifies the binary search and the O(n log n) bound -- but it is NOT
// itself a valid subsequence, only its length is meaningful.
int lengthOfLIS(vector<int> nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);  // first tail >= x
        if (it == tails.end())
            tails.push_back(x);  // extends the longest subsequence
        else
            *it = x;  // same length, smaller tail
    }
    return static_cast<int>(tails.size());
}

/// LC 300. tails[k] = smallest tail of any increasing subsequence of length
/// k + 1. For each number, partition_point finds the first tail >= it (strict
/// increase, so equal tails get overwritten, never extended); overwrite that
/// slot or append. tails stays sorted -- justifying the binary search and the
/// O(n log n) bound -- but is NOT itself a valid subsequence.
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
    let mut tails: Vec<i32> = Vec::new();
    for x in nums {
        let pos = tails.partition_point(|&t| t < x);
        if pos == tails.len() {
            tails.push(x);
        } else {
            tails[pos] = x;
        }
    }
    tails.len() as i32
}

/** LC 300. tails[k] = smallest tail of any increasing subsequence of length k+1; binary search keeps it O(n log n). */
export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = []; // stays sorted, but is NOT itself a valid subsequence
  function lowerBound(target: number): number {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo; // first index whose tail is >= target
  }
  for (const num of nums) {
    const pos = lowerBound(num); // >= (not >): strict increase, so equal values overwrite
    if (pos === tails.length) tails.push(num);
    else tails[pos] = num; // a smaller tail keeps that length easier to extend
  }
  return tails.length;
}

// LC 300. tails[k] = smallest tail of any increasing subsequence of length
// k+1; binary search the first tail >= x and overwrite, appending when none.
func lengthOfLIS(nums []int) int {
	tails := []int{}
	for _, x := range nums {
		slot := sort.SearchInts(tails, x) // first tail >= x: strictness enforced
		if slot == len(tails) {
			tails = append(tails, x) // extends the longest subsequence
		} else {
			tails[slot] = x // same length, smaller tail
		}
	}
	return len(tails)
}

// LC 300. tails[k] = smallest tail of any increasing subsequence of length
// k+1; binary search the first tail >= x and overwrite, append when none.
func lengthOfLIS(_ nums: [Int]) -> Int {
    var tails: [Int] = []  // stays sorted, but is NOT itself a subsequence
    for x in nums {
        var lo = 0, hi = tails.count  // lower bound: first tail >= x
        while lo < hi {
            let mid = (lo + hi) / 2
            if tails[mid] < x { lo = mid + 1 } else { hi = mid }
        }
        if lo == tails.count {
            tails.append(x)  // extends the longest subsequence
        } else {
            tails[lo] = x  // same length, smaller tail
        }
    }
    return tails.count
}

def can_partition(nums: list[int]) -> bool:
    """LC 416. Partition Equal Subset Sum.

    Two equal halves exist iff some subset reaches total / 2, so bail
    on an odd total and run subset-sum dp: a boolean array over sums,
    updated once per number. WHY the sums iterate DOWNWARD: sweeping
    upward would mark s - num and then immediately reuse that fresh
    mark to set s, letting one number be counted twice; descending only
    ever reads marks left by PREVIOUS numbers, so each number is used
    at most once. O(n * total/2) time, O(total/2) space.
    """
    total = sum(nums)
    half, leftover = divmod(total, 2)
    if leftover:
        return False  # an odd total can never split evenly
    reachable = [False] * (half + 1)
    reachable[0] = True  # the empty subset sums to zero
    for num in nums:
        for s in range(half, num - 1, -1):  # downward: num used at most once
            if reachable[s - num]:
                reachable[s] = True
        if reachable[half]:
            return True
    return reachable[half]

// LC 416. An equal split exists iff some subset reaches total/2, so return
// false on an odd total and run subset-sum dp with a boolean array over sums,
// updated once per number. Iterating the sums DOWNWARD per number is
// essential: an upward sweep would let the same number be reused within one
// update. (Elegant alternative: bitset<10001> bits; bits = bits | bits << num
// per number, then answer bits[total / 2] -- same dp, word-parallel.)
bool canPartition(vector<int> nums) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % 2 != 0) return false;
    int target = total / 2;
    vector<bool> reachable(target + 1, false);
    reachable[0] = true;
    for (int num : nums)
        for (int s = target; s >= num; --s)  // downward: each number used once
            if (reachable[s - num]) reachable[s] = true;
    return reachable[target];
}

/// LC 416. An odd total can never split; otherwise run subset-sum dp asking
/// whether some subset reaches total / 2. Iterating the sums DOWNWARD per
/// number is essential: an upward sweep would let one number be reused.
pub fn can_partition(nums: Vec<i32>) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = (total / 2) as usize;
    let mut dp = vec![false; target + 1];
    dp[0] = true;
    for &x in &nums {
        for s in (x as usize..=target).rev() {
            if dp[s - x as usize] {
                dp[s] = true;
            }
        }
    }
    dp[target]
}

/** LC 416. Odd total is an instant no; otherwise subset-sum to total/2, sweeping sums DOWNWARD so no number is reused. */
export function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const reachable: boolean[] = new Array(target + 1).fill(false);
  reachable[0] = true;
  for (const num of nums) {
    for (let sum = target; sum >= num; sum--) {
      // downward: reachable[sum - num] still reflects the PREVIOUS numbers only
      if (reachable[sum - num]) reachable[sum] = true;
    }
    if (reachable[target]) return true;
  }
  return false;
}

// LC 416. Subset-sum to half the total, sweeping sums DOWNWARD per number so
// each number is used at most once; an odd total can never split evenly.
func canPartition(nums []int) bool {
	total := 0
	for _, num := range nums {
		total += num
	}
	if total%2 != 0 {
		return false
	}
	target := total / 2
	reachable := make([]bool, target+1)
	reachable[0] = true // the empty subset sums to zero
	for _, num := range nums {
		for s := target; s >= num; s-- { // downward: each number used once
			if reachable[s-num] {
				reachable[s] = true
			}
		}
	}
	return reachable[target]
}

// LC 416. Equal halves exist iff a subset reaches total/2: subset-sum dp
// with the sums swept DOWNWARD so each number is used at most once.
func canPartition(_ nums: [Int]) -> Bool {
    let total = nums.reduce(0, +)
    if total % 2 != 0 { return false }  // an odd total can never split evenly
    let target = total / 2
    var reachable = [Bool](repeating: false, count: target + 1)
    reachable[0] = true
    for num in nums {
        for s in stride(from: target, through: num, by: -1) where reachable[s - num] {
            reachable[s] = true
        }
    }
    return reachable[target]
}

def combination_sum4(nums: list[int], target: int) -> int:
    """LC 377. Combination Sum IV.

    Count ordered sequences summing to target: sequences[t] adds
    sequences[t - num] for every number that fits, seeded with
    sequences[0] = 1. WHY target sits in the OUTER loop: at each total
    every number gets a chance to be the LAST element, so [1, 2] and
    [2, 1] are both counted -- permutations. Coin Change II flips the
    loops (coins outside), which forces each coin to join in one fixed
    order and counts combinations instead. Loop order is the entire
    point. O(target * len(nums)) time, O(target) space.
    """
    sequences = [0] * (target + 1)
    sequences[0] = 1  # the empty sequence is the one way to make 0
    for t in range(1, target + 1):  # target OUTER: order matters
        for num in nums:
            if num <= t:
                sequences[t] += sequences[t - num]  # num as the last element
    return sequences[target]

// LC 377. dp over targets 0..target with the TARGET in the outer loop, adding
// dp[t - num] for every number that fits, seeded dp[0] = 1. Loop order is the
// entire point: target outside counts permutations (orderings distinct),
// while coins outside, as in Coin Change II, would count combinations. The
// final answer fits in 32 bits per constraints, but unsigned makes any
// intermediate wraparound defined behavior instead of UB.
int combinationSum4(vector<int> nums, int target) {
    vector<unsigned> dp(target + 1, 0);
    dp[0] = 1;
    for (int t = 1; t <= target; ++t)
        for (int num : nums)
            if (num <= t) dp[t] += dp[t - num];
    return static_cast<int>(dp[target]);
}

/// LC 377. dp[t] = sum of dp[t - num] with the TARGET in the outer loop --
/// loop order is the entire point: target outside counts permutations, while
/// numbers outside (Coin Change II) would count combinations. Intermediate
/// sub-target counts can exceed i32 even when the answer fits, so accumulate
/// in u64.
pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
    let target = target as usize;
    let mut dp = vec![0u64; target + 1];
    dp[0] = 1;
    for t in 1..=target {
        for &num in &nums {
            if num as usize <= t {
                dp[t] += dp[t - num as usize];
            }
        }
    }
    dp[target] as i32
}

/** LC 377. Target in the OUTER loop counts permutations (orderings differ); coins outside would count combinations. */
export function combinationSum4(nums: number[], target: number): number {
  const dp: number[] = new Array(target + 1).fill(0);
  dp[0] = 1; // one empty sequence
  for (let t = 1; t <= target; t++) {
    for (const num of nums) {
      if (num <= t) dp[t] += dp[t - num]; // any number may finish a sequence summing to t
    }
  }
  return dp[target];
}

// LC 377. Target in the OUTER loop lets every number be the LAST element at
// every total, counting orderings; coins-outer (LC 518) counts combinations.
func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1 // the empty sequence is the one way to make 0
	for t := 1; t <= target; t++ {
		for _, num := range nums {
			if num <= t {
				dp[t] += dp[t-num] // num as the last element
			}
		}
	}
	return dp[target]
}

// LC 377. dp[t] += dp[t - num] with the TARGET in the outer loop: every
// number can be the LAST pick at every total, which counts permutations.
func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
    var dp = [Int](repeating: 0, count: target + 1)
    dp[0] = 1  // the empty sequence is the one way to make 0
    for t in stride(from: 1, through: target, by: 1) {
        for num in nums where num <= t {
            dp[t] += dp[t - num]  // num as the last element
        }
    }
    return dp[target]
}

def num_squares(n: int) -> int:
    """LC 279. Perfect Squares.

    Exactly Coin Change with the perfect squares up to n as the coins:
    fewest[i] is one plus the minimum of fewest[i - s] over every
    square s <= i, with fewest[0] = 0. Every n is reachable (1 is a
    square), so no sentinel translation is needed at the end.
    O(n * sqrt(n)) time, O(n) space.
    """
    squares = [side * side for side in range(1, int(n**0.5) + 1)]
    fewest = [0] + [n + 1] * n
    for i in range(1, n + 1):
        for square in squares:
            if square > i:
                break  # squares ascend, so the rest overshoot too
            fewest[i] = min(fewest[i], fewest[i - square] + 1)
    return fewest[n]

// LC 279. Exactly Coin Change with the perfect squares as the coins: dp[i] is
// 1 plus the minimum of dp[i - s*s] over every square that fits, with
// dp[0] = 0. Every i is reachable (1 is a square), so no sentinel dance is
// needed. O(n sqrt n) time; BFS over amounts, one square per level, works too.
int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int s = 1; s * s <= i; ++s) dp[i] = min(dp[i], 1 + dp[i - s * s]);
    return dp[n];
}

/// LC 279. Coin Change with the perfect squares as the coins: dp[i] = 1 +
/// min(dp[i - s*s]) over every square at most i, dp[0] = 0. Every i is
/// reachable via 1s, so no sentinel bookkeeping is needed. O(n sqrt n).
pub fn num_squares(n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 1..=n {
        let mut s = 1;
        while s * s <= i {
            dp[i] = dp[i].min(dp[i - s * s] + 1);
            s += 1;
        }
    }
    dp[n]
}

/** LC 279. Coin Change with the squares as coins: dp[i] = 1 + min(dp[i - s]) over squares s, O(n sqrt n). */
export function numSquares(n: number): number {
  const dp: number[] = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let root = 1; root * root <= i; root++) {
      dp[i] = Math.min(dp[i], dp[i - root * root] + 1);
    }
  }
  return dp[n]; // always reachable: 1 is a perfect square
}

// LC 279. Exactly Coin Change with the perfect squares as the coins; every n
// is reachable (1 is a square), so no sentinel translation is needed.
func numSquares(n int) int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = n + 1
		for s := 1; s*s <= i; s++ {
			if dp[i-s*s]+1 < dp[i] {
				dp[i] = dp[i-s*s] + 1
			}
		}
	}
	return dp[n]
}

// LC 279. Exactly Coin Change with the perfect squares as coins; every n is
// reachable (1 is a square), so no sentinel translation is needed.
func numSquares(_ n: Int) -> Int {
    var dp = [Int](repeating: n + 1, count: n + 1)
    dp[0] = 0
    for i in stride(from: 1, through: n, by: 1) {
        var side = 1
        while side * side <= i {
            dp[i] = min(dp[i], 1 + dp[i - side * side])
            side += 1
        }
    }
    return dp[n]
}

def integer_break(n: int) -> int:
    """LC 343. Integer Break.

    best_product[i] is the best product over splits of i into at least
    two parts: try every first part j and pair it with the REST either
    kept whole (i - j) or broken further (best_product[i - j]),
    whichever is larger. That max is what handles the pitfall cases --
    2 and 3 must be broken when they ARE n (scoring 1 and 2), yet stay
    whole as parts inside larger numbers. O(n^2) time, O(n) space.
    """
    best_product = [0] * (n + 1)
    best_product[1] = 1
    for i in range(2, n + 1):
        for part in range(1, i):
            # rest may stay whole or break further; whole wins for small rests
            rest = max(i - part, best_product[i - part])
            best_product[i] = max(best_product[i], part * rest)
    return best_product[n]

// LC 343. dp[i] is the best product from splitting i into at least two parts:
// max over the first part j of j times the larger of (i - j) kept whole or
// dp[i - j] split further. Taking max(i - j, dp[i - j]) is what handles the
// pitfall that 2 and 3 must be broken even though keeping them whole scores
// higher. (Closed form: use all 3s, swapping a 4 in for a leftover 1.)
int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j) dp[i] = max(dp[i], j * max(i - j, dp[i - j]));
    return dp[n];
}

/// LC 343. dp[i] = max over first parts j of j * max(i - j, dp[i - j]): the
/// remainder is either kept whole or broken further. The pitfall is the small
/// cases -- 2 and 3 must be broken even though keeping them whole scores
/// higher, which the max(i - j, dp[i - j]) form handles for the larger i that
/// use them as parts.
pub fn integer_break(n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![0; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        for j in 1..i {
            dp[i] = dp[i].max(j as i32 * (i as i32 - j as i32).max(dp[i - j]));
        }
    }
    dp[n]
}

/** LC 343. dp[i] = max over j of j * max(i-j, dp[i-j]): keep the remainder whole or break it further. */
export function integerBreak(n: number): number {
  const dp: number[] = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      // max(i-j, dp[i-j]) lets small pieces stay whole, since 2 and 3 score
      // higher unbroken; only the FULL n is forced into at least two parts
      dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]));
    }
  }
  return dp[n];
}

// LC 343. dp[i] = max over first part j of j * max(i-j, dp[i-j]): the rest may
// stay whole or break further, which handles 2 and 3 having to break as n.
func integerBreak(n int) int {
	dp := make([]int, n+1)
	dp[1] = 1
	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			rest := i - j // the rest kept whole...
			if dp[i-j] > rest {
				rest = dp[i-j] // ...or broken further, whichever is larger
			}
			if j*rest > dp[i] {
				dp[i] = j * rest
			}
		}
	}
	return dp[n]
}

// LC 343. dp[i] = max over first part j of j * max(i - j, dp[i - j]): the
// rest may stay whole or break further, which handles the small-n traps.
func integerBreak(_ n: Int) -> Int {
    var dp = [Int](repeating: 0, count: n + 1)
    dp[1] = 1
    for i in stride(from: 2, through: n, by: 1) {
        for j in 1..<i {
            dp[i] = max(dp[i], j * max(i - j, dp[i - j]))
        }
    }
    return dp[n]
}

def stone_game_iii(stone_value: list[int]) -> str:
    """LC 1406. Stone Game III.

    Suffix dp on the SCORE DIFFERENCE -- the trick that collapses two
    players into one state: best_lead[i] is (mover's score - opponent's
    score) when both play optimally on the suffix starting at i. The
    mover banks 1, 2, or 3 stones and then becomes the opponent of the
    subproblem, so each choice scores taken - best_lead[next]. The sign
    of best_lead[0] names the winner. O(n) time, O(n) space (three
    rolling variables would make it O(1)).
    """
    n = len(stone_value)
    best_lead = [0] * (n + 1)  # best_lead[n] = 0: no stones, no lead
    for i in range(n - 1, -1, -1):
        taken = 0
        best = float("-inf")
        for j in range(i, min(i + 3, n)):  # take stones i..j (1 to 3 of them)
            taken += stone_value[j]
            best = max(best, taken - best_lead[j + 1])  # minus: roles swap
        best_lead[i] = best
    if best_lead[0] > 0:
        return "Alice"
    if best_lead[0] < 0:
        return "Bob"
    return "Tie"

// LC 1406. Suffix dp on the score DIFFERENCE: dp[i] is the best (mover score
// minus opponent score) achievable from suffix i, maximizing over taking 1,
// 2, or 3 stones of their sum minus dp at the next index. Framing the state
// as a difference instead of two totals is the trick; the sign of dp[0]
// decides the winner, with 0 meaning Tie.
string stoneGameIII(vector<int> stoneValue) {
    int n = static_cast<int>(stoneValue.size());
    vector<long long> dp(n + 1, 0);  // dp[n] = 0: no stones left
    for (int i = n - 1; i >= 0; --i) {
        long long taken = 0, best = LLONG_MIN;
        for (int k = 0; k < 3 && i + k < n; ++k) {
            taken += stoneValue[i + k];
            best = max(best, taken - dp[i + k + 1]);
        }
        dp[i] = best;
    }
    if (dp[0] > 0) return "Alice";
    if (dp[0] < 0) return "Bob";
    return "Tie";
}

/// LC 1406. Suffix dp on the score DIFFERENCE -- the trick that avoids
/// tracking two totals: dp[i] is the best (mover - opponent) margin from
/// suffix i, maximizing over taking 1, 2, or 3 stones minus the dp after
/// them. The sign of dp[0] names the winner.
pub fn stone_game_iii(stone_value: Vec<i32>) -> String {
    let n = stone_value.len();
    let mut dp = vec![0; n + 1]; // dp[n] = 0: no stones, no margin
    for i in (0..n).rev() {
        let mut taken = 0;
        let mut best = i32::MIN;
        for k in i..n.min(i + 3) {
            taken += stone_value[k];
            best = best.max(taken - dp[k + 1]);
        }
        dp[i] = best;
    }
    if dp[0] > 0 {
        "Alice".to_string()
    } else if dp[0] < 0 {
        "Bob".to_string()
    } else {
        "Tie".to_string()
    }
}

/** LC 1406. Suffix dp on the score DIFFERENCE: dp[i] = max over taking 1..3 stones of taken - dp[next]; sign of dp[0] decides. */
export function stoneGameIII(stoneValue: number[]): string {
  const n = stoneValue.length;
  const dp: number[] = new Array(n + 1).fill(0); // dp[i] = best (mover - opponent) from suffix i
  for (let i = n - 1; i >= 0; i--) {
    let taken = 0;
    let best = -Infinity;
    for (let k = 0; k < 3 && i + k < n; k++) {
      taken += stoneValue[i + k];
      best = Math.max(best, taken - dp[i + k + 1]); // the opponent moves optimally on the rest
    }
    dp[i] = best;
  }
  if (dp[0] > 0) return "Alice";
  if (dp[0] < 0) return "Bob";
  return "Tie";
}

// LC 1406. Suffix dp on the SCORE DIFFERENCE: dp[i] maximizes taken - dp[next]
// over banking 1..3 stones (roles swap); the sign of dp[0] names the winner.
func stoneGameIII(stoneValue []int) string {
	n := len(stoneValue)
	dp := make([]int, n+1) // dp[n] = 0: no stones, no lead
	for i := n - 1; i >= 0; i-- {
		taken, best := 0, math.MinInt
		for k := 0; k < 3 && i+k < n; k++ {
			taken += stoneValue[i+k]
			if taken-dp[i+k+1] > best {
				best = taken - dp[i+k+1] // minus: roles swap
			}
		}
		dp[i] = best
	}
	if dp[0] > 0 {
		return "Alice"
	}
	if dp[0] < 0 {
		return "Bob"
	}
	return "Tie"
}

// LC 1406. Suffix dp on the score DIFFERENCE: take 1-3 stones, score their
// sum minus dp at the next index (roles swap); the sign of dp[0] names the winner.
func stoneGameIII(_ stoneValue: [Int]) -> String {
    let n = stoneValue.count
    var dp = [Int](repeating: 0, count: n + 1)  // dp[n] = 0: no stones left
    for i in stride(from: n - 1, through: 0, by: -1) {
        var taken = 0, best = Int.min
        var k = 0
        while k < 3 && i + k < n {
            taken += stoneValue[i + k]
            best = max(best, taken - dp[i + k + 1])  // minus: roles swap
            k += 1
        }
        dp[i] = best
    }
    if dp[0] > 0 { return "Alice" }
    if dp[0] < 0 { return "Bob" }
    return "Tie"
}