// dp[i] = best answer using nums[i..n-1]
// LC 70 (Climbing Stairs) / LC 198 (House Robber)

function dp1D(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;

  const dp = new Array(n + 2).fill(0); // dp[n], dp[n+1] = 0 — nothing left to take

  for (let i = n - 1; i >= 0; i--) {
    const skip = dp[i + 1];
    const take = nums[i] + dp[i + 2];

    dp[i] = Math.max(skip, take);
  }

  return dp[0];
}
// Time: O(n), Space: O(n) → can reduce to O(1) with rolling variables

// ⭐ SPACE OPTIMIZATION (dp[i] only ever needs dp[i+1] and dp[i+2] — fixed lookback):
function dp1DSpaceOpt(nums: number[]): number {
  let next1 = 0; // dp[i+1]
  let next2 = 0; // dp[i+2]

  for (let i = nums.length - 1; i >= 0; i--) {
    const curr = Math.max(next1, nums[i] + next2);

    next2 = next1;
    next1 = curr;
  }

  return next1;
}

// dfs(i) = best answer using nums[i..n-1]
// LC 70 / LC 198

function dp1D_rec(nums: number[]): number {
  const memo = new Map<number, number>();

  function dfs(i: number): number {
    // base case
    if (i >= nums.length) return 0;

    if (memo.has(i)) return memo.get(i)!;

    const skip = dfs(i + 1);
    const take = nums[i] + dfs(i + 2);

    const res = Math.max(skip, take);
    memo.set(i, res);

    return res;
  }

  return dfs(0);
}

// ⭐ The iterative version rolls to O(1) space (next1/next2). Memoized recursion can't —
// the memo has to keep every subproblem it might still need, so it stays O(n).

// Run §4.1's rolling-variable solver twice, on each of the two sub-ranges
// Time: O(n), Space: O(1) — called TWICE, constant factor doesn't change the order

function rob(nums: number[]): number {
  const n = nums.length;

  if (n === 1) return nums[0];

  function solve(start: number, end: number): number {
    let next1 = 0;
    let next2 = 0;

    for (let i = end; i >= start; i--) {
      const curr = Math.max(next1, nums[i] + next2);

      next2 = next1;
      next1 = curr;
    }

    return next1;
  }

  return Math.max(
    solve(0, n - 2), // exclude last house
    solve(1, n - 1)  // exclude first house
  );
}

// Same idea, top-down: memoize §4.1's dfs(i), run it on each of the two sub-ranges
// Time: O(n), Space: O(n) — memo + recursion stack per solve() call, called TWICE

function rob_rec(nums: number[]): number {
  const n = nums.length;

  if (n === 1) return nums[0];

  function solve(start: number, end: number): number {
    const memo = new Map<number, number>();

    function dfs(idx: number): number {
      // base case
      if (idx > end) return 0;

      if (memo.has(idx)) return memo.get(idx)!;

      const skip = dfs(idx + 1);
      const take = nums[idx] + dfs(idx + 2);

      const res = Math.max(skip, take);
      memo.set(idx, res);

      return res;
    }

    return dfs(start);
  }

  return Math.max(
    solve(0, n - 2), // exclude last house
    solve(1, n - 1)  // exclude first house
  );
}

// dp[i][prev] = LIS achievable from nums[i..] given prev index chosen so far
// LC 300 — Classic, understand BOTH approaches

function lengthOfLIS_DP(nums: number[]): number {
  const n = nums.length;
  let nextRow = new Array(n + 1).fill(0); // base case: i === n

  for (let i = n - 1; i >= 0; i--) {
    const currRow = new Array(n + 1).fill(0);

    for (let prev = 0; prev <= n; prev++) {
      const skip = nextRow[prev];

      let take = 0;
      if (prev === n || nums[i] > nums[prev]) {
        take = 1 + nextRow[i];
      }

      currRow[prev] = Math.max(skip, take);
    }

    nextRow = currRow;
  }

  return nextRow[n];
}
// Time: O(n²), Space: O(n) — dp[i][prev] only ever needs dp[i+1][prev] (same prev,
// row below) and dp[i+1][i] (row below, different column) — never the same row → 2 rows only

// dfs(i, prev) = LIS achievable from nums[i..] given prev index chosen
// LC 300

function lengthOfLIS_rec(nums: number[]): number {
  const n = nums.length;
  const memo: (number | null)[][] = Array.from({ length: n }, () => new Array(n + 1).fill(null));

  function dfs(i: number, prev: number): number {
    // base case
    if (i === n) return 0;

    if (memo[i][prev] !== null) return memo[i][prev];

    const skip = dfs(i + 1, prev);

    let take = 0;
    if (prev === n || nums[i] > nums[prev]) {
      take = 1 + dfs(i + 1, i);
    }

    const res = Math.max(skip, take);
    memo[i][prev] = res;

    return res;
  }

  return dfs(0, n);
}
// Time: O(n²) — n × (n+1) distinct (i,prev) states, each computed once
// Space: O(n²) memo + O(n) recursion stack

