DP Fundamentals

🧠 Dynamic Programming Fundamentals

The Magic of Remembering: A Journey into DP

Imagine you’re a detective solving a mystery. Instead of re-investigating the same clues over and over, you write everything down in your notebook. That’s exactly what Dynamic Programming does — it remembers!

🎯 What is Dynamic Programming?

The Lazy Smart Kid Analogy

Think of a smart kid who’s also a bit lazy. When mom asks:

• “What’s 3 + 2?” → Kid calculates: 5
• “What’s 3 + 2 + 4?” → Kid thinks: “Wait, I already know 3+2=5, so it’s just 5+4 = 9!”

That’s DP in a nutshell! Don’t redo work you’ve already done.

Real Definition (Simple Version)

Dynamic Programming = Breaking a big problem into smaller pieces + Remembering the answers to those pieces

// Without DP (doing work again)
fibonacci(5) calls fibonacci(4) and fibonacci(3)
fibonacci(4) calls fibonacci(3) again! 😱

// With DP (remember!)
fibonacci(3) = 2 (saved!)
fibonacci(4) = 3 (saved!)
fibonacci(5) = 5 ✅

When Do We Use DP?

Look for these two magic signs:

1. Overlapping Subproblems — Same smaller problems appear again and again
2. Optimal Substructure — The best answer comes from combining best answers of smaller parts

graph TD
    A["Big Problem"] --> B["Subproblem 1"]
    A --> C["Subproblem 2"]
    B --> D["Tiny Problem"]
    C --> D
    D -->|Same problem!| E["Save it once, use twice!"]

🛠️ DP Implementation Approaches

There are two ways to cook the same dish!

Approach 1: Top-Down (Memoization)

The “Ask and Remember” Way

Imagine you’re at the top of a staircase, looking down. You ask: “How many ways to reach the bottom?” Then you break it into smaller questions.

// Top-Down: Start from what we want
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

int climb(int n) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];

    memo[n] = climb(n-1) + climb(n-2);
    return memo[n];
}

Why “Memoization”? You write a memo (note) to remember answers!

Approach 2: Bottom-Up (Tabulation)

The “Build from Ground Up” Way

Now imagine you’re at the bottom of the staircase, looking up. You solve small problems first, then use them to solve bigger ones.

// Bottom-Up: Start from smallest
int climb(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

Which One to Pick? 🤔

Pro tip: Start with Top-Down (easier to think), convert to Bottom-Up (faster) later!

🏗️ State Definition in DP

What is “State”?

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

Think of it like GPS coordinates. To know where you are:

• In a city: You need street + building number
• In a game: You need position + score + lives left
• In DP: You need the variables that change

The Recipe for Defining State

Ask yourself: “What do I need to know to answer this subproblem?”

Example 1: Fibonacci

• What changes? Just the position n
• State: dp[n] = nth Fibonacci number

// State: just one variable!
dp[n] = dp[n-1] + dp[n-2]

Example 2: Knapsack Problem

• What changes? Current item AND remaining capacity
• State: dp[item][capacity]

// State: TWO variables!
// dp[i][w] = max value using items 0..i
//            with capacity w
dp[i][w] = max(
    dp[i-1][w],              // skip item
    dp[i-1][w-wt[i]] + val[i] // take item
);

Example 3: Edit Distance

• What changes? Position in first string AND position in second string
• State: dp[i][j]

// dp[i][j] = min operations to convert
//            first i chars to first j chars

State Definition Checklist ✅

1. What variables change as we solve subproblems?
2. What’s the minimum info needed to solve each subproblem?
3. Can I express the answer using these variables?

graph TD
    A["Identify what changes"] --> B["List all variables"]
    B --> C["Remove unnecessary ones"]
    C --> D["Define: dp of remaining variables"]
    D --> E["Your State!"]

🔄 State Transition in DP

What is Transition?

Transition = The rule that connects smaller answers to bigger answers

It’s the magic formula that says: “If I know the answer for smaller problems, here’s how to get the answer for this problem!”

The Transition Recipe

1. Look at your current state
2. Think: “What decisions can I make?”
3. Each decision leads to a smaller subproblem
4. Combine the smaller answers

Example: Climbing Stairs

Problem: You can climb 1 or 2 steps. How many ways to reach step n?

Transition Thinking:

• To reach step n, I either came from step n-1 (took 1 step) OR step n-2 (took 2 steps)
• Ways to reach n = Ways to reach n-1 + Ways to reach n-2

// Transition equation:
dp[n] = dp[n-1] + dp[n-2]

// In code:
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

Example: House Robber

Problem: Can’t rob adjacent houses. Maximize money!

Transition Thinking:

• At house i, I either rob it or skip it
• Rob it: money[i] + best from houses 0 to i-2
• Skip it: best from houses 0 to i-1

// Transition equation:
dp[i] = max(
    dp[i-1],           // skip house i
    dp[i-2] + money[i] // rob house i
)

Example: Longest Common Subsequence

Problem: Find longest sequence common to both strings

Transition:

if (s1[i] == s2[j]) {
    // Characters match! Add 1 to previous
    dp[i][j] = dp[i-1][j-1] + 1;
} else {
    // No match: take best so far
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

Transition Pattern Summary

💾 DP Space Optimization

The Problem with Space

Sometimes our DP tables get HUGE!

// 2D DP table for strings of length 1000
int[][] dp = new int[1000][1000];
// That's 1,000,000 integers! 😰

The Key Insight 💡

Often, we only need a few previous rows/values to compute the current one!

Technique 1: Rolling Array (2 Rows → 1D)

Before: Using full 2D array

int[][] dp = new int[n][m];
for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
        dp[i][j] = dp[i-1][j-1] + ...
    }
}

