Dynamic Programming Made Easy - Learn Step by Step

🤔 Why Should You Care About Dynamic Programming?

🎮

Video Game Level Design

Games calculate the minimum moves to complete a level, optimal paths through dungeons, or best equipment combinations - all using DP!

📱

Text Message Autocorrect

Your phone uses DP (edit distance) to find the closest matching word when you make a typo.

🗺️

GPS Navigation

Finding the shortest route from point A to B uses DP algorithms to avoid recalculating the same paths.

💰

Investment Portfolio

Optimizing investment strategies over time to maximize returns uses DP principles.

🎬

Video Streaming

Netflix and YouTube use DP to optimize video quality based on your bandwidth, buffering ahead efficiently.

🏭

Manufacturing

Assembly lines use DP to minimize production time and costs by finding optimal sequences.

🌟 Level 1: The Basics (Start Here!)

Level 1

What is Dynamic Programming? Think of it as Smart Problem Solving! 🧠

Imagine you're climbing stairs and counting how many ways you can reach the top. Instead of recounting every time, you remember what you already calculated. That's DP!

🪜 Climbing Stairs Problem

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

🦶

Step 0

1 way

👟

Step 1

1 way

👟👟

Step 2

2 ways

🏃

Step 3

3 ways

🎯

Step 4

5 ways!

Formula: Ways(n) = Ways(n-1) + Ways(n-2)
Step 4: 3 + 2 = 5 ways! 🎉

The Two Magic Ingredients of DP 🪄

1️⃣ Overlapping Subproblems

The same smaller problems appear multiple times.

Example: To reach step 4, you calculate step 2 multiple times!

2️⃣ Optimal Substructure

The best solution uses best solutions of smaller problems.

Example: Best way to step 4 = Best way to step 3 + Best way to step 2

Your First DP Solution - Climbing Stairs 🪜

# Without DP - Slow and Repetitive! ❌
def climb_stairs_slow(n):
    if n <= 1:
        return 1
    # Recalculates same values over and over!
    return climb_stairs_slow(n-1) + climb_stairs_slow(n-2)

# With DP - Fast and Smart! ✅
def climb_stairs_dp(n):
    if n <= 1:
        return 1
    
    # Create a memory to store results
    dp = [0] * (n + 1)
    dp[0] = 1  # 1 way to stay at ground
    dp[1] = 1  # 1 way to reach step 1
    
    # Build up from bottom
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        print(f"Step {i}: {dp[i]} ways")
    
    return dp[n]

# Try it!
result = climb_stairs_dp(4)
# Output: Step 2: 2 ways
#         Step 3: 3 ways
#         Step 4: 5 ways
                                

⚠️ Common Mistake #1: Forgetting Base Cases

# ❌ WRONG - No base cases!
def fibonacci_wrong(n):
    memo = {}
    return fibonacci_wrong(n-1) + fibonacci_wrong(n-2)
    # This causes infinite recursion!
                            

✅ The Right Way

# ✅ CORRECT - Always define base cases first
def fibonacci_correct(n, memo={}):
    if n <= 1:  # Base cases
        return n
    if n in memo:  # Check memory
        return memo[n]
    memo[n] = fibonacci_correct(n-1, memo) + fibonacci_correct(n-2, memo)
    return memo[n]
                            

🎮 Try It Yourself: Calculate Fibonacci

Enter a number to see how DP calculates Fibonacci efficiently!

🎨 Level 2: Common DP Patterns

Level 2