// LC 1235 — the canonical "DP + binary search on sorted structure" problem
// Time: O(n log n) [sort + n states × O(log n)], Space: O(n)

function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
  const n = startTime.length;
  const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);

  jobs.sort((a, b) => a[0] - b[0]);

  function findNextJob(i: number): number {
    let lo = i + 1, hi = n;

    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      // next job's start >= this job's end → compatible
      if (jobs[mid][0] >= jobs[i][1]) hi = mid;
      else lo = mid + 1;
    }

    return lo;
  }

  const dp = Array(n + 1).fill(0);

  for (let i = n - 1; i >= 0; i--) {
    const skip = dp[i + 1];
    const nextJobIdx = findNextJob(i);
    const take = jobs[i][2] + dp[nextJobIdx];

    dp[i] = Math.max(skip, take);
  }

  return dp[0];
}
// KEY: sort by START time so findNextJob's binary search has a clean
// "first index ≥ target" (lower_bound) shape.

// dfs(i) = max profit from jobs[i..n-1]
// Time: O(n log n) [n states × O(log n) findNextJob], Space: O(n) memo + recursion stack

function jobScheduling_rec(startTime: number[], endTime: number[], profit: number[]): number {
  const n = startTime.length;
  const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);

  jobs.sort((a, b) => a[0] - b[0]);

  function findNextJob(i: number): number {
    let lo = i + 1, hi = n;

    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (jobs[mid][0] >= jobs[i][1]) hi = mid;
      else lo = mid + 1;
    }

    return lo;
  }

  const memo = new Map<number, number>();

  function dfs(i: number): number {
    // base case
    if (i === n) return 0;

    if (memo.has(i)) return memo.get(i)!;

    const skip = dfs(i + 1);
    const nextJobIdx = findNextJob(i);
    const take = jobs[i][2] + dfs(nextJobIdx);

    const res = Math.max(skip, take);
    memo.set(i, res);

    return res;
  }

  return dfs(0);
}
// Plain recursion (no memo) would be O(2^n · log n) — 2 choices/call × O(log n) findNextJob work

// dp[i] = max sum subarray ENDING at i
// LC 53, 918 (circular version)
// Time: O(n), Space: O(1) — already rolling, only one prior value needed

function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let curr = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const startFresh = nums[i];
    const extend = curr + nums[i];

    curr = Math.max(startFresh, extend);
    maxSum = Math.max(maxSum, curr);
  }

  return maxSum;
}

// ⭐ TRAP: LC 918 (Maximum Sum Circular Subarray)
// Answer = max(normal Kadane, totalSum - min subarray)
// Edge case: if all numbers are negative, min subarray = whole array → return normal Kadane

// dfs(i) = max subarray sum ENDING exactly at i (looks back to i-1)
// Kadane's own derivation IS this recursion — backward suits it better than forward here
// Time: O(n) — n distinct states, cached. Space: O(n) — memo + recursion stack

function maxSubArray_rec(nums: number[]): number {
  const n = nums.length;
  const memo: number[] = new Array(n).fill(NaN);

  function dfs(i: number): number {
    // base case
    if (i === 0) return nums[0];

    if (!Number.isNaN(memo[i])) return memo[i];

    const startFresh = nums[i];
    const extend = nums[i] + dfs(i - 1);

    const res = Math.max(startFresh, extend);
    memo[i] = res;

    return res;
  }

  let best = -Infinity;
  for (let i = 0; i < n; i++) best = Math.max(best, dfs(i));
  return best;
}

// dp tracks BOTH max and min product ending at i.
// WHY min: a negative number flips min→max. The most-negative product can
// become the largest the moment we multiply by another negative.
// LC 152 — the two-variable trick is the whole point.
// Time: O(n), Space: O(1)

function maxProduct(nums: number[]): number {
  let result = nums[0];
  let curMax = nums[0]; // max product ending at i
  let curMin = nums[0]; // min product ending at i (could flip to max)

  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    // ⭐ snapshot both BEFORE overwriting — curMax is used to compute curMin
    const cand1 = curMax * n;
    const cand2 = curMin * n;

    curMax = Math.max(n, cand1, cand2); // start fresh at n, or extend
    curMin = Math.min(n, cand1, cand2);

    result = Math.max(result, curMax);
  }

  return result;
}
// TRAP: don't update curMax then use the NEW curMax for curMin — snapshot first.
// SDE3 SIGNAL: "Unlike sum, product isn't monotonic under sign, so I carry the
// running minimum to capture negative-times-negative comebacks."

// dfs(i) = [max, min] product PAIR ending exactly at i — same backward shape as Kadane,
// but the memo stores a pair since either half of the pair can become the answer next step
// Time: O(n), Space: O(n) — memo + recursion stack

