Dynamic Programming: Remember to Avoid Repeating Work!

Welcome! You’ve learned sorting and searching. Now Dynamic Programming (DP) - the smartest way to solve big problems by remembering answers and reusing them!

Why Dynamic Programming? (The Repeated Work Problem)

The Birthday Cake Problem

Imagine baking a birthday cake. You need:

• 2 cups flour
• 1 cup sugar
• 3 eggs

But each ingredient needs smaller ingredients! Flour needs wheat, sugar needs sugarcane, eggs need chicken feed…

Without DP: You recalculate everything every time (wasteful!) With DP: You remember “flour needs 5 wheat” and reuse that answer!

DP saves time by remembering solutions to subproblems!

The Two Ways to Remember

Method 1: Top-Down (Memoization) - “Sticky Notes”

Start with the big problem, break it down, and stick notes with answers as you go.

Like: Solving a math problem and writing down answers for later

Method 2: Bottom-Up (Tabulation) - “Fill the Table”

Start with tiny problems, solve them, and build up to the big answer.

Like: Filling out a multiplication table from 1×1 up to 10×10

Example: Climbing Stairs - “How Many Ways to the Top?”

Problem: You can climb 1 or 2 stairs at a time. How many ways to climb 4 stairs?

Without DP: Try every combination (slow!) With DP: Remember smaller stair problems!

Top-Down Approach (Memoization)

// Ways to climb stairs with memory
var memo = make(map[int]int)

func WaysToClimb(n int) int {
    // Base cases: 0 stairs = 1 way (do nothing), negative = 0 ways
    if n <= 0 {
        return 1
    }
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2  // 1+1 or 2
    }
    
    // Check if we already calculated this
    if val, exists := memo[n]; exists {
        return val  // Use remembered answer!
    }
    
    // Calculate and remember
    ways := WaysToClimb(n-1) + WaysToClimb(n-2)
    memo[n] = ways
    return ways
}

For 4 stairs: 5 ways (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

Bottom-Up Approach (Tabulation)

// Ways to climb stairs by building up
func WaysToClimbTable(n int) int {
    if n <= 0 {
        return 1
    }
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    
    // Create table for answers
    dp := make([]int, n+1)
    dp[0] = 1  // 0 stairs: 1 way
    dp[1] = 1  // 1 stair: 1 way
    dp[2] = 2  // 2 stairs: 2 ways
    
    // Fill table from small to big
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]  // Ways to reach i
    }
    
    return dp[n]
}

Like filling: dp[3] = dp[2] + dp[1] = 2 + 1 = 3 ways

Classic DP Problems - Real-Life Examples!

Problem 1: House Robber - “Steal Maximum Money Without Getting Caught”

Problem: Houses in a row have money: [2, 7, 9, 3, 1] Can’t rob adjacent houses (alarm connects them). What’s maximum you can steal?

DP Thinking: For each house, decide: rob it (add money + skip next) or skip it (take best from previous)

