wal.sh
home > research > dp-tutorial · Dec 16, 2024

Dynamic Programming Tutorial

dynamic programmingmemoizationtabulationpythonalgorithmoptimal substructurefibonacci

Dynamic Programming Tutorial

Table of Contents

1. Introduction to Dynamic Programming

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems.

Key concepts:

  1. Optimal Substructure
  2. Overlapping Subproblems
  3. Memoization
  4. Bottom-up vs Top-down approaches

2. Setup

from typing import List, Dict, Optional
from functools import lru_cache
import time

def timing_decorator(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"{func.__name__} took {end - start:.4f} seconds")
        return result
    return wrapper

3. Classic Example: Fibonacci

3.1. Recursive (Naive) Approach

@timing_decorator
def fib_recursive(n: int) -> int:
    """Calculate nth Fibonacci number recursively."""
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# Test
test_fib = [fib_recursive(n) for n in range(10)]
print(f"First 10 Fibonacci numbers (recursive): {test_fib}")

3.2. Memoization (Top-down)

@timing_decorator
def fib_memo(n: int, memo: Dict[int, int] = None) -> int:
    """Calculate nth Fibonacci number with memoization."""
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Using Python's built-in memoization
@timing_decorator
@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    """Calculate nth Fibonacci number with lru_cache."""
    if n <= 1:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

# Test
test_memo = [fib_memo(n) for n in range(10)]
test_lru = [fib_lru(n) for n in range(10)]
print(f"First 10 Fibonacci numbers (memoized): {test_memo}")
print(f"First 10 Fibonacci numbers (lru_cache): {test_lru}")

3.3. Bottom-up Approach

@timing_decorator
def fib_bottom_up(n: int) -> int:
    """Calculate nth Fibonacci number iteratively."""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Test
test_bottom_up = [fib_bottom_up(n) for n in range(10)]
print(f"First 10 Fibonacci numbers (bottom-up): {test_bottom_up}")

4. Grid Problems

4.1. Path Finding

@timing_decorator
def count_paths(grid: List[List[int]]) -> int:
    """
    Count paths from top-left to bottom-right in a grid.
    Can only move right or down. 0 represents blocked cell.
    """
    if not grid or not grid[0]:
        return 0
        
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    
    # Initialize first cell
    dp[0][0] = 1 if grid[0][0] else 0
    
    # Initialize first row
    for j in range(1, cols):
        if grid[0][j]:
            dp[0][j] = dp[0][j-1]
            
    # Initialize first column
    for i in range(1, rows):
        if grid[i][0]:
            dp[i][0] = dp[i-1][0]
    
    # Fill rest of the grid
    for i in range(1, rows):
        for j in range(1, cols):
            if grid[i][j]:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[-1][-1]

# Test
test_grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
print(f"Paths in test grid: {count_paths(test_grid)}")

5. String Problems

5.1. Longest Common Subsequence

@timing_decorator
def lcs(text1: str, text2: str) -> str:
    """Find longest common subsequence between two strings."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build length table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Reconstruct the subsequence
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
            
    return ''.join(reversed(result))

# Test
s1, s2 = "ABCDGH", "AEDFHR"
print(f"LCS of {s1} and {s2}: {lcs(s1, s2)}")

6. Exercises

Here are some practice problems to work through:

  1. Coin Change Problem
  2. Knapsack Problem
  3. Edit Distance
  4. Maximum Subarray
  5. Longest Increasing Subsequence

6.1. Solution: Coin Change

@timing_decorator
def coin_change(coins: List[int], amount: int) -> int:
    """
    Find minimum number of coins needed to make amount.
    Returns -1 if amount cannot be made.
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Test
test_coins = [1, 2, 5]
test_amount = 11
print(f"Minimum coins needed for {test_amount}: {coin_change(test_coins, test_amount)}")

7. Running the Examples

To run all examples: 

if __name__ == '__main__':
    print("\n=== Testing Fibonacci Implementations ===")
    n = 35
    fib_recursive(n)
    fib_memo(n)
    fib_lru(n)
    fib_bottom_up(n)
    
    print("\n=== Testing Grid Pathfinding ===")
    test_grid = [[1,1,1],[1,0,1],[1,1,1]]
    count_paths(test_grid)
    
    print("\n=== Testing String Problems ===")
    lcs("ABCDGH", "AEDFHR")
    
    print("\n=== Testing Coin Change ===")
    coin_change([1,2,5], 11)

8. Resources

9. Notes

This tutorial provides a foundation in dynamic programming. Key takeaways:

  1. Always look for overlapping subproblems
  2. Try to formulate recurrence relations
  3. Consider space-time tradeoffs
  4. Practice with variations of these patterns