Dynamic Programming Pattern

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid recomputing them, making it highly efficient for problems with overlapping subproblems and optimal substructure.

When to Use This Pattern

• Problems with overlapping subproblems
• Problems with optimal substructure (optimal solution contains optimal solutions to subproblems)
• Optimization problems (maximize or minimize something)
• Counting problems (how many ways to...)
• Problems that can be solved recursively but are inefficient

Key Concepts

1. Overlapping Subproblems

The problem can be broken down into subproblems which are reused several times. For example, in Fibonacci, F(5) = F(4) + F(3), and F(4) = F(3) + F(2), so F(3) is computed multiple times.

2. Optimal Substructure

An optimal solution to the problem contains optimal solutions to subproblems. For example, the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C.

3. Two Approaches

• Top-Down (Memoization): Start with the main problem and recursively solve subproblems, storing results in a memo table.
• Bottom-Up (Tabulation): Start with the smallest subproblems and build up to the main problem using a table.

Visual Representation - Fibonacci DP

Common DP Patterns

• Fibonacci Numbers: F(n) = F(n-1) + F(n-2)
• 0/1 Knapsack: Choose items with weight and value constraints
• Longest Common Subsequence (LCS): Find longest common subsequence between two strings
• Longest Increasing Subsequence (LIS): Find longest increasing subsequence
• Subset Sum: Check if a subset sums to a target

Algorithm Section

Top-Down Approach (Memoization)

function dp_topdown(n, memo):
    if n in memo:
        return memo[n]
    
    if base_case(n):
        result = base_value
    else:
        result = combine(dp_topdown(subproblem1, memo),
                         dp_topdown(subproblem2, memo))
    
    memo[n] = result
    return result

Bottom-Up Approach (Tabulation)

function dp_bottomup(n):
    dp = array of size n+1
    dp[0] = base_value
    
    for i from 1 to n:
        dp[i] = combine(dp[subproblem1], dp[subproblem2])
    
    return dp[n]

Fibonacci Example in C++

#include <vector>
#include <unordered_map>
using namespace std;

// Top-Down (Memoization)
unordered_map<int, int> memo;

int fib_memo(int n) {
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    if (n <= 1) {
        return n;
    }
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

// Bottom-Up (Tabulation)
int fib_tab(int n) {
    if (n <= 1) {
        return n;
    }
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

0/1 Knapsack Pattern in C++

#include <vector>
#include <algorithm>
using namespace std;

int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    // dp[i][w] = maximum value with first i items and capacity w
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                // Choose max of: don't take item, or take item
                dp[i][w] = max(
                    dp[i-1][w],  // Don't take item i
                    dp[i-1][w - weights[i-1]] + values[i-1]  // Take item i
                );
            } else {
                // Can't take item i (too heavy)
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][capacity];
}