Introduction to Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic paradigm for solving optimization problems by breaking them down into simpler overlapping subproblems and storing the results to avoid redundant computations. The term "dynamic programming" was coined by Richard Bellman in the 1950s, though it has nothing to do with programming in the modern sense—it refers to the mathematical optimization method.

DP is particularly effective for problems that exhibit two key properties: overlapping subproblems and optimal substructure. It transforms exponential-time recursive solutions into polynomial-time algorithms, making it one of the most important techniques in competitive programming and algorithm design.

When to Use Dynamic Programming

Consider DP when you encounter:

• Optimization problems (minimize/maximize)
• Counting problems (how many ways)
• Decision problems (yes/no with conditions)
• Problems that can be broken into similar subproblems
• Recursive solutions with repeated calculations

Core Principles

Dynamic Programming is built on two fundamental principles:

1. Overlapping Subproblems: The problem can be broken down into subproblems that are reused multiple times. Instead of recomputing solutions, we store them.
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems. This allows us to build solutions from smaller optimal solutions.

Example: Fibonacci Numbers

The classic example demonstrates the power of DP. Without DP, computing Fibonacci numbers recursively has exponential time complexity:

# Naive recursive approach - O(2^n)
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# With DP (memoization) - O(n)
memo = {}
def fibonacci_dp(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_dp(n - 1) + fibonacci_dp(n - 2)
    return memo[n]

Memoization vs Tabulation

Dynamic Programming can be implemented in two ways: memoization (top-down) and tabulation (bottom-up). Both achieve the same goal of avoiding redundant computations but use different approaches.

Memoization (Top-Down Approach)

Memoization starts with the original problem and recursively breaks it down, storing results as we go. It's called "top-down" because we start at the top (the problem) and work our way down to base cases.

# Memoization example: Climbing Stairs
memo = {}
def climb_stairs_memo(n):
    """How many ways to climb n stairs (1 or 2 steps at a time)"""
    if n in memo:
        return memo[n]
    
    # Base cases
    if n == 0 or n == 1:
        return 1
    
    # Recursive case with memoization
    memo[n] = climb_stairs_memo(n - 1) + climb_stairs_memo(n - 2)
    return memo[n]

# Advantages:
# - Natural recursive structure
# - Only computes needed subproblems
# - Easy to understand

# Disadvantages:
# - Recursion overhead
# - Stack overflow risk for deep recursion
# - Less control over computation order

Tabulation (Bottom-Up Approach)

Tabulation builds solutions iteratively from the bottom up, starting with base cases and building up to the desired solution. It fills a table (usually an array) with solutions to all subproblems.

# Tabulation example: Climbing Stairs
def climb_stairs_tab(n):
    """Bottom-up approach using tabulation"""
    if n <= 1:
        return 1
    
    # Create table to store results
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case
    dp[1] = 1  # Base case
    
    # Fill table from bottom up
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# Advantages:
# - No recursion overhead
# - Better space optimization possible
# - Predictable memory access patterns
# - Can optimize space (only keep needed values)

# Disadvantages:
# - Computes all subproblems (even unused ones)
# - Less intuitive for some problems
# - Need to determine computation order

Space-Optimized Tabulation

Many DP problems can be optimized to use O(1) space instead of O(n):

# Space-optimized version
def climb_stairs_optimized(n):
    """O(1) space instead of O(n)"""
    if n <= 1:
        return 1
    
    prev2 = 1  # dp[i-2]
    prev1 = 1  # dp[i-1]
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

When to Use Each Approach

Common DP Patterns

Recognizing common DP patterns helps identify when and how to apply dynamic programming. Here are the most important patterns with detailed examples.

1. 1D DP (Linear DP)

Problems where the state depends on a single dimension. Often involves sequences or linear structures.

Pattern: Linear Sequence

# Template for 1D DP
def dp_1d(n):
    dp = [0] * (n + 1)
    dp[0] = base_case_0
    dp[1] = base_case_1
    
    for i in range(2, n + 1):
        dp[i] = combine(dp[i-1], dp[i-2], ...)
    
    return dp[n]

Example: Maximum Subarray Sum

def max_subarray_sum(arr):
    """Kadane's Algorithm - O(n) time, O(1) space"""
    max_sum = current_sum = arr[0]
    
    for i in range(1, len(arr)):
        # Either extend previous subarray or start new one
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# DP interpretation:
# dp[i] = maximum sum ending at index i
# dp[i] = max(arr[i], dp[i-1] + arr[i])

2. 2D DP (Grid/Matrix DP)

Problems involving two dimensions, often grids, matrices, or two sequences.

Pattern: Grid Paths

# Template for 2D DP
def dp_2d(m, n):
    dp = [[0] * n for _ in range(m)]
    
    # Initialize first row and column
    for i in range(m):
        dp[i][0] = base_case
    for j in range(n):
        dp[0][j] = base_case
    
    # Fill table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = combine(dp[i-1][j], dp[i][j-1], ...)
    
    return dp[m-1][n-1]

Example: Unique Paths

def unique_paths(m, n):
    """Number of unique paths from top-left to bottom-right"""
    dp = [[0] * n for _ in range(m)]
    
    # Base case: first row and column have only one path
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    # Fill table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# Space-optimized version (O(n) space)
def unique_paths_optimized(m, n):
    prev = [1] * n
    for i in range(1, m):
        curr = [1] * n
        for j in range(1, n):
            curr[j] = prev[j] + curr[j-1]
        prev = curr
    return prev[n-1]

3. Knapsack Problems

Classic optimization problems involving selecting items with constraints.

0/1 Knapsack

def knapsack_01(weights, values, capacity):
    """0/1 Knapsack: Each item can be used at most once"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            
            # Take item i (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]

# Space-optimized (1D array)
def knapsack_01_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Iterate backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

Unbounded Knapsack

def unbounded_knapsack(weights, values, capacity):
    """Unbounded: Each item can be used unlimited times"""
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(
                    dp[w],
                    dp[w - weights[i]] + values[i]
                )
    
    return dp[capacity]

4. Longest Common Subsequence (LCS)

def longest_common_subsequence(s1, s2):
    """Find length of longest common subsequence"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

def lcs_reconstruct(s1, s2, dp):
    """Reconstruct the actual LCS string"""
    i, j = len(s1), len(s2)
    lcs = []
    
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            lcs.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs))