function maxProduct_rec(nums: number[]): number {
  const n = nums.length;
  const memo = new Map<number, [number, number]>();

  function dfs(i: number): [number, number] {
    // base case
    if (i === 0) return [nums[0], nums[0]];

    if (memo.has(i)) return memo.get(i)!;

    const [prevMax, prevMin] = dfs(i - 1);
    const ni = nums[i];
    const cand1 = prevMax * ni;
    const cand2 = prevMin * ni;

    const res: [number, number] = [Math.max(ni, cand1, cand2), Math.min(ni, cand1, cand2)];
    memo.set(i, res);

    return res;
  }

  let best = -Infinity;
  for (let i = 0; i < n; i++) best = Math.max(best, dfs(i)[0]);
  return best;
}

// dp[start] = can s[start..n] be segmented using wordDict?
// LC 139

function wordBreak(s: string, wordDict: string[]): boolean {
  const n = s.length;
  const wordSet = new Set(wordDict);

  const dp: boolean[] = Array(n + 1).fill(false);
  dp[n] = true; // base case: reached the end cleanly

  for (let start = n - 1; start >= 0; start--) {
    for (let end = start + 1; end <= n; end++) {
      const seg = s.slice(start, end);

      if (wordSet.has(seg) && dp[end]) {
        dp[start] = true;
        break; // one valid split is enough
      }
    }
  }

  return dp[0];
}
// Time: O(n² · L) where L = avg slice length, Space: O(n)
// SDE3: precompute max word length to prune the inner loop: end <= start + maxLen

// dfs(start) = can s[start..n] be segmented? Try every dictionary word starting at start
// LC 139

function wordBreak_rec(s: string, wordDict: string[]): boolean {
  const n = s.length;
  const wordSet = new Set(wordDict);
  const memo: (boolean | null)[] = Array(n).fill(null);

  function dfs(start: number): boolean {
    // base case
    if (start === n) return true;

    if (memo[start] !== null) return memo[start];

    for (let end = start + 1; end <= n; end++) {
      const seg = s.slice(start, end);

      if (wordSet.has(seg) && dfs(end)) {
        memo[start] = true;
        return true;
      }
    }

    memo[start] = false;
    return false;
  }

  return dfs(0);
}

// dp[i] = number of ways to decode s[i..n-1]
// LC 91 — Hard due to '0' handling

function numDecodings_DP(s: string): number {
  const n = s.length;
  const dp: number[] = new Array(n + 1).fill(0);
  dp[n] = 1; // base case: reached the end cleanly

  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === "0") { dp[i] = 0; continue; } // lone '0' — no valid decode from here

    dp[i] = dp[i + 1]; // take 1 digit

    if (i + 1 < n) {
      const twoDigit = Number(s.slice(i, i + 2));
      if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i + 2]; // take 2 digits
    }
  }

  return dp[0];
}
// Time: O(n), Space: O(n)

// ⭐ SPACE OPTIMIZATION (dp[i] only ever needs dp[i+1] and dp[i+2] — fixed lookback):
function numDecodings(s: string): number {
  const n = s.length;
  let next1 = 1; // dp[i+1]
  let next2 = 0; // dp[i+2]

  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === "0") {
      next2 = next1;
      next1 = 0;
      continue;
    }

    const oneDigit = next1;
    let twoDigit = 0;
    if (i + 1 < n) {
      const num = Number(s.slice(i, i + 2));
      if (num >= 10 && num <= 26) twoDigit = next2;
    }

    const curr = oneDigit + twoDigit;
    next2 = next1;
    next1 = curr;
  }

  return next1;
}
// Time: O(n), Space: O(1)
// TRAP: '0' cannot be decoded alone — always check before adding dp[i+1] / next1.

// dfs(i) = number of ways to decode s[i..n-1]
// LC 91

function numDecodings_rec(s: string): number {
  const n = s.length;
  const memo: (number | null)[] = new Array(n).fill(null);

  function dfs(i: number): number {
    // base case
    if (i === n) return 1; // successfully decoded
    if (s[i] === "0") return 0;

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

    const oneDigit = dfs(i + 1);

    let twoDigit = 0;
    if (i + 1 < n) {
      const num = Number(s.slice(i, i + 2));
      if (num >= 10 && num <= 26) twoDigit = dfs(i + 2);
    }

    const res = oneDigit + twoDigit;
    memo[i] = res;

    return res;
  }

  return dfs(0);
}

// dp[i][j] = min possible maximum sum when splitting nums[0..i-1] into j parts
// LC 410 — Split Array Largest Sum (partition into k parts, minimize max sum)
// Time: O(n²k), Space: O(nk)

