Linear DP

🌟 Linear DP: The Art of Smart Counting

Imagine you’re climbing the world’s most magical staircase…

🎭 The Story of the Lazy Wizard

Once upon a time, there was a lazy wizard who hated doing the same work twice. Every time someone asked him a question, he would write down the answer on a sticky note. When someone asked the same question again? He’d just read the sticky note!

This wizard invented Dynamic Programming.

DP is exactly this: Remember what you’ve already solved, so you never solve it again.

🔢 The Fibonacci Pattern: Where It All Begins

What’s the Big Idea?

Imagine rabbits. One pair of rabbits has babies. Those babies grow up and have more babies. How many rabbits do you have after 10 months?

This is the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21...

Each number = sum of the two numbers before it.

The Problem with Being Naive

def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)

Why is this bad? To find fib(5), you calculate fib(3) TWICE. For fib(50), you’d wait until the sun burns out! ☀️💀

The Wizard’s Way (Memoization)

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Now we remember! Each answer gets saved. Ask again? Here’s your sticky note!

The Bottom-Up Way (Tabulation)

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Even simpler! Start from the beginning, build your way up.

graph TD
    A["Start: dp[0]=0, dp[1]=1"] --> B["dp[2] = dp[1] + dp[0] = 1"]
    B --> C["dp[3] = dp[2] + dp[1] = 2"]
    C --> D["dp[4] = dp[3] + dp[2] = 3"]
    D --> E["dp[5] = dp[4] + dp[3] = 5"]
    E --> F["Answer: 5"]

🪜 Climbing Stairs: Your First DP Adventure

The Story

You’re a tiny ant at the bottom of a staircase. You can take 1 step or 2 steps at a time. How many different ways can you reach the top?

Why This Matters

At step n, you could have come from:

• Step n-1 (took 1 step), OR
• Step n-2 (took 2 steps)

So: Ways to reach step n = Ways to step (n-1) + Ways to step (n-2)

Sound familiar? It’s Fibonacci in disguise! 🎭

The Code

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1  # One way to climb 1 step
    dp[2] = 2  # Two ways to climb 2 steps
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Let’s Walk Through It

3 steps: How many ways?

Path 1: 1 → 1 → 1 (three single steps)
Path 2: 1 → 2 (one single, one double)
Path 3: 2 → 1 (one double, one single)
Answer: 3 ways!

Check: dp[3] = dp[2] + dp[1] = 2 + 1 = 3 ✅

graph TD
    A["Step 0: Start"] --> B["Step 1: 1 way"]
    A --> C["Step 2: 2 ways"]
    B --> C
    C --> D["Step 3: 3 ways"]
    B --> D

🏠 House Robber: The Clever Thief

The Story

You’re a sneaky raccoon 🦝 on a street with houses in a row. Each house has treasure inside. But here’s the catch: If you rob two houses next to each other, the alarm goes off!

Which houses do you rob to get the MOST treasure without triggering alarms?

The Thinking

At each house, you have two choices:

1. Rob it: Add its value + whatever you got from two houses back
2. Skip it: Keep whatever you had from the previous house

Formula: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

The Code

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

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

Answer: Rob houses 0, 2, and 4 → Get 2+9+1 = 12! 💰

Space-Optimized Version

def rob_optimized(nums):
    if not nums:
        return 0
    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = curr
    return prev1

Why? We only need the last two values! No need for a whole array.

🔐 Decode Ways: Cracking the Secret Code

The Story

Your friend sends you a secret message using numbers:

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

You receive: "226"

How many ways can you decode it?

• 2-2-6 → “BBF”
• 22-6 → “VF”
• 2-26 → “BZ”

Answer: 3 ways!

The Tricky Parts

1. "0" alone is invalid (no letter is 0)
2. "06" is invalid (can’t have leading zero)
3. Numbers 10-26 can be one letter or two digits

The Formula

At position i:

• If current digit is valid (1-9): Add dp[i-1]
• If last two digits form valid letter (10-26): Add dp[i-2]

The Code

def num_decodings(s):
    if not s or s[0] == '0':
        return 0

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string = 1 way
    dp[1] = 1  # First char (already checked not '0')

    for i in range(2, n + 1):
        # Check single digit
        if s[i-1] != '0':
            dp[i] += dp[i-1]

        # Check two digits
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]

    return dp[n]

Walking Through “226”

Answer: 3 ways! 🎉

graph TD
    A["'226'"] --> B["'2' + decode#40;'26'#41;"]
    A --> C["'22' + decode#40;'6'#41;"]
    B --> D["'2'+'2'+decode#40;'6'#41;"]
    B --> E["'2'+'26'"]
    C --> F["'22'+'6'"]
    D --> G["BBF"]
    E --> H["BZ"]
    F --> I["VF"]

🧠 The Pattern You Just Learned

All four problems follow the same recipe:

1. Find the SUBPROBLEM (what's the smaller version?)
2. Find the RECURRENCE (how do smaller answers build bigger ones?)
3. Define BASE CASES (what do you know for sure?)
4. BUILD UP (go from small to big!)

🚀 Key Takeaways

1. DP = Remembering answers to avoid repeated work
2. Linear DP moves through an array, building answers step by step
3. Fibonacci pattern appears everywhere: stairs, robbers, codes!
4. Start simple: Work out small examples by hand first
5. Space trick: Often you only need the last 2 values, not the whole array

🎯 Quick Reference

# Fibonacci Template
dp[i] = dp[i-1] + dp[i-2]

# Decision Template (take or skip)
dp[i] = max(dp[i-1], dp[i-2] + value[i])

# Conditional Template (valid paths)
if condition1: dp[i] += dp[i-1]
if condition2: dp[i] += dp[i-2]

You’re now a DP apprentice! 🧙‍♂️

The lazy wizard would be proud. Now go save some rabbits, climb some stairs, rob some houses (in code only!), and crack some secret messages!