DP Fundamentals

🧙‍♂️ Dynamic Programming: The Magic of Remembering

Once upon a time, there was a wizard who was terrible at math. Every time someone asked him “What’s 3 + 5?”, he would count on his fingers. Then they’d ask “What’s 3 + 5 again?” and he’d count ALL OVER. Silly wizard!

One day, a clever student said: “Why not write down the answer the first time? Then just READ it!”

The wizard’s eyes lit up. This simple trick—remembering answers instead of recalculating them—is the heart of Dynamic Programming.

🎯 What is Dynamic Programming?

Dynamic Programming (DP) is like having a super memory.

Instead of solving the same puzzle over and over, you:

1. Solve it once
2. Write down the answer
3. Look it up next time

That’s it! You’re trading a bit of paper (memory) for a LOT of time savings.

Real Life Example 🍕

Imagine you run a pizza shop. A customer asks:

“How much for 2 slices?”

You calculate: $3 per slice × 2 = $6

Another customer asks the SAME thing. Do you calculate again? No! You just remember: “2 slices = $6”

┌─────────────────────────────┐
│  WITHOUT DP (Silly Wizard)  │
│  Calculate → Forget →       │
│  Calculate → Forget →       │
│  Calculate... (forever!)    │
└─────────────────────────────┘

┌─────────────────────────────┐
│  WITH DP (Smart Student)    │
│  Calculate → Remember →     │
│  Look up → Done! 🎉         │
└─────────────────────────────┘

🔑 When Does DP Work?

DP only works when your problem has two magical properties:

1. Overlapping Subproblems 🔄

The same small puzzle appears MANY times.

Example: Fibonacci Numbers

fib(5) needs fib(4) and fib(3)
fib(4) needs fib(3) and fib(2)
fib(3) needs fib(2) and fib(1)

Notice fib(3) appears twice? That’s overlap!

2. Optimal Substructure 🏗️

The best answer to the BIG puzzle = combining best answers to SMALL puzzles.

Example: Shortest Path The shortest path from A to C through B = (Shortest A→B) + (Shortest B→C)

🛠️ Two Ways to Build DP Solutions

Think of building a staircase. You can start from the bottom or the top!

Approach 1: Top-Down (Memoization) ⬇️

“Ask, then remember.”

You start with the BIG question and break it down. When you find an answer, you SAVE it.

# Memory box to store answers
memo = {}

def fib(n):
    # Already solved? Just return it!
    if n in memo:
        return memo[n]

    # Base cases (we know these)
    if n <= 1:
        return n

    # Solve and SAVE
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

How it feels:

"What's fib(5)?"
→ "Hmm, I need fib(4) and fib(3)..."
   → "What's fib(4)? I need fib(3) and fib(2)..."
      → (keeps asking smaller questions)
      → "Oh! fib(1) = 1, fib(0) = 0. Done!"
   → (now I remember fib(3)!)
→ "fib(5) = 5. Saved!"

Approach 2: Bottom-Up (Tabulation) ⬆️

“Build from ground up.”

You start with the SMALLEST answers and build up to the big one.

def fib(n):
    if n <= 1:
        return n

    # Build a table
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    # Fill from small to big
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

How it feels:

"Let me build up step by step..."
dp[0] = 0 ✓
dp[1] = 1 ✓
dp[2] = 0 + 1 = 1 ✓
dp[3] = 1 + 1 = 2 ✓
dp[4] = 1 + 2 = 3 ✓
dp[5] = 2 + 3 = 5 ✓
"Answer: 5!"

Which One to Pick? 🤔

📦 State: The Heart of Every DP Problem

State = What information do I need to describe my current situation?

Think of it like saving a video game. What do you need to save?

• Your position
• Your health
• Your inventory
• The level you’re on

In DP, state is the information you store to describe a subproblem.

Example: Climbing Stairs 🪜

You can climb 1 or 2 steps at a time. How many ways to reach step N?

State: dp[i] = number of ways to reach step i

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = 1  # 1 way to stay at ground
    dp[1] = 1  # 1 way to reach step 1

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

    return dp[n]

Example: Knapsack Problem 🎒

You have items with weights and values. What’s the maximum value you can carry?

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

Two pieces of information needed:

