DP Fundamentals

🧙‍♂️ Dynamic Programming: The Magic Recipe Book

Imagine you’re a chef who writes down every recipe you discover. Instead of figuring out how to make the same dish again and again, you just look at your notes!

🎯 What is Dynamic Programming?

Dynamic Programming (DP) is like having a magic notebook where you write down answers to problems you’ve already solved.

The Pizza Party Problem 🍕

Imagine you’re counting how many ways to share 10 pizza slices among friends. You figure out:

• 1 slice → 1 way
• 2 slices → 2 ways
• 3 slices → 3 ways

Without DP: You count from scratch every time someone asks.

With DP: You write it down! Next time someone asks about 3 slices, you just check your notebook.

// Our magic notebook!
const notebook = {};

function pizzaWays(slices) {
  // Already solved? Check notebook!
  if (notebook[slices]) {
    return notebook[slices];
  }

  // Solve and save
  const answer = calculateWays(slices);
  notebook[slices] = answer;
  return answer;
}

✨ The Two Magic Rules

1. Overlapping Subproblems → Same questions appear again and again
2. Optimal Substructure → Big answer = smaller answers combined

🏗️ DP Implementation Approaches

There are two ways to build your magic notebook. Think of them like two ways to climb stairs!

🔝 Top-Down (Memoization)

“Start at the top, ask for help going down”

graph TD
    A["fib 5"] --> B["fib 4"]
    A --> C["fib 3"]
    B --> D["fib 3"]
    B --> E["fib 2"]
    style D fill:#90EE90
    style C fill:#90EE90

You start with the big question and break it into smaller ones. Like asking:

• “What’s fib(5)?” → “Well, I need fib(4) + fib(3)”

const memo = {};

function fib(n) {
  // Base cases: We know these!
  if (n <= 1) return n;

  // Already solved? Return it!
  if (memo[n]) return memo[n];

  // Solve, save, return
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

⬆️ Bottom-Up (Tabulation)

“Start at the bottom, build your way up”

graph LR
    A["fib 0 = 0"] --> B["fib 1 = 1"]
    B --> C["fib 2 = 1"]
    C --> D["fib 3 = 2"]
    D --> E["fib 4 = 3"]
    E --> F["fib 5 = 5"]

You start with tiny problems and build up. Like stacking blocks!

function fibBottomUp(n) {
  // Our table (like a shelf)
  const table = [0, 1];

  // Build from bottom up
  for (let i = 2; i <= n; i++) {
    table[i] = table[i-1] + table[i-2];
  }

  return table[n];
}

🎭 Which One to Choose?

🎨 State Definition in DP

State = The information you need to describe exactly where you are in the problem.

🎮 The Video Game Analogy

In a video game, your “state” might be:

• Your position (level 3, room 5)
• Your health (80 HP)
• Your coins (250 gold)

In DP, we pick the smallest set of information needed to solve the problem.

Example: Climbing Stairs 🪜

Problem: How many ways to climb n stairs if you can take 1 or 2 steps?

State: Just the step number you’re on!

• dp[i] = number of ways to reach step i

function climbStairs(n) {
  const dp = new Array(n + 1);

  // Base states
  dp[0] = 1; // 1 way to stay at ground
  dp[1] = 1; // 1 way to reach step 1

  // Fill the rest
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }

  return dp[n];
}

Example: Knapsack Problem 🎒

Problem: Fill a bag with items (weight + value) to maximize value.

State: Two things matter!

• Which item we’re considering (i)
• Remaining capacity (w)

So: dp[i][w] = max value using first i items with capacity w

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill(null)
    .map(() => Array(capacity + 1).fill(0));

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

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

  return dp[n][capacity];
}

🎯 State Definition Checklist

🔄 State Transition in DP

Transition = How you move from one state to another. It’s the recipe for combining smaller answers!

🍳 The Cooking Recipe

If states are ingredients, transitions are the cooking steps:

• “Take the previous result…”
• “Add this new option…”
• “Pick the best one!”

The Transition Formula Pattern

Most DP problems follow this pattern:

dp[current] = operation(
  dp[previous_options],
  current_choice
)

Example: Minimum Coin Change 🪙

Problem: Fewest coins to make amount n

States: dp[amount] = min coins for this amount

Transition: Try each coin, pick the best!

function minCoins(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins for amount 0

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

  return dp[amount] === Infinity
    ? -1
    : dp[amount];
}

graph TD
    A["dp[5] = ?"] --> B["Try coin 1:<br/>dp[4] + 1"]
    A --> C["Try coin 2:<br/>dp[3] + 1"]
    A --> D["Try coin 5:<br/>dp[0] + 1 ✓"]
    D --> E["Best: 1 coin!"]

Example: Longest Common Subsequence 📝

Problem: Find longest sequence in both strings

States: dp[i][j] = LCS of first i chars and first j chars

Transition: Match or skip!

function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array(m + 1).fill(null)
    .map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        // Characters match!
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        // Skip one character
        dp[i][j] = Math.max(
          dp[i-1][j],
          dp[i][j-1]
        );
      }
    }
  }

  return dp[m][n];
}

🎯 Transition Patterns

💾 DP Space Optimization

Sometimes your DP table is HUGE. But wait—do you really need all of it?

🎪 The Moving Spotlight

Imagine a theater spotlight. It only lights up what’s happening NOW. We don’t need to light the whole stage!

Key Insight: If dp[i] only depends on dp[i-1], we only need 2 rows!

Before: Full Table 📊

// Fibonacci with full table
function fibFull(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: O(n) 😰
}

After: Just Two Variables! ✨

// Fibonacci optimized!
function fibOptimized(n) {
  if (n <= 1) return n;

  let prev2 = 0;  // dp[i-2]
  let prev1 = 1;  // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
  // Space: O(1) 🎉
}

2D to 1D Optimization

For 2D problems where each row only depends on the previous row:

// Knapsack: Before (2D)
// dp[i][w] depends on dp[i-1][w]
// and dp[i-1][w-weight]

// Knapsack: After (1D)
function knapsackOptimized(weights, values, cap) {
  const dp = Array(cap + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // Go BACKWARDS to avoid overwriting!
    for (let w = cap; w >= weights[i]; w--) {
      dp[w] = Math.max(
        dp[w],
        dp[w - weights[i]] + values[i]
      );
    }
  }

  return dp[cap];
}

⚠️ The Backward Loop Trick

When optimizing 0/1 problems, iterate backwards:

graph LR
    A["Wrong: → forward"] --> B["Overwrites<br/>needed values!"]
    C["Right: ← backward"] --> D["Safe! Uses<br/>old values"]

🎯 Space Optimization Patterns

🚀 Quick Reference: The DP Checklist

1. Can I use DP?

   • ✅ Overlapping subproblems?
   • ✅ Optimal substructure?

2. Define the State

   • What info do I need?
   • What does dp[...] represent?

3. Find the Transition

   • How do states connect?
   • What choices can I make?

4. Set Base Cases

   • What are the smallest problems?
   • What are their answers?

5. Choose an Approach

   • Top-down (recursion + memo)
   • Bottom-up (loops + table)

6. Optimize Space (if needed)

   • Do I need the full table?
   • Can I use rolling variables?

🎊 You Did It!

You now understand the foundations of Dynamic Programming:

• 🧠 What DP is → A smart way to remember answers
• 🔨 Two approaches → Top-down vs Bottom-up
• 🎯 State definition → What info describes your problem
• 🔄 State transition → How states connect
• 💾 Space optimization → Use less memory

Remember: Every DP problem is just a puzzle. Find the states, find the transitions, and let the magic happen! ✨