// Rob houses without robbing neighbors
func RobHouses(money []int) int {
    if len(money) == 0 {
        return 0
    }
    if len(money) == 1 {
        return money[0]
    }
    
    // dp[i] = maximum money from first i houses
    dp := make([]int, len(money))
    dp[0] = money[0]                          // First house: take it
    dp[1] = max(money[0], money[1])           // Second: take the bigger one
    
    for i := 2; i < len(money); i++ {
        // For each house: max of (skip it, take previous best) or (take it + skip previous)
        dp[i] = max(dp[i-1], money[i] + dp[i-2])
    }
    
    return dp[len(money)-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

For [2,7,9,3,1]: Best is 2+9+1 = 12 (houses 1,3,5)

Problem 2: Coin Change - “Fewest Coins for Exact Amount”

Problem: Coins: [1, 2, 5], make exactly 11 cents. Fewest coins?

DP Thinking: For each amount, try each coin and see which gives fewest coins

// Fewest coins to make exact amount
func FewestCoins(coins []int, amount int) int {
    // dp[i] = fewest coins to make amount i
    dp := make([]int, amount+1)
    
    // Initialize: impossible amounts = lots of coins
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0  // 0 amount needs 0 coins
    
    // For each amount from 1 to target
    for i := 1; i <= amount; i++ {
        // Try each coin
        for _, coin := range coins {
            if coin <= i {
                // If using this coin gives fewer coins, use it!
                dp[i] = min(dp[i], dp[i-coin] + 1)
            }
        }
    }
    
    if dp[amount] > amount {
        return -1  // Impossible
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

For 11 cents with [1,2,5]: 3 coins (5+5+1)

Problem 3: Longest Common Sequence - “What’s Similar Between Two Stories?”

Problem: Find longest sequence of letters that appears in both strings in same order.

“ABCD” and “ACBD” → “ABD” (not consecutive positions, but same order)

// Longest sequence that appears in both strings (in order)
func LongestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    
    // dp[i][j] = LCS of first i chars of text1 and first j chars of text2
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                // Same character: extend previous LCS
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                // Different: take best from either skipping one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    
    return dp[m][n]
}

Like: Finding common plot points between two stories

How to Solve DP Problems (Step by Step)

Step 1: Recognize It’s a DP Problem

Signs:

• “Maximum/minimum of something”
• “Number of ways to do something”
• “Can I reach this state?”
• Overlapping subproblems (same calculation repeated)

Step 2: Define Your DP State

What to track: What information do you need at each step?

Examples:

• Climbing stairs: dp[n] = ways to reach stair n
• House robber: dp[i] = max money from first i houses
• Coin change: dp[amount] = min coins for that amount

Step 3: Find the Recurrence Relation

How does current state relate to previous states?

Examples:

• Fibonacci: dp[n] = dp[n-1] + dp[n-2]
• House robber: dp[i] = max(dp[i-1], money[i] + dp[i-2])

Step 4: Set Base Cases

The simplest scenarios:

// Climbing stairs base cases
dp[0] = 1  // 0 stairs: 1 way (do nothing)
dp[1] = 1  // 1 stair: 1 way (climb 1)
dp[2] = 2  // 2 stairs: 2 ways (1+1 or 2)

Step 5: Choose Implementation Style

Top-Down (Recursion + Memo):

• Natural thinking
• Good for complex dependencies
• Might hit recursion limits

Bottom-Up (Tabulation):

• Iterative, no recursion limits
• Usually faster
• Good for simple dependencies

Common DP Patterns You See Everywhere

Pattern 1: 1D Array Problems (Single Sequence)

Like: Maximum sum of contiguous subarray

// Maximum subarray sum (Kadane's algorithm - a DP classic!)
func MaxSubarraySum(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSum := nums[0]
    currentSum := nums[0]
    
    for i := 1; i < len(nums); i++ {
        // At each position: start new subarray OR extend current
        currentSum = max(nums[i], currentSum + nums[i])
        maxSum = max(maxSum, currentSum)
    }
    
    return maxSum
}

Real life: Finding best consecutive days of profit

Pattern 2: 2D Table Problems (Two Sequences)

Like: Edit distance between two words

// How many edits to turn word1 into word2?
func EditDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i  // Delete all chars from word1
    }
    for j := range dp[0] {
        dp[0][j] = j  // Insert all chars to make word2
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]  // No change needed
            } else {
                // Try: substitute, delete, or insert
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
            }
        }
    }
    
    return dp[m][n]
}

Real life: Spell check suggestions, DNA sequence comparison

Pattern 3: Knapsack Problems (Choose Items with Constraints)

Like: Fill backpack with most valuable items without exceeding weight

// 0/1 Knapsack: each item once
func Knapsack(maxWeight int, weights, values []int) int {
    n := len(weights)
    // dp[i][w] = max value using first i items, weight limit w
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, maxWeight+1)
    }
    
    for i := 1; i <= n; i++ {
        for w := 1; w <= maxWeight; w++ {
            if weights[i-1] <= w {
                // Take item: value + remaining capacity
                // Or skip item: previous best
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            } else {
                // Can't take: use previous best
                dp[i][w] = dp[i-1][w]
            }
        }
    }
    
    return dp[n][maxWeight]
}

Real life: Loading truck with most valuable cargo, budget planning

When Should You Use Dynamic Programming?

Use DP when you see these clues:

1. Optimization Problems: “What’s the maximum/minimum?”

   • Most profitable stock trades
   • Shortest path in maze
   • Maximum value backpack can hold

2. Counting Problems: “How many ways?”

   • Ways to climb stairs
   • Ways to make change
   • Paths through grid

3. Yes/No Decisions: “Can I reach this state?”

   • Can I make exact amount with coins?
   • Can I pack all items in knapsack?

4. Overlapping Subproblems: Same calculation repeated

   • Fibonacci (calculates fib(5) many times)
   • Edit distance (compares same substrings)

5. Optimal Substructure: Best solution uses best subsolutions

   • Shortest path uses shortest subpaths
   • Best knapsack solution uses best sub-knapsacks

Speed and Memory in DP

• Time: Usually O(n²) or O(n³) - worth it for hard problems!
• Space: Often O(n) or O(n²) - can optimize by reusing arrays
• Trade-off: More memory = faster execution

Practice Problems - Build Your DP Skills! 🧠

Start simple, get harder:

1. Fibonacci Numbers - Classic DP warm-up
2. Climbing Stairs - Count ways to reach top
3. House Robber - Maximum money without adjacent houses
4. Coin Change - Fewest coins for exact amount
5. Longest Common Subsequence - Similar parts of two strings
6. Knapsack - Most valuable items that fit
7. Edit Distance - Changes to turn one word into another
8. Word Break - Can sentence be split into dictionary words?
9. Maximum Subarray - Contiguous numbers with largest sum
10. Decode Ways - Number of ways to decode a message

🎉 Congratulations! You’re a DP Thinker!

Dynamic Programming is like learning to ride a bike - tricky at first, but once you get it, you can go anywhere!

Key Takeaways:

• Break big problems into smaller ones
• Remember answers to avoid repeat work
• Build solutions step by step
• Practice makes perfect!

Next: Hashing - super-fast lookups with magic number tricks! 🚀