function splitArray(nums: number[], k: number): number {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    new Array(k + 1).fill(Infinity)
  );
  dp[0][0] = 0;

  for (let j = 1; j <= k; j++) {
    for (let i = j; i <= n; i++) {
      // last group is nums[m..i-1], previous groups cover nums[0..m-1] — try every split point m
      for (let m = j - 1; m < i; m++) {
        const lastGroupSum = prefix[i] - prefix[m];
        dp[i][j] = Math.min(dp[i][j], Math.max(dp[m][j - 1], lastGroupSum));
      }
    }
  }

  return dp[n][k];
}
// ⭐ ALTERNATIVE: binary search on the answer + greedy feasibility check → O(n log(sum)).
// For interviews: mention both, implement whichever is easier to explain out loud.

// LC 1043 — Partition Array for Maximum Sum: after partitioning, every element in a
// subarray becomes that subarray's max. dp[i] = max sum for arr[0..i-1].
// Time: O(n*k), Space: O(n)

function maxSumAfterPartitioning(arr: number[], k: number): number {
  const n = arr.length;
  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    let maxVal = 0;

    // fix the group's right endpoint at i, try every length 1..k
    for (let len = 1; len <= k && i - len >= 0; len++) {
      maxVal = Math.max(maxVal, arr[i - len]);
      dp[i] = Math.max(dp[i], dp[i - len] + maxVal * len);
    }
  }

  return dp[n];
}

// dfs(i, j) = min largest-sum splitting nums[i..n-1] into j groups
// Peels the FIRST group off the front — mirror of the bottom-up prefix table. LC 410
// Time: O(n²k) distinct (i,j) states × O(n) inner scan. Space: O(nk) memo + O(k) stack

function splitArray_rec(nums: number[], k: number): number {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

  const rangeSum = (i: number, j: number) => prefix[j] - prefix[i];
  const memo = new Map<string, number>();

  function dfs(i: number, j: number): number {
    // base case
    if (j === 1) return rangeSum(i, n);

    const key = i + "," + j;
    if (memo.has(key)) return memo.get(key)!;

    let best = Infinity;
    for (let m = i + 1; m <= n - (j - 1); m++) {
      // first group is nums[i..m-1], recurse on the rest with one fewer group
      best = Math.min(best, Math.max(rangeSum(i, m), dfs(m, j - 1)));
    }

    memo.set(key, best);
    return best;
  }

  return dfs(0, k);
}

// dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
// LC 1143 — Foundation for many other problems

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length,
    n = text2.length;
  // ⭐ Allocate (m+1) x (n+1) for clean base cases
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0),
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // characters match: extend
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // skip one char
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n) → reducible to O(min(m,n)) with rolling row

// ⭐ LCS Space Optimization (two-row rolling):
function lcsSpaceOpt(text1: string, text2: string): number {
  const m = text1.length,
    n = text2.length;
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) curr[j] = prev[j - 1] + 1;
      else curr[j] = Math.max(prev[j], curr[j - 1]);
    }
    [prev, curr] = [curr, prev]; // swap references
    curr.fill(0);
  }

  return prev[n];
}

// TOP-DOWN — rec(i, j) = LCS of text1[i..m-1] and text2[j..n-1] (walk both strings left→right)
// LC 1143

function longestCommonSubsequence_rec(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(-1));
  function rec(i: number, j: number): number {
    if (i === m || j === n) return 0;
    if (memo[i][j] !== -1) return memo[i][j];
    let res: number;
    if (text1[i] === text2[j]) res = 1 + rec(i + 1, j + 1);
    else res = Math.max(rec(i + 1, j), rec(i, j + 1));
    return (memo[i][j] = res);
  }
  return rec(0, 0);
}

// ⭐ Note: the iterative version rolls to a 2-row table. The memo here needs the full m×n grid —
// same space trade-off as 4.1: recursion can't roll away rows it might still need to revisit.

// dp[i][j] = min ops to convert word1[0..i-1] to word2[0..j-1]
// LC 72 — Three operations: insert, delete, replace

function minDistance(word1: string, word2: string): number {
  const m = word1.length,
    n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0),
  );

  // Base cases: converting to/from empty string
  for (let i = 0; i <= m; i++) dp[i][0] = i; // delete all
  for (let j = 0; j <= n; j++) dp[0][j] = j; // insert all

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // no op needed
      } else {
        dp[i][j] =
          1 +
          Math.min(
            dp[i - 1][j], // delete from word1
            dp[i][j - 1], // insert into word1
            dp[i - 1][j - 1], // replace
          );
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

// TOP-DOWN — rec(i, j) = edit distance between word1[i..m-1] and word2[j..n-1]
// LC 72

function minDistance_rec(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const memo: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
  function rec(i: number, j: number): number {
    if (i === m) return n - j;
    if (j === n) return m - i;
    if (memo[i][j] !== -1) return memo[i][j];
    let res: number;
    if (word1[i] === word2[j]) res = rec(i + 1, j + 1);
    else res = 1 + Math.min(rec(i + 1, j), rec(i, j + 1), rec(i + 1, j + 1));
    return (memo[i][j] = res);
  }
  return rec(0, 0);
}

// dp[i][j] = number of unique paths to reach (i,j) from (0,0)
// LC 62, 63 (with obstacles)

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(1));
  // First row and column are all 1 (only one way to move along an edge)

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // from top + from left
    }
  }

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

