// ─────────────────────────────────────────────────────────────────────────────
// DYNAMIC PROGRAMMING
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : solve overlapping subproblems once; combine via a recurrence over optimal substructure.
// TELL   : "number of ways", "minimum cost / maximum value", "longest ... subsequence", "can you reach /
//          partition", "edit", "knapsack / capacity", "grid paths". Brute force is exponential.
// SAY    : state, recurrence (transition), base case, memoization (top-down), tabulation (bottom-up),
//          space-optimized / rolling array, 1-D DP, 2-D grid DP, knapsack DP, sequence/string DP, interval DP.
// BIG-O  : (number of states) x (work per transition). Space = states, often reducible by one dimension.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── TEMPLATE
//   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).

// ── 1. [1-D] Climbing stairs / Fibonacci  —  dp[i] = dp[i-1] + dp[i-2]; rolling two vars  —  O(n) / O(1)
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;
}
assert.equal(climbStairs(2), 2);
assert.equal(climbStairs(5), 8);
assert.equal(climbStairs(0), 1);

// ── 2. [1-D] House robber I  —  dp[i] = max(dp[i-1], dp[i-2] + nums[i])  —  O(n) / O(1)
function rob(nums) {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];
  return prev1;
}
assert.equal(rob([2, 7, 9, 3, 1]), 12);
assert.equal(rob([1]), 1);
assert.equal(rob([]), 0);

// ── 3. [1-D] House robber II (circular)  —  max(rob(without first), rob(without last))  —  O(n) / O(1)
const robCircular = (nums) => nums.length === 1 ? nums[0] : Math.max(rob(nums.slice(1)), rob(nums.slice(0, -1)));
assert.equal(robCircular([2, 3, 2]), 3);
assert.equal(robCircular([1, 2, 3, 1]), 4);
assert.equal(robCircular([5]), 5);

// ── 4. [knapsack, unbounded, min] Coin change (fewest coins)  —  dp[a] = min(dp[a - c] + 1)  —  O(amount * coins) / O(amount)
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];
}
assert.equal(coinChange([1, 2, 5], 11), 3);
assert.equal(coinChange([2], 3), -1);
assert.equal(coinChange([1], 0), 0);

// ── 5. [knapsack, unbounded, count] Coin change II (number of combinations)  —  coins OUTER loop to avoid counting permutations  —  O(amount * coins)
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];
}
assert.equal(change(5, [1, 2, 5]), 4);
assert.equal(change(3, [2]), 0);
assert.equal(change(0, [7]), 1);

// ── 6. [sequence] Longest increasing subsequence  —  O(n^2): dp[i] = 1 + max dp[j] for j<i, a[j]<a[i]
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+1
function 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;
}
assert.equal(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]), 4);
assert.equal(lengthOfLISFast([10, 9, 2, 5, 3, 7, 101, 18]), 4);
assert.equal(lengthOfLISFast([7, 7, 7]), 1);
assert.equal(lengthOfLIS([]), 0);

// ── 7. [string, 2-D] Longest common subsequence  —  match: 1 + dp[i-1][j-1]; else max(dp[i-1][j], dp[i][j-1])  —  O(mn) / O(mn)
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];
}
assert.equal(lcs('abcde', 'ace'), 3);
assert.equal(lcs('abc', 'def'), 0);
assert.equal(lcs('', 'a'), 0);

// ── 8. [string, 2-D] Edit distance (Levenshtein)  —  dp[i][j] = min(delete, insert, replace) + 1 unless chars match  —  O(mn)
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];
}
assert.equal(minDistance('horse', 'ros'), 3);
assert.equal(minDistance('intention', 'execution'), 5);
assert.equal(minDistance('', 'abc'), 3);

// ── 9. [knapsack 0/1] max value with capacity W  —  1-D dp over capacity, iterate capacity DESCENDING so each item used once  —  O(nW) / O(W)
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];
}
assert.equal(knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7), 9);
assert.equal(knapsack01([10], [5], 5), 0);
assert.equal(knapsack01([], [], 5), 0);

// ── 10. [knapsack unbounded] same but capacity ASCENDING so items can repeat  —  O(nW) / O(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];
}
assert.equal(knapsackUnbounded([2, 3], [3, 4], 7), 10); // 2+2+3 -> 3+3+4; 0/1 version can only do 2+3 -> 7
assert.equal(knapsack01([2, 3], [3, 4], 7), 7);
assert.equal(knapsackUnbounded([2], [3], 7), 9);

// ── 11. [2-D grid] Unique paths  —  dp[r][c] = dp[r-1][c] + dp[r][c-1]; rolling row  —  O(mn) / O(n)
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];
}
assert.equal(uniquePaths(3, 7), 28);
assert.equal(uniquePaths(3, 2), 3);
assert.equal(uniquePaths(1, 1), 1);

// ── 12. [2-D grid] Min path sum  —  dp[r][c] = grid + min(up, left); in place  —  O(mn) / O(1) extra
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];
}
assert.equal(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]), 7);
assert.equal(minPathSum([[1, 2, 3], [4, 5, 6]]), 12);
assert.equal(minPathSum([[5]]), 5);

// ── 13. [string, 1-D] Word break  —  dp[i] = any j<i with dp[j] && s[j..i) in dict  —  O(n^2 * L) / O(n)
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];
}
assert.equal(wordBreak('leetcode', ['leet', 'code']), true);
assert.equal(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']), false);
assert.equal(wordBreak('', ['a']), true);

// ── 14. [knapsack 0/1, boolean] Partition equal subset sum  —  target = sum/2; dp[s] reachable; descending capacity  —  O(n * sum) / O(sum)
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];
}
assert.equal(canPartition([1, 5, 11, 5]), true);
assert.equal(canPartition([1, 2, 3, 5]), false);
assert.equal(canPartition([]), true);

// ── 15. [1-D string] Decode ways  —  dp[i] += dp[i-1] if s[i-1] != '0'; += dp[i-2] if 10..26  —  O(n) / O(1)
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;
}
assert.equal(numDecodings('226'), 3);
assert.equal(numDecodings('06'), 0);
assert.equal(numDecodings('10'), 1);

// ── 16. [1-D] Maximum product subarray  —  track max AND min (negatives flip); swap when x < 0  —  O(n) / O(1)
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;
}
assert.equal(maxProduct([2, 3, -2, 4]), 6);
assert.equal(maxProduct([-2, 0, -1]), 0);
assert.equal(maxProduct([-2, 3, -4]), 24);

// ── 17. [interval DP] Longest palindromic subsequence  —  dp[i][j] over substrings by increasing length; = LCS(s, reverse(s))  —  O(n^2)
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;
}
assert.equal(longestPalindromeSubseq('bbbab'), 4);
assert.equal(longestPalindromeSubseq('cbbd'), 2);
assert.equal(longestPalindromeSubseq(''), 0);

// ── 18. [1-D] Kadane as DP  —  dp[i] = max(nums[i], dp[i-1] + nums[i]) = "best subarray ENDING at i"; answer = max dp  —  O(n) / O(1)
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;
}
assert.equal(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
assert.equal(maxSubArray([-1]), -1);
assert.equal(maxSubArray([5, 4, -1, 7, 8]), 23);

console.log('ok: algorithms/dynamic-programming.js');