1. Which items we’ve considered
2. How much weight capacity remains

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(capacity+1):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            # Take item if it fits
            if weights[i-1] <= w:
                take = values[i-1] + dp[i-1][w-weights[i-1]]
                dp[i][w] = max(dp[i][w], take)

    return dp[n][capacity]

Choosing Good States 🎯

Ask yourself:

1. What changes between subproblems?
2. What do I need to know to solve the current problem?
3. What’s the MINIMUM information required?

Bad state: Too much info (wasteful) Good state: Just enough to make decisions

🔀 State Transition: The Magic Formula

Transition = How do I get from one state to another?

This is the RECIPE that connects small answers to big answers.

Pattern: Current = f(Previous States)

dp[current] = some_function(dp[smaller_problems])

Fibonacci Transition

dp[i] = dp[i-1] + dp[i-2]

Current = sum of two previous

Climbing Stairs Transition

dp[i] = dp[i-1] + dp[i-2]

To reach step i: come from step i-1 OR step i-2

Knapsack Transition

dp[i][w] = max(
    dp[i-1][w],           # Don't take item
    dp[i-1][w-wt] + val   # Take item
)

Choose the better option: skip or take

Writing Transitions: The 3-Step Dance 💃

Step 1: Identify your choices at each step

• Can I take this item or not?
• Can I go left or right?
• Can I use this coin or not?

Step 2: Write the formula for each choice

• If I take it: value + previous state
• If I skip it: just previous state

Step 3: Combine choices (usually max or min or sum)

# General pattern
dp[current] = combine(
    choice_1_result,
    choice_2_result,
    ...
)

🎈 Space Optimization: Travel Light!

Here’s a secret: Sometimes you don’t need to remember EVERYTHING.

Observation: Many DP solutions only look at the previous 1 or 2 states.

Fibonacci: From O(n) to O(1) Space

Before (stores everything):

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

After (only keeps what we need):

if n <= 1:
    return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
    curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
return prev1

We only need two variables!

Knapsack: From O(n×W) to O(W) Space

Key insight: Each row only needs the previous row.

Before (2D table):

dp = [[0]*(W+1) for _ in range(n+1)]

After (1D table, traverse backwards):

dp = [0] * (W + 1)
for i in range(n):
    # BACKWARDS to avoid using updated values
    for w in range(W, weights[i]-1, -1):
        dp[w] = max(dp[w], dp[w-weights[i]] + values[i])

Why Backwards? 🔙

When we go left-to-right, we overwrite values we still need!

Forward (WRONG):
dp[3] = dp[3-2] + val  # Uses NEW dp[1]

Backward (CORRECT):
dp[5] = dp[5-2] + val  # Uses OLD dp[3]
dp[3] = dp[3-2] + val  # Uses OLD dp[1]

🗺️ The DP Roadmap

graph TD
    A["🎯 Identify Problem"] --> B{Has Overlapping<br>Subproblems?}
    B -->|Yes| C{Has Optimal<br>Substructure?}
    B -->|No| X["❌ Not DP"]
    C -->|Yes| D["✅ Use DP!"]
    C -->|No| X
    D --> E["Define State"]
    E --> F["Write Transition"]
    F --> G["Set Base Cases"]
    G --> H["Choose Approach"]
    H --> I["Top-Down"]
    H --> J["Bottom-Up"]
    I --> K["Optimize Space?"]
    J --> K
    K --> L["🎉 Solution!"]

🧪 Classic Example: Longest Common Subsequence

Find the longest sequence that appears in both strings.

Strings: “ABCDE” and “ACE” Answer: “ACE” (length 3)

State Definition

dp[i][j] = LCS length of first i chars of string1 and first j chars of string2

Transition

if s1[i-1] == s2[j-1]:
    # Characters match! Add 1 to previous
    dp[i][j] = dp[i-1][j-1] + 1
else:
    # No match. Take best of skipping either char
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Full Code

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Space-Optimized Version

def lcs_optimized(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0]*(n+1)

    return prev[n]

🎓 Summary: Your DP Toolkit

🚀 You’re Ready!

Remember the wizard from our story? After learning to write down answers, he became the fastest mathematician in the kingdom!

DP is not magic—it’s being smart about memory.

When you see a problem that:

• Has the same subproblems appearing again and again
• Can be solved by combining smaller solutions

…you now know what to do. Define your state, write your transition, and let the computer do the remembering!

Happy Coding! 🎉