Understanding Dynamic Programming

Dynamic Programming (DP) works on problems that have:

Fibonacci Sequence - Introduction to DP

Let's start with the classic Fibonacci example to understand DP concepts:

Naive Recursive Solution (Inefficient)

int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n-1) + fibRecursive(n-2);
}
// Time Complexity: O(2^n) - Very slow!
                    

Memoization (Top-Down DP)

#include <vector>

vector<int> memo;

int fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // Already computed
    
    memo[n] = fibMemo(n-1) + fibMemo(n-2);
    return memo[n];
}

int fibonacci(int n) {
    memo.assign(n+1, -1);
    return fibMemo(n);
}
// Time Complexity: O(n), Space: O(n)
                    

Tabulation (Bottom-Up DP)

int fibDP(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}
// Time Complexity: O(n), Space: O(n)

// Space-optimized version
int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}
// Time Complexity: O(n), Space: O(1)
                    

Coin Change Problem

Find the minimum coins needed to make a given amount:

#include <vector>
#include <algorithm>

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1); // Initialize with impossible value
    dp[0] = 0; // Base case: 0 coins needed for amount 0
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

// Count number of ways to make amount
int coinChangeWays(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1; // One way to make 0: use no coins
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    
    cout << "Min coins needed: " << coinChange(coins, amount) << endl; // 2 (3+3)
    cout << "Ways to make amount: " << coinChangeWays(coins, amount) << endl;
    
    return 0;
}
                    

0/1 Knapsack Problem

Maximize value in a knapsack with weight constraint:

#include <vector>
#include <algorithm>

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                // Either take item or don't take it
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w]; // Can't take this item
            }
        }
    }
    
    return dp[n][W];
}

// Space-optimized version (1D array)
int knapsackOptimized(vector<int>& weights, vector<int>& values, int W) {
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < weights.size(); i++) {
        // Iterate backwards to avoid using updated values
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}
                    

Longest Increasing Subsequence (LIS)

Find the length of the longest increasing subsequence:

#include <vector>
#include <algorithm>

// O(n^2) DP solution
int lisDP(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i] = length of LIS ending at i
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return *max_element(dp.begin(), dp.end());
}

// O(n log n) Binary Search solution
int lisBinarySearch(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

// Reconstruct the actual LIS
vector<int> reconstructLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> parent(n, -1);
    
    int maxLength = 1, maxIndex = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            maxIndex = i;
        }
    }
    
    // Reconstruct LIS
    vector<int> lis;
    for (int i = maxIndex; i != -1; i = parent[i]) {
        lis.push_back(nums[i]);
    }
    
    reverse(lis.begin(), lis.end());
    return lis;
}
                    

Edit Distance (Levenshtein Distance)

Minimum operations to transform one string to another:

int editDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    // Initialize base cases
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; // Delete all characters
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // Insert all characters
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[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];
}

int main() {
    string word1 = "horse";
    string word2 = "ros";
    cout << "Edit distance: " << editDistance(word1, word2) << endl; // 3
    
    return 0;
}
                    

Common DP Patterns

DP Strategy