// LC 63 — With obstacles:
function uniquePathsWithObstacles(grid: number[][]): number {
  const m = grid.length,
    n = grid[0].length;
  if (grid[0][0] === 1 || grid[m - 1][n - 1] === 1) return 0;

  const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = 1;

  // Fill first row
  for (let j = 1; j < n; j++) dp[0][j] = grid[0][j] === 1 ? 0 : dp[0][j - 1];
  // Fill first col
  for (let i = 1; i < m; i++) dp[i][0] = grid[i][0] === 1 ? 0 : dp[i - 1][0];

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = grid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
    }
  }

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

// TOP-DOWN — rec(i, j) = # paths from (i, j) to the bottom-right corner (only right/down remain)
// LC 62 — same idea extends to the obstacle grid (LC 63): return 0 the moment a cell is blocked

function uniquePaths_rec(m: number, n: number): number {
  const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(-1));
  function rec(i: number, j: number): number {
    if (i === m - 1 || j === n - 1) return 1;
    if (memo[i][j] !== -1) return memo[i][j];
    return (memo[i][j] = rec(i + 1, j) + rec(i, j + 1));
  }
  return rec(0, 0);
}

// dp[i][j] = # of times s[0..j-1] appears as subseq in t[0..i-1]
// LC 115 — Tricky recurrence

function numDistinct(s: string, t: string): number {
  const m = s.length,
    n = t.length;
  // dp[i][j]: ways to form t[0..j-1] from s[0..i-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0),
  );

  // Empty t can always be formed (by taking 0 chars)
  for (let i = 0; i <= m; i++) dp[i][0] = 1;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j]; // always: skip s[i-1]
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] += dp[i - 1][j - 1]; // use s[i-1] to match t[j-1]
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)
// TRAP: Initialize dp[i][0] = 1 for all i. Never dp[0][j>0] = 1.

// TOP-DOWN — rec(i, j) = ways to form t[j..n-1] as a subsequence of s[i..m-1]
// LC 115

function numDistinct_rec(s: string, t: string): number {
  const m = s.length, n = t.length;
  const memo: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
  function rec(i: number, j: number): number {
    if (j === n) return 1;
    if (i === m) return 0;
    if (memo[i][j] !== -1) return memo[i][j];
    let res = rec(i + 1, j);
    if (s[i] === t[j]) res += rec(i + 1, j + 1);
    return (memo[i][j] = res);
  }
  return rec(0, 0);
}

// dp[i][j] = side length of largest all-1 square with bottom-right corner at (i,j)
// LC 221 — Beautiful DP insight

function maximalSquare(matrix: string[][]): number {
  const m = matrix.length,
    n = matrix[0].length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0),
  );
  let maxSide = 0;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1][j - 1] === "1") {
        // Bottleneck = smallest of the three neighbors
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
        maxSide = Math.max(maxSide, dp[i][j]);
      }
    }
  }

  return maxSide * maxSide; // area = side²
}
// Time: O(m*n), Space: O(m*n)
// ⭐ The recurrence min(top, left, top-left) + 1 is the key insight.
// Visualize: you can only extend a square if all three neighbors are squares.

// TOP-DOWN — rec(i, j) = side of the largest all-1 square with its TOP-LEFT corner at (i, j)
// Mirror image of the bottom-right recurrence: same min(...)+1 identity, reflected. LC 221

function maximalSquare_rec(matrix: string[][]): number {
  const m = matrix.length, n = matrix[0].length;
  const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(-1));
  function rec(i: number, j: number): number {
    if (i >= m || j >= n || matrix[i][j] === "0") return 0;
    if (memo[i][j] !== -1) return memo[i][j];
    const side = 1 + Math.min(rec(i + 1, j), rec(i, j + 1), rec(i + 1, j + 1));
    return (memo[i][j] = side);
  }
  let maxSide = 0;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) maxSide = Math.max(maxSide, rec(i, j));
  return maxSide * maxSide;
}

// dp[i][j] = max coins from bursting ALL balloons between i and j (exclusive)
// LC 312 — Think "what is the LAST balloon to burst?"

function maxCoins(nums: number[]): number {
  // Add sentinel balloons at boundaries (value 1)
  const arr = [1, ...nums, 1];
  const n = arr.length;
  // dp[i][j] = max coins from open interval (i, j), bursting all inside
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

  // Fill by increasing length of interval
  for (let len = 2; len < n; len++) {
    // len = gap between endpoints
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      for (let k = i + 1; k < j; k++) {
        // k = LAST balloon to burst in (i,j)
        dp[i][j] = Math.max(
          dp[i][j],
          arr[i] * arr[k] * arr[j] + dp[i][k] + dp[k][j],
        );
      }
    }
  }

  return dp[0][n - 1];
}
// Time: O(n³), Space: O(n²)
// KEY INSIGHT: By choosing k as the LAST to burst (not first), i and j are
// still present when k bursts, making arr[i]*arr[k]*arr[j] correct.

