Dynamic Programming for Beginners: From Zero to Hero

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler subproblems. It's not a specific algorithm—it's a problem-solving approach.

The Two Key Properties

A problem can be solved with DP if it has:

1. Optimal Substructure:* The optimal solution contains optimal solutions to subproblems
2. Overlapping Subproblems:* The same subproblems are solved multiple times

A Simple Analogy

• Think of calculating Fibonacci numbers:
• fib(5) = fib(4) + fib(3)
• fib(4) = fib(3) + fib(2)
• Notice: fib(3) is calculated twice!

Without DP, we recalculate the same values. With DP, we store results and reuse them.

# Without DP - O(2^n) - Very slow!
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# With DP - O(n) - Much better!
def fib_dp(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_dp(n-1, memo) + fib_dp(n-2, memo)
    return memo[n]

When to Use DP

Look for these clues in problem statements:

1. "Find the minimum/maximum..."*
2. "Count the number of ways..."*
3. "Is it possible to..."*
4. "Find the longest/shortest..."*
5. Problems involving sequences, strings, or grids*

Red Flags

• Asking for all possible solutions (might need backtracking instead)
• No overlapping subproblems (greedy might work)

Top-Down Approach (Memoization)

Start with the main problem and recursively solve subproblems, storing results.

Template

def solve(params):
    memo = {}
    
    def dp(state):
        # Base case
        if is_base_case(state):
            return base_value
        
        # Check memo
        if state in memo:
            return memo[state]
        
        # Recursive case
        result = combine(
            dp(smaller_state_1),
            dp(smaller_state_2),
            ...
        )
        
        memo[state] = result
        return result
    
    return dp(initial_state)

Example: Climbing Stairs

You can climb 1 or 2 steps at a time. Count ways to reach the top.

def climb_stairs(n):
    memo = {}
    
    def dp(step):
        if step == 0:
            return 1  # One way: don't move
        if step < 0:
            return 0  # Invalid
        if step in memo:
            return memo[step]
        
        # Either take 1 step or 2 steps
        memo[step] = dp(step - 1) + dp(step - 2)
        return memo[step]
    
    return dp(n)

Bottom-Up Approach (Tabulation)

Start with base cases and build up to the solution.

Template

def solve(params):
    # Create DP table
    dp = [0] * (n + 1)
    
    # Base cases
    dp[0] = base_value_0
    dp[1] = base_value_1
    
    # Fill table
    for i in range(2, n + 1):
        dp[i] = combine(dp[i-1], dp[i-2], ...)
    
    return dp[n]

Example: Climbing Stairs (Bottom-Up)

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

Space Optimization

Often you only need the last few values:

def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

Step-by-Step Examples

Example 1: House Robber

Can't rob adjacent houses. Maximize loot.

Step 1: Define the state dp[i] = maximum money robbing houses 0 to i

• Step 2: Find the recurrence*
• At house i, either:
• Rob it: dp[i] = nums[i] + dp[i-2]
• Skip it: dp[i] = dp[i-1]

So: dp[i] = max(nums[i] + dp[i-2], dp[i-1])

• Step 3: Base cases*
• dp[0] = nums[0]
• dp[1] = max(nums[0], nums[1])

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], nums[i] + dp[i-2])
    
    return dp[-1]

Example 2: Coin Change

Find minimum coins to make amount.

State: dp[amount] = minimum coins needed

Recurrence: dp[a] = min(dp[a - coin] + 1) for each coin

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

Common DP Patterns

1. Linear DP - State depends on previous elements - Examples: Climbing Stairs, House Robber

2. Grid DP - 2D state (row, col) - Examples: Unique Paths, Minimum Path Sum

3. String DP - Compare/match characters - Examples: Edit Distance, Longest Common Subsequence

4. Interval DP - Process ranges/intervals - Examples: Matrix Chain Multiplication

5. Knapsack DP - Select items with constraints - Examples: 0/1 Knapsack, Subset Sum

Tips for Interviews

1. Start with recursion:* Write the brute force recursive solution first
2. Identify overlapping subproblems:* Draw the recursion tree
3. Define state clearly:* What information uniquely identifies a subproblem?
4. Write the recurrence:* How do smaller problems combine?
5. Handle base cases:* What are the trivial cases?
6. Consider space optimization:* Can you reduce O(n) to O(1)?

Common Mistakes

• Forgetting base cases
• Off-by-one errors in table indexing
• Not initializing the DP table correctly
• Incorrect state definition

Summary

1. DP is powerful but follows a pattern:
2. Recognize it's a DP problem
3. Define the state
4. Find the recurrence relation
5. Identify base cases
6. Implement (top-down or bottom-up)
7. Optimize space if needed

Practice is key—start with classic problems and build intuition!