Pattern 1: 0/1 Knapsack (Choose or Don't Choose) 🎒

You're packing for a trip with limited bag space. Which items give you the most value?

The Decision Process

1

For each item: Can I include it?

2

If yes: What's the value with it?

3

Compare: Better with or without?

🎒 Knapsack Example: Capacity = 4kg

📱

Phone

1kg, $500

💻

Laptop

3kg, $1500

📷

Camera

2kg, $1000

✅

Best Mix

📱+💻 = $2000

Knapsack Solution

def knapsack(weights, values, capacity):
    n = len(weights)
    # Create DP table: dp[i][w] = max value with first i items and weight limit w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i-1][w]
            
            # Option 2: Take item i-1 (if it fits)
            if weights[i-1] <= w:
                value_with_item = values[i-1] + dp[i-1][w - weights[i-1]]
                dp[i][w] = max(dp[i][w], value_with_item)
    
    return dp[n][capacity]

# Example usage
weights = [1, 3, 2]  # kg
values = [500, 1500, 1000]  # dollars
capacity = 4  # kg

max_value = knapsack(weights, values, capacity)
print(f"Maximum value: ${max_value}")  # Output: $2000
                                

Pattern 2: Longest Common Subsequence (LCS) 🔤

Finding similarities between two sequences - like DNA matching or text comparison!

Finding LCS between "ABCDGH" and "AEDFHR"

""

A

B

C

D

G

H

A

1

Result: LCS = "ADH" (length 3) ✨

Pattern 3: Coin Change (Minimum Coins) 💰

Making Change with Minimum Coins

def min_coins(coins, amount):
    # dp[i] = minimum coins needed for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins for amount 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Example: Making 11¢ with coins [1¢, 5¢, 6¢]
coins = [1, 5, 6]
amount = 11
result = min_coins(coins, amount)
print(f"Minimum coins for {amount}¢: {result}")  # Output: 2 (5¢ + 6¢)
                                

💪 Level 3: Practice Problems

Practice Time!

Problem Set: From Easy to Hard

E

Easy: House Robber 🏠

You're a robber planning to rob houses. Each house has money, but you can't rob adjacent houses (alarm system!). Find maximum money you can rob.

💡 Hint

For each house, decide: rob it (and skip previous) or skip it (and take previous max).

M

Medium: Unique Paths 🏁

Robot at top-left of grid needs to reach bottom-right. Can only move right or down. How many unique paths exist?

💡 Hint

Ways to reach a cell = ways from above + ways from left.

H

Hard: Edit Distance ✏️

Convert word1 to word2 using minimum operations (insert, delete, replace). What's the minimum number of operations?

💡 Hint

If characters match, no operation needed. Otherwise, try all 3 operations and pick minimum.

🎯 Challenge: Solve the House Robber Problem

Given houses with money: [2, 7, 9, 3, 1], what's the maximum you can rob?

def rob_houses(houses):
    # Your code here!
    # Tip: dp[i] = max money robbing up to house i
    pass
                            

Show Solution

def rob_houses(houses):
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    dp = [0] * len(houses)
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        # Rob current house or skip it
        dp[i] = max(dp[i-1], houses[i] + dp[i-2])
    
    return dp[-1]

# Answer: 12 (rob houses 0, 2, 4: 2+9+1=12)
                                

🚀 Level 4: Advanced Techniques

Level 4

Space Optimization: From O(n²) to O(n) 🎯

Space-Optimized Fibonacci

# Regular DP - O(n) space
def fib_regular(n):
    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]

# Optimized - O(1) space! 🚀
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1
                                

State Machine DP 🤖

Some problems involve tracking different states (like buy/sell stocks with cooldown).

Stock Trading with States

💰

Hold

Own stock

→

💵

Sold

Just sold

→

⏸️

Rest

Cooldown

DP on Trees 🌳

Maximum Path Sum in Binary Tree

def max_path_sum(root):
    def helper(node):
        if not node:
            return 0
        
        # Get max sum from left and right subtrees
        left_max = max(helper(node.left), 0)  # Ignore negative paths
        right_max = max(helper(node.right), 0)
        
        # Max path through current node
        current_max = node.val + left_max + right_max
        
        # Update global maximum
        self.max_sum = max(self.max_sum, current_max)
        
        # Return max path continuing through parent
        return node.val + max(left_max, right_max)
    
    self.max_sum = float('-inf')
    helper(root)
    return self.max_sum
                                

📖 Quick Reference Guide

🎯 DP Problem Identification Checklist

✅ Can be broken into smaller subproblems?
✅ Subproblems overlap (appear multiple times)?
✅ Optimal solution uses optimal subproblem solutions?
✅ Asking for minimum/maximum/count/possibility?

📝 Common DP Patterns

🎒 0/1 Knapsack: Include or exclude
💰 Unbounded Knapsack: Unlimited items
🔤 LCS/LIS: Sequence problems
🏁 Grid Traversal: Paths in matrix
✂️ Partition: Split into subsets
🎮 Game Theory: Win/lose states

⚡ Time Complexities

📊 1D DP: O(n)
📊 2D DP: O(n²) or O(nm)
📊 Knapsack: O(n × capacity)
📊 LCS: O(n × m)
📊 Matrix Chain: O(n³)
📊 TSP: O(n² × 2ⁿ)

🚀 Pro Tips for DP Success

Start with recursion: Write the recursive solution first
Add memoization: Cache results to avoid recomputation
Convert to table: Build bottom-up if needed
Optimize space: Use rolling arrays when possible
Draw the recursion tree: Visualize overlapping subproblems
Define state clearly: What does dp[i][j] represent?