// TOP-DOWN — rec(i, j) = max coins bursting everything strictly between i and j
// Interval DP has no forward/backward axis — recursion picks the LAST balloon to burst,
// same choice the bottom-up fill makes by increasing interval length. LC 312

function maxCoins_rec(nums: number[]): number {
  const arr = [1, ...nums, 1];
  const n = arr.length;
  const memo: number[][] = Array.from({ length: n }, () => new Array(n).fill(-1));
  function rec(i: number, j: number): number {
    if (j - i < 2) return 0;
    if (memo[i][j] !== -1) return memo[i][j];
    let best = 0;
    for (let k = i + 1; k < j; k++) {
      best = Math.max(best, arr[i] * arr[k] * arr[j] + rec(i, k) + rec(k, j));
    }
    return (memo[i][j] = best);
  }
  return rec(0, n - 1);
}

// dp[i][j] = length of LPS in s[i..j]
// LC 516

function longestPalindromeSubseq(s: string): number {
  const n = s.length;
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

  // Base case: single characters are palindromes of length 1
  for (let i = 0; i < n; i++) dp[i][i] = 1;

  // Fill for increasing lengths
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = (len === 2 ? 0 : dp[i + 1][j - 1]) + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[0][n - 1];
}
// Time: O(n²), Space: O(n²)
// RELATIONSHIP: LPS(s) = LCS(s, reverse(s))
// For min insertions to make palindrome: n - LPS(s)  (LC 1312)

// TOP-DOWN — rec(i, j) = LPS length within s[i..j], shrinking inward from both ends
// LC 516

function longestPalindromeSubseq_rec(s: string): number {
  const n = s.length;
  const memo: number[][] = Array.from({ length: n }, () => new Array(n).fill(-1));
  function rec(i: number, j: number): number {
    if (i > j) return 0;
    if (i === j) return 1;
    if (memo[i][j] !== -1) return memo[i][j];
    let res: number;
    if (s[i] === s[j]) res = 2 + rec(i + 1, j - 1);
    else res = Math.max(rec(i + 1, j), rec(i, j - 1));
    return (memo[i][j] = res);
  }
  return rec(0, n - 1);
}

// cuts[i] = min cuts for s[0..i]
// LC 132 — Combine palindrome check with 1D DP

function minCut(s: string): number {
  const n = s.length;
  // Precompute isPalin[i][j] using DP (expand around center)
  const isPalin: boolean[][] = Array.from({ length: n }, () =>
    new Array(n).fill(false),
  );
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      isPalin[i][j] = s[i] === s[j] && (j - i <= 2 || isPalin[i + 1][j - 1]);
    }
  }

  // cuts[i] = min cuts for s[0..i]
  const cuts = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    if (isPalin[0][i]) {
      cuts[i] = 0;
      continue;
    } // whole prefix is palindrome
    cuts[i] = i; // worst case: cut after every character
    for (let j = 1; j <= i; j++) {
      if (isPalin[j][i]) {
        cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
      }
    }
  }

  return cuts[n - 1];
}
// Time: O(n²), Space: O(n²) for isPalin precomputation

// TOP-DOWN — rec(i) = min cuts for s[i..n-1]; peels the FIRST palindrome piece off the front
// Sentinel rec(n) = -1 lets a whole-suffix palindrome cost exactly 0 cuts (1 + -1). LC 132

function minCut_rec(s: string): number {
  const n = s.length;
  const isPalin: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--)
    for (let j = i; j < n; j++)
      isPalin[i][j] = s[i] === s[j] && (j - i <= 2 || isPalin[i + 1][j - 1]);
  const memo = new Array(n).fill(-2);
  function rec(i: number): number {
    if (i === n) return -1;
    if (memo[i] !== -2) return memo[i];
    let best = Infinity;
    for (let j = i; j < n; j++) {
      if (isPalin[i][j]) best = Math.min(best, 1 + rec(j + 1));
    }
    return (memo[i] = best);
  }
  return rec(0);
}

// dp[i][j] = does p[0..j-1] match s[0..i-1]?
// LC 10 (regex: . and *) — The hardest string DP

