01 — Dynamic Programming — Basics

What is Dynamic Programming?

Optimization technique for problems with:

1. Overlapping subproblems — same subproblems solved repeatedly
2. Optimal substructure — optimal solution built from optimal sub-solutions

Brute force: O(2^n) or worse
DP:          O(n) or O(n²) — solve each subproblem ONCE, store result

---

Two Approaches

1. Memoization (Top-Down)

Start from the main problem, recurse down, cache results.

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

2. Tabulation (Bottom-Up)

Build solution iteratively from base cases up.

// Fibonacci — tabulation
function fib(n: number): number {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// Space optimized — only need last 2 values
function fib(n: number): number {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

---

Memoization vs Tabulation

---

1D DP Problems

Climbing Stairs

Ways to reach step n (1 or 2 steps at a time).

// dp[i] = dp[i-1] + dp[i-2]
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

House Robber

Max money robbing non-adjacent houses.

// dp[i] = max(dp[i-1], dp[i-2] + nums[i])
function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  let prev2 = 0, prev1 = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Minimum Cost Climbing Stairs

function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  for (let i = 2; i < n; i++) {
    cost[i] += Math.min(cost[i - 1], cost[i - 2]);
  }
  return Math.min(cost[n - 1], cost[n - 2]);
}

Decode Ways

Count ways to decode a numeric string ("226" → "BZ", "VF", "BBF").

function numDecodings(s: string): number {
  if (s[0] === '0') return 0;
  const n = s.length;
  let prev2 = 1, prev1 = 1;
  
  for (let i = 1; i < n; i++) {
    let curr = 0;
    if (s[i] !== '0') curr += prev1;                    // Single digit
    const two = parseInt(s.substring(i - 1, i + 1));
    if (two >= 10 && two <= 26) curr += prev2;          // Two digits
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

---

DP Problem-Solving Framework

1. Define state:     What does dp[i] represent?
2. Base case:        What are the trivial answers? (dp[0], dp[1])
3. Recurrence:       How does dp[i] relate to smaller subproblems?
4. Order:            Bottom-up: smallest → largest
5. Answer:           Where is the final answer? (dp[n], max(dp), etc.)
6. Optimize space:   Can we use O(1) instead of O(n)?

---

Recognizing DP Problems

Clues that a problem needs DP:
  ✅ "Count the number of ways..."
  ✅ "Find the minimum/maximum..."
  ✅ "Is it possible to..." (with optimal substructure)
  ✅ "Find the longest/shortest..."
  ✅ Overlapping subproblems in recursion tree
  ✅ Choices at each step that affect future steps

---

Key Takeaways

• DP = store results of subproblems to avoid recomputation
• Memoization (top-down) = recursion + cache; Tabulation (bottom-up) = iterative
• Always start by defining the state and recurrence relation
• Space optimize by keeping only the last 1-2 values when possible
• Most 1D DP problems follow: dp[i] = f(dp[i-1], dp[i-2], ...)