5. Edit Distance (Levenshtein Distance)

def edit_distance(s1, s2):
    """Minimum operations to transform s1 into s2
    Operations: insert, delete, replace"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # Delete
                    dp[i][j-1],      # Insert
                    dp[i-1][j-1]     # Replace
                )
    
    return dp[m][n]

6. Interval DP

Problems involving intervals or ranges, often solved by considering all possible splits.

# Template for interval DP
def interval_dp(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    
    # Length 1 intervals
    for i in range(n):
        dp[i][i] = base_case
    
    # Length 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = min_or_max(
                    dp[i][j],
                    combine(dp[i][k], dp[k+1][j])
                )
    
    return dp[0][n-1]

7. State Machine DP

Problems where you transition between different states.

# Example: Best Time to Buy and Sell Stock
def max_profit(prices):
    """State machine: hold, sold"""
    hold = float('-inf')  # State: holding stock
    sold = 0              # State: sold (not holding)
    
    for price in prices:
        # Can either keep holding or buy today
        hold = max(hold, sold - price)
        # Can either keep sold or sell today
        sold = max(sold, hold + price)
    
    return sold

Classic DP Problems

Here are detailed solutions to classic dynamic programming problems that appear frequently in interviews and competitions.

1. Fibonacci Sequence

The simplest DP problem, perfect for understanding the concept.

# Tabulation approach
def fibonacci(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# Space-optimized
def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

2. Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence where elements are in increasing order.

def longest_increasing_subsequence(arr):
    """O(n²) solution"""
    n = len(arr)
    dp = [1] * n  # Each element is a subsequence of length 1
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

def lis_optimized(arr):
    """O(n log n) solution using binary search"""
    tails = []
    
    for num in arr:
        # Binary search for the position to replace
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    
    return len(tails)

3. Coin Change

Find the minimum number of coins needed to make a target amount.

def coin_change_min(coins, amount):
    """Minimum coins to make amount"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins for amount 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

def coin_change_ways(coins, amount):
    """Number of ways to make amount"""
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use no coins
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

4. Longest Palindromic Subsequence

def longest_palindromic_subsequence(s):
    """Find length of longest palindromic subsequence"""
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Fill table for lengths 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    return dp[0][n-1]

5. Word Break

def word_break(s, word_dict):
    """Check if string can be segmented into dictionary words"""
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string can always be segmented
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break
    
    return dp[n]

6. House Robber

def house_robber(nums):
    """Maximum money without robbing adjacent houses"""
    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], dp[i-2] + nums[i])
    
    return dp[-1]