After: Only keep 2 rows!

int[] prev = new int[m];
int[] curr = new int[m];

for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
        curr[j] = prev[j-1] + ...
    }
    // Swap rows
    int[] temp = prev;
    prev = curr;
    curr = temp;
}

Technique 2: Single Row (When only previous column matters)

Fibonacci Example:

// Before: Array of size n
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

// After: Just 2 variables! 🎉
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}
// Answer: prev1

Space: O(n) → O(1)! 🚀

Technique 3: Reverse Loop Trick

For 0/1 Knapsack-style problems:

// Before: 2D (O(n*W) space)
for (int i = 0; i < n; i++) {
    for (int w = W; w >= wt[i]; w--) {
        dp[i][w] = max(dp[i-1][w],
                       dp[i-1][w-wt[i]] + v[i]);
    }
}

// After: 1D with reverse loop!
for (int i = 0; i < n; i++) {
    for (int w = W; w >= wt[i]; w--) {
        dp[w] = max(dp[w], dp[w-wt[i]] + v[i]);
    }
}

Why reverse? So we don’t overwrite values we still need!

Space Optimization Summary

graph TD
    A["Check DP dependency"] --> B{How many rows needed?}
    B -->|Only prev row| C["Use 2 arrays + swap"]
    B -->|Only prev 1-2 values| D["Use 2-3 variables"]
    B -->|Same row, earlier cols| E["Reverse the loop"]
    C --> F["O of m space"]
    D --> G["O of 1 space"]
    E --> H["O of m space"]

When Can You Optimize?

🎯 Putting It All Together

The DP Problem-Solving Recipe

1. Identify DP Potential

   • Overlapping subproblems? ✓
   • Optimal substructure? ✓

2. Define the State

   • What variables describe a subproblem?

3. Write the Transition

   • How do smaller subproblems combine?

4. Set Base Cases

   • What are the smallest subproblems?

5. Optimize Space (if needed)

   • Can we reduce memory usage?

Quick Reference

// Template for most DP problems:

// 1. Define state array
int[] dp = new int[n + 1];

// 2. Base case(s)
dp[0] = ...; // smallest subproblem

// 3. Fill using transition
for (int i = 1; i <= n; i++) {
    dp[i] = // transition formula
}

// 4. Answer
return dp[n];

🌟 You Did It!

You now understand:

• ✅ What DP is and when to use it
• ✅ Top-Down vs Bottom-Up approaches
• ✅ How to define states like a pro
• ✅ How to write transition equations
• ✅ How to optimize space

Remember: DP is just being smart about remembering. Every expert was once a beginner who refused to give up!

Practice makes perfect. Start with simple problems (Fibonacci, Climbing Stairs) and work your way up!

💡 Pro Tip: When stuck, draw out small examples by hand. The pattern will reveal itself!