function isMatch_regex(s: string, p: string): boolean {
  const m = s.length,
    n = p.length;
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true;

  // Handle patterns like a*, a*b*, a*b*c* matching empty string
  for (let j = 2; j <= n; j++) {
    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] === "*") {
        // '*' matches zero of preceding char: dp[i][j-2]
        // '*' matches one more: dp[i-1][j] if p[j-2] matches s[i-1]
        dp[i][j] =
          dp[i][j - 2] ||
          (dp[i - 1][j] && (p[j - 2] === "." || p[j - 2] === s[i - 1]));
      } else if (p[j - 1] === "." || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // direct match
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

// LC 44 (wildcard: ? and *) — same table shape, DIFFERENT semantics for '*':
// regex '*' means "zero or more of the PRECEDING char" (always paired: a*, .*).
// wildcard '*' is its OWN token meaning "zero or more of ANY chars" — no pairing.
function isMatch_wildcard(s: string, p: string): boolean {
  const m = s.length,
    n = p.length;
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === "*") dp[0][j] = dp[0][j - 1]; // '*' alone can match empty
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        // '*' matches EMPTY here: dp[i][j-1]   OR   consumes s[i-1]: dp[i-1][j]
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (p[j - 1] === "?" || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

// TOP-DOWN — rec(i, j) = does s[i..m-1] match p[j..n-1]? Consume both strings left→right
// LC 10 — the '*' lookahead (p[j+1]) is the only tricky part; same logic as the table, just recursive

function isMatch_regex_rec(s: string, p: string): boolean {
  const m = s.length, n = p.length;
  const memo = new Map<string, boolean>();
  function rec(i: number, j: number): boolean {
    if (j === n) return i === m;
    const key = i + "," + j;
    if (memo.has(key)) return memo.get(key)!;
    const firstMatch = i < m && (p[j] === "." || p[j] === s[i]);
    let res: boolean;
    if (j + 1 < n && p[j + 1] === "*") {
      res = rec(i, j + 2) || (firstMatch && rec(i + 1, j));
    } else {
      res = firstMatch && rec(i + 1, j + 1);
    }
    memo.set(key, res);
    return res;
  }
  return rec(0, 0);
}

// dp[i][j] = can s3[0..i+j-1] be formed by interleaving s1[0..i-1] and s2[0..j-1]?
// LC 97

function isInterleave(s1: string, s2: string, s3: string): boolean {
  const m = s1.length,
    n = s2.length;
  if (m + n !== s3.length) return false;

  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true;

  for (let i = 1; i <= m; i++)
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  for (let j = 1; j <= n; j++)
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] =
        (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
        (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }

  return dp[m][n];
}

// TOP-DOWN — rec(i, j) = can s1[i..], s2[j..] interleave to form the rest of s3?
// LC 97

function isInterleave_rec(s1: string, s2: string, s3: string): boolean {
  const m = s1.length, n = s2.length;
  if (m + n !== s3.length) return false;
  const memo: (boolean | undefined)[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(undefined));
  function rec(i: number, j: number): boolean {
    if (i === m && j === n) return true;
    if (memo[i][j] !== undefined) return memo[i][j]!;
    const k = i + j;
    let res = false;
    if (i < m && s1[i] === s3[k]) res = rec(i + 1, j);
    if (!res && j < n && s2[j] === s3[k]) res = rec(i, j + 1);
    return (memo[i][j] = res);
  }
  return rec(0, 0);
}

// Each item used at most once. Maximize value subject to weight capacity.
// Foundation for LC 416, 494, 1049

function knapsack01(
  weights: number[],
  values: number[],
  capacity: number,
): number {
  const n = weights.length;
  // dp[w] = max value using capacity w
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // ⭐ CRITICAL: Traverse RIGHT TO LEFT to avoid using item i twice
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}
// Time: O(n * capacity), Space: O(capacity)
// WHY RIGHT TO LEFT: If we go left-to-right, dp[w - weights[i]] might already
// reflect item i being used, causing it to be used multiple times.

// TOP-DOWN — rec(i, w) = max value using items[i..n-1] with remaining capacity w
// ⭐ The (item, capacity) state means no "traverse right-to-left" trick is needed here — each
// item's OWN recursive call already fixes whether it was taken, so it can never be reused.

function knapsack01_rec(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const memo: number[][] = Array.from({ length: n }, () => new Array(capacity + 1).fill(-1));
  function rec(i: number, w: number): number {
    if (i === n) return 0;
    if (memo[i][w] !== -1) return memo[i][w];
    let res = rec(i + 1, w);
    if (weights[i] <= w) res = Math.max(res, values[i] + rec(i + 1, w - weights[i]));
    return (memo[i][w] = res);
  }
  return rec(0, capacity);
}

// dp[w] = can we achieve sum w using a subset?
// LC 416

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 dp = new Array(target + 1).fill(false);
  dp[0] = true; // empty subset sums to 0

  for (const num of nums) {
    for (let w = target; w >= num; w--) {
      // Right to left!
      dp[w] = dp[w] || dp[w - num];
    }
  }

  return dp[target];
}
// Time: O(n * target), Space: O(target)

// TOP-DOWN — rec(i, w) = can nums[i..n-1] form exactly sum w?
// LC 416 — same item-index trick as 8.1: no ordering gotcha to remember

function canPartition_rec(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const n = nums.length;
  const memo: (boolean | undefined)[][] = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(undefined));
  function rec(i: number, w: number): boolean {
    if (w === 0) return true;
    if (i === n) return false;
    if (memo[i][w] !== undefined) return memo[i][w]!;
    let res = rec(i + 1, w);
    if (!res && nums[i] <= w) res = rec(i + 1, w - nums[i]);
    return (memo[i][w] = res);
  }
  return rec(0, target);
}

