Linear DP

🧱 Linear DP: Building Solutions Step by Step

The Staircase Metaphor 🪜

Imagine you’re climbing a magical staircase. Each step you take builds on the ones before. You can’t jump to step 10 without first knowing how to reach step 9. This is Dynamic Programming — solving big problems by remembering small solutions!

🐰 The Fibonacci Pattern: Nature’s Building Blocks

What is Fibonacci?

Think of baby rabbits. Start with 1 pair. After a month, they have babies. Now you have 2 pairs. Next month, the first pair has more babies. Now 3 pairs. Then 5, then 8…

The Pattern:

1, 1, 2, 3, 5, 8, 13, 21...

Each number = sum of the previous two numbers!

Simple Example

// The magical formula
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

It’s like asking “How many rabbits at month 5?” You need to know month 4 and month 3 first!

The Smart Way (DP)

function fib(n) {
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    let next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

Why this works: We only remember the last two numbers. Like climbing stairs — you only need to remember the last two steps!

graph TD
    A["fib#40;5#41; = ?"] --> B["Need fib#40;4#41; + fib#40;3#41;"]
    B --> C["fib#40;4#41; = fib#40;3#41; + fib#40;2#41;"]
    B --> D["fib#40;3#41; = fib#40;2#41; + fib#40;1#41;"]
    C --> E["Build from bottom up!"]
    D --> E

🪜 Climbing Stairs: Your First DP Problem

The Story

You’re a little frog 🐸 at the bottom of a staircase with n steps. You can hop 1 step or 2 steps at a time. How many different ways can you reach the top?

Think Like a Frog

To reach step 5:

• Jump from step 4 (1 step hop)
• Jump from step 3 (2 step hop)

So: ways(5) = ways(4) + ways(3)

Sound familiar? It’s Fibonacci!

Real Example

3 steps → 3 ways:

1. 1 + 1 + 1 (hop, hop, hop)
2. 1 + 2 (hop, leap)
3. 2 + 1 (leap, hop)

The Code

function climbStairs(n) {
  if (n <= 2) return n;

  let prev = 1, curr = 2;

  for (let i = 3; i <= n; i++) {
    let next = prev + curr;
    prev = curr;
    curr = next;
  }

  return curr;
}

Why It Works

graph TD
    A["Step 5: 8 ways"] --> B["From Step 4: 5 ways"]
    A --> C["From Step 3: 3 ways"]
    B --> D["5 + 3 = 8 ✓"]
    C --> D

🏠 House Robber: The Clever Thief

The Story

You’re a sneaky raccoon 🦝 on a street of houses. Each house has yummy treats inside. But there’s a catch! If you visit two houses next to each other, the alarm goes off!

How do you get the MOST treats?

Think Like a Raccoon

At each house, you have 2 choices:

1. Rob this house → Can’t rob the previous one
2. Skip this house → Keep what you had

Real Example

Houses: [2, 7, 9, 3, 1]

Answer: Rob houses 1, 3, 5 → 2 + 9 + 1 = 12

The Magic Formula

best(i) = max(
  best(i-1),           // skip this house
  best(i-2) + value(i) // rob this house
)

The Code

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = 0;
  let prev1 = 0;

  for (let num of nums) {
    let curr = Math.max(
      prev1,        // skip
      prev2 + num   // rob
    );
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

graph TD
    A["At each house"] --> B{"Rob or Skip?"}
    B -->|Rob| C["Add value + skip neighbor"]
    B -->|Skip| D["Keep previous best"]
    C --> E["Pick the MAX"]
    D --> E

🔐 Decode Ways: Secret Messages

The Story

You’re a spy 🕵️ receiving secret number codes. Each letter A-Z is coded as 1-26.

• A = 1, B = 2, C = 3 … Z = 26

Given a string of numbers, how many ways can you decode it?

The Tricky Part

The code “12” could mean:

• “1” then “2” → A, B → “AB”
• “12” together → L → “L”

2 ways to decode “12”!

Real Example

Code: “226”

Answer: 3 ways!

The Rules

1. Single digit (1-9) → Valid letter
2. Two digits (10-26) → Valid letter
3. “0” alone → Invalid!
4. “30”, “40” etc → Invalid!

Think Step by Step

At position i:

• Can we use 1 digit? Add ways(i-1)
• Can we use 2 digits? Add ways(i-2)

The Code

function numDecodings(s) {
  if (s[0] === '0') return 0;

  let prev2 = 1;  // empty string
  let prev1 = 1;  // first char

  for (let i = 1; i < s.length; i++) {
    let curr = 0;

    // One digit decode
    if (s[i] !== '0') {
      curr += prev1;
    }

    // Two digit decode
    let twoDigit = parseInt(s.slice(i-1, i+1));
    if (twoDigit >= 10 && twoDigit <= 26) {
      curr += prev2;
    }

    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

Visual Guide

graph TD
    A["'226'"] --> B["2 → valid single"]
    A --> C["22 → valid pair"]
    B --> D["26 → valid pair"]
    B --> E["2,6 → valid singles"]
    C --> F["6 → valid single"]
    D --> G["Way 1: B-Z"]
    E --> H["Way 2: B-B-F"]
    F --> I["Way 3: V-F"]

🎯 The DP Pattern Summary

All four problems follow the same recipe:

The Recipe 🍳

1. Find the subproblem — What smaller question helps answer the big one?
2. Write the formula — How does today depend on yesterday?
3. Remember only what you need — Usually just 1-2 previous values
4. Build from the ground up — Start small, grow big

Side by Side

💡 The Big Idea

Dynamic Programming is just smart remembering!

Instead of solving the same thing over and over, we:

1. Solve small problems first
2. Write down the answers
3. Use those answers to solve bigger problems

It’s like leaving breadcrumbs 🍞 on your path — so you never get lost!

🚀 You Got This!

These four problems are the foundation. Master them, and you’ll see this pattern everywhere:

• Stock trading
• Coin change
• Text editing
• Path finding

Remember: Every expert was once a beginner standing at the bottom of the staircase. Now you know how to climb it — one step at a time! 🪜✨