Dynamic Programming

//   1. STATE      : dp[i] (or dp[i][j]) = answer to the subproblem described by i (and j). Say it in words.//   2. RECURRENCE : dp[i] = f(dp[smaller]). Decide what the LAST choice was.//   3. BASE CASE  : dp[0] / dp[i][0] / dp[0][j].//   4. ORDER      : iterate so dependencies are computed first (i ascending; j inner; or by length for intervals).//   5. ANSWER     : dp[n] or max over dp[]. Then optimize space if dp[i] only needs dp[i-1], dp[i-2].//   Top-down memo  : write the recursion, add a Map/array cache keyed by state. Easiest to get right.//   Bottom-up tab  : loop in dependency order. No recursion depth limit; faster constant.//   Rolling array  : keep only previous row(s): O(n) -> O(1) or O(mn) -> O(n).

function climbStairs(n) {  let a = 1, b = 1; // dp[0], dp[1]  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];  return b;}

function rob(nums) {  let prev2 = 0, prev1 = 0;  for (const x of nums) [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];  return prev1;}

const robCircular = (nums) => nums.length === 1 ? nums[0] : Math.max(rob(nums.slice(1)), rob(nums.slice(0, -1)));

function coinChange(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;  for (let a = 1; a <= amount; a++) for (const c of coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);  return dp[amount] === Infinity ? -1 : dp[amount];}

function change(amount, coins) {  const dp = new Array(amount + 1).fill(0);  dp[0] = 1;  for (const c of coins) for (let a = c; a <= amount; a++) dp[a] += dp[a - c];  return dp[amount];}

function lengthOfLIS(nums) {  const dp = new Array(nums.length).fill(1);  for (let i = 0; i < nums.length; i++) for (let j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);  return nums.length ? Math.max(...dp) : 0;}// Patience sorting / binary search O(n log n): tails[k] = smallest tail of an increasing subsequence of length k+1function lengthOfLISFast(nums) {  const tails = [];  for (const x of nums) {    let lo = 0, hi = tails.length; // lower bound    while (lo < hi) { const m = (lo + hi) >> 1; if (tails[m] < x) lo = m + 1; else hi = m; }    tails[lo] = x;  }  return tails.length;}

function lcs(a, b) {  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));  for (let i = 1; i <= a.length; i++) for (let j = 1; j <= b.length; j++) {    dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);  }  return dp[a.length][b.length];}

function minDistance(a, b) {  const dp = Array.from({ length: a.length + 1 }, (_, i) => [i, ...new Array(b.length).fill(0)]);  for (let j = 0; j <= b.length; j++) dp[0][j] = j;  for (let i = 1; i <= a.length; i++) for (let j = 1; j <= b.length; j++) {    dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);  }  return dp[a.length][b.length];}

function knapsack01(weights, values, W) {  const dp = new Array(W + 1).fill(0);  for (let i = 0; i < weights.length; i++) for (let w = W; w >= weights[i]; w--) dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);  return dp[W];}

function knapsackUnbounded(weights, values, W) {  const dp = new Array(W + 1).fill(0);  for (let w = 1; w <= W; w++) for (let i = 0; i < weights.length; i++) if (weights[i] <= w) dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);  return dp[W];}

function uniquePaths(m, n) {  const row = new Array(n).fill(1);  for (let r = 1; r < m; r++) for (let c = 1; c < n; c++) row[c] += row[c - 1];  return row[n - 1];}

function minPathSum(grid) {  const m = grid.length, n = grid[0].length;  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {    if (r === 0 && c === 0) continue;    const up = r > 0 ? grid[r - 1][c] : Infinity, left = c > 0 ? grid[r][c - 1] : Infinity;    grid[r][c] += Math.min(up, left);  }  return grid[m - 1][n - 1];}

function wordBreak(s, wordDict) {  const dict = new Set(wordDict), dp = new Array(s.length + 1).fill(false);  dp[0] = true;  for (let i = 1; i <= s.length; i++) for (let j = 0; j < i; j++) if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; }  return dp[s.length];}

function canPartition(nums) {  const total = nums.reduce((a, b) => a + b, 0);  if (total % 2) return false;  const target = total / 2, dp = new Array(target + 1).fill(false);  dp[0] = true;  for (const x of nums) for (let s = target; s >= x; s--) dp[s] = dp[s] || dp[s - x];  return dp[target];}

function numDecodings(s) {  if (!s || s[0] === '0') return 0;  let prev2 = 1, prev1 = 1; // dp[0], dp[1]  for (let i = 2; i <= s.length; i++) {    let cur = 0;    if (s[i - 1] !== '0') cur += prev1;    const two = Number(s.slice(i - 2, i));    if (two >= 10 && two <= 26) cur += prev2;    [prev2, prev1] = [prev1, cur];  }  return prev1;}

function maxProduct(nums) {  let best = nums[0], hi = nums[0], lo = nums[0];  for (let i = 1; i < nums.length; i++) {    const x = nums[i];    if (x < 0) [hi, lo] = [lo, hi];    hi = Math.max(x, hi * x); lo = Math.min(x, lo * x);    best = Math.max(best, hi);  }  return best;}

function longestPalindromeSubseq(s) {  const n = s.length, dp = Array.from({ length: n }, () => new Array(n).fill(0));  for (let i = n - 1; i >= 0; i--) { // i descending so dp[i+1][*] is ready    dp[i][i] = 1;    for (let j = i + 1; j < n; j++) dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);  }  return n ? dp[0][n - 1] : 0;}

function maxSubArray(nums) {  let endingHere = nums[0], best = nums[0];  for (let i = 1; i < nums.length; i++) { endingHere = Math.max(nums[i], endingHere + nums[i]); best = Math.max(best, endingHere); }  return best;}