// Count # subsets that sum to target
// LC 494 (with +/- signs)

function findTargetSumWays(nums: number[], target: number): number {
  // Let P = set of positives, N = set of negatives
  // P - N = target, P + N = total → P = (total + target) / 2
  // Count subsets summing to (total + target) / 2
  const total = nums.reduce((a, b) => a + b, 0);
  if ((total + target) % 2 !== 0 || Math.abs(target) > total) return 0;
  const sum = (total + target) / 2;

  const dp = new Array(sum + 1).fill(0);
  dp[0] = 1; // one way to reach sum 0: take nothing

  for (const num of nums) {
    for (let w = sum; w >= num; w--) {
      // Right to left!
      dp[w] += dp[w - num];
    }
  }

  return dp[sum];
}
// Time: O(n * sum), Space: O(sum)
// ⭐ TRANSFORMATION TRICK: Convert +/- problem to subset sum by algebra.

// TOP-DOWN — rec(i, remaining) = ways to assign +/- to nums[i..n-1] so they sum to `remaining`
// ⭐ DIRECT: recursion needs no subset-sum algebra transform — it just branches +nums[i] / -nums[i]

function findTargetSumWays_rec(nums: number[], target: number): number {
  const n = nums.length;
  const memo = new Map<string, number>();
  function rec(i: number, remaining: number): number {
    if (i === n) return remaining === 0 ? 1 : 0;
    const key = i + "," + remaining;
    if (memo.has(key)) return memo.get(key)!;
    const res = rec(i + 1, remaining - nums[i]) + rec(i + 1, remaining + nums[i]);
    memo.set(key, res);
    return res;
  }
  return rec(0, target);
}

// Each coin can be used unlimited times. Minimize # coins.
// LC 322

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let w = 1; w <= amount; w++) {
    for (const coin of coins) {
      if (coin <= w && dp[w - coin] !== Infinity) {
        dp[w] = Math.min(dp[w], dp[w - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Time: O(amount * #coins), Space: O(amount)
// ⭐ UNBOUNDED: Traverse LEFT TO RIGHT (item can be reused)
// vs 0/1 Knapsack: RIGHT TO LEFT (each item once)

// TOP-DOWN — rec(rem) = min coins to make exactly `rem`
// Unbounded: no item index needed at all — any coin can repeat, so `rem` alone is the whole state

function coinChange_rec(coins: number[], amount: number): number {
  const memo = new Array(amount + 1).fill(-2);
  function rec(rem: number): number {
    if (rem === 0) return 0;
    if (rem < 0) return Infinity;
    if (memo[rem] !== -2) return memo[rem];
    let best = Infinity;
    for (const coin of coins) best = Math.min(best, 1 + rec(rem - coin));
    return (memo[rem] = best);
  }
  const ans = rec(amount);
  return ans === Infinity ? -1 : ans;
}

// Count # ways to make amount using coins (unlimited each). Order doesn't matter.
// LC 518

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;

  // ⭐ OUTER LOOP = coins, INNER LOOP = amounts
  // This ensures combinations (not permutations) — each coin subset counted once
  for (const coin of coins) {
    for (let w = coin; w <= amount; w++) {
      dp[w] += dp[w - coin];
    }
  }

  return dp[amount];
}
// Time: O(amount * #coins), Space: O(amount)

// COMPARISON:
// Outer=coins, Inner=amounts → COMBINATIONS (each subset once)    ← Coin Change II
// Outer=amounts, Inner=coins → PERMUTATIONS (order matters)       ← Climbing Stairs style

// TOP-DOWN — rec(i, rem) = ways to make `rem` using coins[i..n-1], each coin reusable
// ⭐ Coin index only ever moves i→i+1 (never back) — THAT is what forces combinations, not
// permutations. The recursive mirror of the bottom-up "outer loop = coins" ordering trick.

function change_rec(amount: number, coins: number[]): number {
  const n = coins.length;
  const memo: number[][] = Array.from({ length: n }, () => new Array(amount + 1).fill(-1));
  function rec(i: number, rem: number): number {
    if (rem === 0) return 1;
    if (i === n) return 0;
    if (memo[i][rem] !== -1) return memo[i][rem];
    let ways = rec(i + 1, rem);
    if (coins[i] <= rem) ways += rec(i, rem - coins[i]);
    return (memo[i][rem] = ways);
  }
  return rec(0, amount);
}