Dynamic Programming — Patterns & Classic Problems

// Naive recursion — O(2ⁿ) — recomputes the same subproblems
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Top-down (memoization) — O(n) time, O(n) space
function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// Bottom-up (tabulation) — O(n) time, O(1) space
function fibTab(n: number): number {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}
// Time: O(n) | Space: O(1)
// Note: identical pattern to Fibonacci

function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;

  for (const num of nums) {
    const curr = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
// Time: O(n) | Space: O(1)
// State: dp[i] = max loot from first i houses
// Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

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

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

  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Time: O(amount × coins.length) | Space: O(amount)

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

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }

  return dp[m - 1][n - 1];
}
// Time: O(m × n) | Space: O(m × n)

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = 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 character
      }
    }
  }

  return dp[m][n];
}
// Time: O(m × n) | Space: O(m × n)

function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => i === 0 ? j : j === 0 ? i : 0)
  );

  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];
      } 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)

function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  // dp[i][w] = max value using first i items with capacity w
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // Don't take item i
      dp[i][w] = dp[i - 1][w];

      // Take item i (if it fits)
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      }
    }
  }

  return dp[n][capacity];
}
// Time: O(n × capacity) | Space: O(n × capacity)

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;

  for (const num of nums) {
    // Traverse backwards to prevent using same item twice
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }

  return dp[target];
}
// Time: O(n × target) | Space: O(target)

function longestPalindrome(s: string): string {
  let start = 0, maxLen = 1;

  function expand(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLen) {
        start  = left;
        maxLen = right - left + 1;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);      // odd-length palindromes
    expand(i, i + 1);  // even-length palindromes
  }

  return s.substring(start, start + maxLen);
}
// Time: O(n²) | Space: O(1)

// Step 1: Write recursive solution
function longestIncreasingSubseq(nums: number[], i = 0, prev = -1): number {
  if (i === nums.length) return 0;
  let skip = longestIncreasingSubseq(nums, i + 1, prev);
  let take = 0;
  if (prev === -1 || nums[i] > nums[prev]) {
    take = 1 + longestIncreasingSubseq(nums, i + 1, i);
  }
  return Math.max(skip, take);
}

// Step 2: Add memoization (top-down DP)
// Step 3: Convert to bottom-up if space optimization is needed

// Optimal LIS — O(n log n) with patience sort / binary search
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }

  return tails.length;
}
// Time: O(n log n) | Space: O(n)

DP Patterns:
  1D linear:     Fibonacci, Climbing Stairs, House Robber, Coin Change
  2D grid:       Unique Paths, Minimum Path Sum
  2D sequences:  LCS, Edit Distance, LIS
  0/1 Knapsack:  Subset Sum, Partition Equal Subset
  Interval:      Palindromic Substrings, Burst Balloons

3-step framework:
  1. Define state (what does dp[i] mean?)
  2. Write recurrence (how does dp[i] relate to dp[i-1], dp[i-2]?)
  3. Base cases (dp[0], dp[1])

Optimizations:
  Space: Often 2D dp[i][j] can be reduced to 1D by reusing the row
  Time: Memoization avoids redundant recomputation
  Direction: Knapsack iterates backwards to prevent reuse