Dynamic Programming Patterns

After solving hundreds of LeetCode problems, I've identified several recurring patterns in dynamic programming problems that help me approach new challenges more systematically.

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique for solving problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations.

Key DP Patterns

1. Fibonacci Sequence Pattern

This is the simplest DP pattern, where each state depends on the previous two states.

Example Problems:

• Fibonacci Number

• Climbing Stairs

• House Robber

Implementation Approach:

`python
def fibonacci(n):
    if n <= 1:
        return 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]

2. 0/1 Knapsack Pattern

This pattern is used when you need to make decisions to include or exclude items to maximize some value within constraints.

Example Problems:

• 0/1 Knapsack

• Subset Sum

• Partition Equal Subset Sum

Implementation Approach:

`python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w-weights[i-1]],
                    dp[i-1][w]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

3. Longest Common Subsequence Pattern

Used for problems involving finding common elements or patterns between sequences.

Example Problems:

• Longest Common Subsequence

• Longest Increasing Subsequence

• Edit Distance

Implementation Approach:

`python
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    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])
    
    return dp[m][n]

4. Matrix Chain Multiplication Pattern

Used for problems where you need to find the optimal way to perform a series of operations.

Example Problems:

• Matrix Chain Multiplication

• Burst Balloons

• Minimum Cost Tree From Leaf Values

5. Kadane's Algorithm Pattern

Used for problems involving finding optimal subarrays or subsequences.

Example Problems:

• Maximum Subarray

• Maximum Sum Circular Subarray

Implementation Approach:

`python
def max_subarray(nums):
    current_sum = max_sum = nums[0]
    
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Recognizing DP Problems

A problem might be solvable with DP if it has these characteristics:

1. Optimal substructure (optimal solution contains optimal solutions to subproblems)

2. Overlapping subproblems (same subproblems solved multiple times)

3. Usually asks for optimization (maximum/minimum/longest/shortest)

Approach to Solving DP Problems

1. Define the state (what does each entry in your DP table represent?)

2. Formulate the recurrence relation (how do states relate to each other?)

3. Identify the base cases

4. Decide on a bottom-up or top-down approach

5. Optimize for space if needed

By recognizing these patterns, you can develop a more systematic approach to solving DP problems rather than treating each one as completely new.