Dynamic Programming

Dynamic Programming solves complex problems by breaking them down into simpler subproblems, storing solutions to avoid redundant calculations. It's applicable when problems have optimal substructure and overlapping subproblems.

When to Use

Problem asks for optimization (maximum, minimum, count)
Overlapping subproblems exist
Optimal substructure property holds
Problems with 'all possible ways' or 'count number of ways'

Common Patterns

1D DP

State depends on previous states in a linear fashion

Example: Fibonacci, house robber, climbing stairs

2D DP

State depends on two parameters

Example: Longest common subsequence, edit distance, unique paths

Knapsack

Choose items with constraints to optimize value

Example: 0/1 knapsack, coin change, partition problems

Code Templates

Python

# 1D DP template
def dp_1d(n):
    dp = [0] * (n + 1)
    # Base cases
    dp[0] = base_value_0
    dp[1] = base_value_1
    
    for i in range(2, n + 1):
        dp[i] = transition_function(dp, i)
    
    return dp[n]

# 2D DP template
def dp_2d(s1, s2):
    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] = base_value_i
    for j in range(n + 1):
        dp[0][j] = base_value_j
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if condition(s1[i-1], s2[j-1]):
                dp[i][j] = transition_match(dp, i, j)
            else:
                dp[i][j] = transition_no_match(dp, i, j)
    
    return dp[m][n]

# 0/1 Knapsack template
def knapsack(weights, values, capacity):
    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-1
            dp[i][w] = dp[i-1][w]
            
            # Take item i-1 if possible
            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]

C++

// 1D DP template
int dp1D(int n) {
    vector<int> dp(n + 1, 0);
    // Base cases
    dp[0] = baseValue0;
    dp[1] = baseValue1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = transitionFunction(dp, i);
    }
    
    return dp[n];
}

// 2D DP template
int dp2D(string s1, string s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // Base cases
    for (int i = 0; i <= m; i++) dp[i][0] = baseValueI;
    for (int j = 0; j <= n; j++) dp[0][j] = baseValueJ;
    
    // Fill DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (condition(s1[i-1], s2[j-1])) {
                dp[i][j] = transitionMatch(dp, i, j);
            } else {
                dp[i][j] = transitionNoMatch(dp, i, j);
            }
        }
    }
    
    return dp[m][n];
}

// 0/1 Knapsack template
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            // Don't take item i-1
            dp[i][w] = dp[i-1][w];
            
            // Take item i-1 if possible
            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];
}