# Space-optimized
def house_robber_optimized(nums):
    prev2 = 0  # dp[i-2]
    prev1 = 0  # dp[i-1]
    
    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current
    
    return prev1

7. Decode Ways

def num_decodings(s):
    """Number of ways to decode a string (A=1, B=2, ..., Z=26)"""
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string has 1 way
    dp[1] = 1  # Single digit has 1 way (if not '0')
    
    for i in range(2, n + 1):
        # Single digit decode
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        
        # Two digit decode
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    
    return dp[n]

8. Partition Equal Subset Sum

def can_partition(nums):
    """Check if array can be partitioned into two equal sum subsets"""
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

DP Optimization Techniques

1. Space Optimization

Many 2D DP problems can be reduced to 1D or even O(1) space by recognizing that we only need previous values.

# Example: 2D → 1D optimization
# Original 2D DP
dp = [[0] * n for _ in range(m)]

# Optimized 1D DP (if we only need previous row)
prev = [0] * n
curr = [0] * n
for i in range(1, m):
    # Compute curr from prev
    prev = curr

2. State Compression

For problems with limited states, use bitmasks to represent states compactly.

# Example: Traveling Salesman Problem
def tsp_dp(graph):
    n = len(graph)
    # dp[mask][last] = minimum cost visiting cities in mask, ending at last
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at city 0
    
    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            for next_city in range(n):
                if mask & (1 << next_city):
                    continue
                new_mask = mask | (1 << next_city)
                dp[new_mask][next_city] = min(
                    dp[new_mask][next_city],
                    dp[mask][last] + graph[last][next_city]
                )
    
    return min(dp[(1 << n) - 1][i] + graph[i][0] for i in range(n))

3. Sliding Window Optimization

For problems where the recurrence only depends on a window of previous values.

# Example: Maximum sum of k consecutive elements
def max_sum_k_consecutive(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i-k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

How to Identify DP Problems

Recognizing when to use DP is crucial. Look for these indicators:

Problem Characteristics

• Optimization Problem: Asking for minimum, maximum, or optimal solution
• Counting Problem: "How many ways" or "number of possibilities"
• Decision Problem: "Is it possible" with constraints
• Subproblem Overlap: Same subproblems appear multiple times
• Optimal Substructure: Optimal solution contains optimal sub-solutions

Common Problem Types

• Sequence/Array problems (LIS, LCS, Edit Distance)
• Grid/Matrix problems (Unique Paths, Minimum Path Sum)
• String problems (Palindrome, Word Break, Interleaving)
• Tree problems (Binary Tree DP, Tree Diameter)
• Game theory (Nim, Game of Stones)

Step-by-Step Approach

1. Identify the State: What information do we need to track?
2. Define the Recurrence: How do we compute current state from previous states?
3. Base Cases: What are the smallest subproblems?
4. Fill the Table: Compute states in the correct order
5. Extract Solution: Get the answer from the DP table

Practice Problems

Here are recommended problems to practice dynamic programming:

Easy

• LeetCode 70: Climbing Stairs
• LeetCode 53: Maximum Subarray
• LeetCode 121: Best Time to Buy and Sell Stock
• LeetCode 198: House Robber
• LeetCode 746: Min Cost Climbing Stairs

Medium

• LeetCode 5: Longest Palindromic Substring
• LeetCode 62: Unique Paths
• LeetCode 64: Minimum Path Sum
• LeetCode 300: Longest Increasing Subsequence
• LeetCode 322: Coin Change
• LeetCode 416: Partition Equal Subset Sum
• LeetCode 1143: Longest Common Subsequence
• LeetCode 139: Word Break

Hard

• LeetCode 32: Longest Valid Parentheses
• LeetCode 72: Edit Distance
• LeetCode 85: Maximal Rectangle
• LeetCode 312: Burst Balloons
• LeetCode 887: Super Egg Drop
• LeetCode 115: Distinct Subsequences

Summary

Dynamic Programming is a powerful technique for solving optimization problems by breaking them into overlapping subproblems and storing solutions to avoid redundant computation.

Key takeaways:

• DP requires overlapping subproblems and optimal substructure
• Memoization (top-down) and tabulation (bottom-up) are two implementation approaches
• Common patterns include 1D DP, 2D DP, knapsack, interval DP, and state machine DP
• Space optimization can reduce memory usage significantly
• Practice recognizing DP problems by looking for optimization, counting, or decision problems
• Many problems can be solved by identifying the state, recurrence relation, and base cases

Mastery of dynamic programming opens doors to solving complex optimization problems efficiently and is essential for competitive programming and technical interviews.