Dynamic Programming

Hard 35 min read

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
1
1
1
1
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

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