Dynamic Programming Patterns and Templates

Introduction to Dynamic Programming

Dynamic Programming solves problems by breaking them into smaller subproblems, solving each subproblem once, and storing results for reuse. It is typically used for optimization problems (e.g., maximizing/minimizing a value) and involves two main approaches:

• Memoization: Top-down, recursive approach with caching.
• Tabulation: Bottom-up, iterative approach using arrays/tables.

Common DP Patterns

Below are the major DP patterns, their characteristics, and templates for solving them.

1. 1D Dynamic Programming

Description: Problems where the state is represented by a single variable (e.g., index or count). Typically involves a single array for storing intermediate results.

Examples:

• Fibonacci sequence
• Climbing Stairs (LeetCode #70)
• House Robber (LeetCode #198)

Memoization Template:

def solve(n):
    memo = {}
    def dp(i):
        if i in memo:
            return memo[i]
        if i <= base_case_value:  # Base case
            return base_case_result
        memo[i] = transition_function(dp(i-1), dp(i-2), ...)  # Recurrence relation
        return memo[i]
    return dp(n)

Tabulation Template:

def solve(n):
    if n <= base_case_value:
        return base_case_result
    dp = [0] * (n + 1)  # Initialize 1D array
    dp[0] = base_case_0  # Set base cases
    dp[1] = base_case_1
    for i in range(2, n + 1):
        dp[i] = transition_function(dp[i-1], dp[i-2], ...)  # Fill table
    return dp[n]

Key Points:

• State: dp[i] represents the solution for the subproblem at index i.
• Transition: Relates dp[i] to previous states (e.g., dp[i] = dp[i-1] + dp[i-2]).