Linear DP

🧱 Linear DP: Building Answers One Step at a Time

Imagine you’re climbing a staircase, but each step you take depends on where you’ve been. That’s Dynamic Programming — remembering the past to make the future easier.

🎯 What is Linear DP?

Think of Linear DP like a chain of dominoes. You set up each domino based on the ones before it. When you push the first one, the rest fall in order.

In simple words:

• You have a row of problems (like boxes numbered 1, 2, 3…)
• Each box’s answer depends on boxes before it
• You solve them one by one, left to right
• You remember each answer so you don’t repeat work

graph TD
    A["Box 1"] --> B["Box 2"]
    B --> C["Box 3"]
    C --> D["Box 4"]
    D --> E["... Box N"]

🐰 The Fibonacci Pattern: The Mother of All DP

The Story of Two Bunnies

Once upon a time, a farmer had 1 pair of baby bunnies. Every month:

• Baby bunnies grow up (take 1 month)
• Grown-up bunnies make 1 new baby pair

How many bunny pairs after 6 months?

See the pattern? Each total = previous two totals added together!

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

This is the Fibonacci sequence — and it’s EVERYWHERE in DP!

The Magic Formula

fib(n) = fib(n-1) + fib(n-2)

Translation: To know today’s answer, just add yesterday’s and the day before’s!

Why This Matters

The Fibonacci pattern appears whenever:

• Current state = combining 1 or 2 previous states
• You’re counting ways to reach something
• You’re building something step by step

graph TD
    F5["fib 5 = 5"] --> F4["fib 4 = 3"]
    F5 --> F3a["fib 3 = 2"]
    F4 --> F3b["fib 3 = 2"]
    F4 --> F2a["fib 2 = 1"]

🪜 Climbing Stairs: Your First DP Adventure!

The Problem

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

The “Aha!” Moment

Where can you be right before the top step?

Only two places:

1. One step below (then take 1 step)
2. Two steps below (then take 2 steps)

So the total ways = ways to step (n-1) + ways to step (n-2)

Wait… that’s Fibonacci! 🎉

Visual Example: 4 Steps

Ways to reach Step 4:

Step 4: ⭐ (Goal!)
   ↗️ (take 1)     ↗️ (take 2)
Step 3            Step 2
(3 ways)          (2 ways)

Total: 3 + 2 = 5 ways!

All 5 ways to climb 4 steps:

1. 1→1→1→1
2. 1→1→2
3. 1→2→1
4. 2→1→1
5. 2→2

The Code

public int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1;  // ways for step 1
    int prev1 = 2;  // ways for step 2

    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Why only 2 variables? We only need the last two answers. Old answers can be forgotten — just like a caterpillar that only remembers its last 2 moves!

🏠 House Robber: The Greedy Thief’s Dilemma

The Story

You’re a very careful thief 🥷 (don’t worry, it’s just pretend!). Houses line up on a street, each with money inside.

The catch: If you rob two houses next to each other, alarms go off! 🚨

Goal: Steal the MOST money without triggering alarms.

The Thinking Process

At each house, you ask yourself:

1. Rob this house → Add its money, but SKIP the previous house
2. Skip this house → Keep whatever you had from before

House:    [💰2]  [💰7]  [💰9]  [💰3]  [💰1]
Index:      0      1      2      3      4

Building the Solution

Answer: $12 (Rob houses 0, 2, and 4)

The Magic Formula

dp[i] = max(dp[i-1], dp[i-2] + money[i])
        └─skip it─┘  └──rob it + skip neighbor──┘

The Code

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

    int prev2 = 0;
    int prev1 = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int current = Math.max(
            prev1,           // skip this house
            prev2 + nums[i]  // rob this house
        );
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

🔢 Decode Ways: Secret Messages!

The Spy Story

You’re a secret agent 🕵️. You received a coded message where:

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

The message “226” could mean:

• “2-2-6” → B-B-F → “BBF”
• “22-6” → V-F → “VF”
• “2-26” → B-Z → “BZ”

How many ways can you decode “226”? Answer: 3 ways!

The Rules

1. A single digit works if it’s 1-9 (not 0!)
2. Two digits work if they form 10-26

graph TD
    A["'226'"] --> B["'2' + decode '26'"]
    A --> C["'22' + decode '6'"]
    B --> D["'26' → 1 way"]
    B --> E["'2'+'6' → 1 way"]
    C --> F["'6' → 1 way"]

Walk Through “226”

Tricky Cases

• “06” → 0 ways (can’t start with 0)
• “10” → 1 way (only “10” works)
• “27” → 1 way (2-7, can’t use “27”)
• “11” → 2 ways (1-1 or 11)

The Code

public int numDecodings(String s) {
    if (s.charAt(0) == '0') return 0;

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

    for (int i = 1; i < s.length(); i++) {
        int current = 0;

        // Single digit (1-9)
        if (s.charAt(i) != '0') {
            current += prev1;
        }

        // Two digits (10-26)
        int twoDigit = Integer.parseInt(
            s.substring(i-1, i+1)
        );
        if (twoDigit >= 10 && twoDigit <= 26) {
            current += prev2;
        }

        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

🎯 The Pattern: See It Everywhere!

All four problems share the same skeleton:

// 1. Handle base cases
// 2. Keep track of prev1, prev2
// 3. For each position i:
//    current = f(prev1, prev2, data[i])
// 4. Slide the window forward
// 5. Return prev1

🚀 Key Takeaways

1. Fibonacci is the foundation — Most linear DP combines 1-2 previous answers

2. Space trick — You usually only need 2 variables, not an array!

3. Ask the right question — “Where could I have come FROM?” not “Where do I go?”

4. Build trust — Solve small cases by hand first, then see the pattern

5. Same recipe, different ingredients — All these problems look different but cook the same way!

graph LR
    A["Identify subproblems"] --> B["Find recurrence"]
    B --> C["Handle base cases"]
    C --> D["Code it up!"]
    D --> E["Optimize space"]

💪 You’ve Got This!

Linear DP is like learning to ride a bike. The first few problems feel tricky, but once you see the Fibonacci pattern hiding inside, you’ll spot it everywhere!

Remember: Every expert was once a beginner who didn’t give up. Now go practice these problems until they feel as natural as counting! 🎉