Dynamic Programming
Introduction to Dynamic Programming
Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid redundant calculations, making it much more efficient than naive recursive approaches.
DP problems have two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems are solved multiple times).
Basic DP: Fibonacci with Memoization
The Fibonacci sequence is a perfect introduction to DP. Compare the naive recursive approach with memoized and bottom-up solutions.
Fibonacci: Recursion vs DP
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
class Fibonacci {
public:
// Naive recursion - O(2^n)
long long fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// Top-down DP (Memoization) - O(n)
long long fibMemo(int n, vector<long long>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Bottom-up DP (Tabulation) - O(n)
long long fibDP(int n) {
if (n <= 1) return n;
vector<long long> 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];
}
// Space-optimized DP - O(1) space
long long fibOptimized(int n) {
if (n <= 1) return n;
long long prev2 = 0, prev1 = 1, current;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
void comparePerformance(int n) {
cout << "Computing Fibonacci(" << n << "):" << endl;
// Test memoization
vector<long long> memo(n + 1, -1);
auto start = high_resolution_clock::now();
long long result1 = fibMemo(n, memo);
auto end = high_resolution_clock::now();
auto duration1 = duration_cast<microseconds>(end - start);
cout << "Memoization: " << result1 << " (Time: " << duration1.count() << " μs)" << endl;
// Test bottom-up DP
start = high_resolution_clock::now();
long long result2 = fibDP(n);
end = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(end - start);
cout << "Bottom-up DP: " << result2 << " (Time: " << duration2.count() << " μs)" << endl;
// Test optimized
start = high_resolution_clock::now();
long long result3 = fibOptimized(n);
end = high_resolution_clock::now();
auto duration3 = duration_cast<microseconds>(end - start);
cout << "Optimized: " << result3 << " (Time: " << duration3.count() << " μs)" << endl;
}
};
int main() {
Fibonacci fib;
fib.comparePerformance(40);
return 0;
}Memoization and tabulation dramatically improve performance by avoiding redundant calculations.
Classic DP: 0/1 Knapsack Problem
The knapsack problem is fundamental in DP. Given items with weights and values, find the maximum value that can fit in a knapsack of given capacity.
0/1 Knapsack Implementation
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Knapsack {
public:
// Recursive solution with memoization
int knapsackMemo(int capacity, vector<int>& weights, vector<int>& values,
int n, vector<vector<int>>& memo) {
// Base case
if (n == 0 || capacity == 0) {
return 0;
}
// Check if already computed
if (memo[n][capacity] != -1) {
return memo[n][capacity];
}
// If weight of nth item is more than capacity, it cannot be included
if (weights[n - 1] > capacity) {
memo[n][capacity] = knapsackMemo(capacity, weights, values, n - 1, memo);
} else {
// Return maximum of two cases:
// 1. nth item included
// 2. nth item not included
int include = values[n - 1] + knapsackMemo(capacity - weights[n - 1],
weights, values, n - 1, memo);
int exclude = knapsackMemo(capacity, weights, values, n - 1, memo);
memo[n][capacity] = max(include, exclude);
}
return memo[n][capacity];
}
// Bottom-up DP solution
int knapsackDP(int capacity, vector<int>& weights, vector<int>& values, int n) {
// Create DP table
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// Build table dp[][] in bottom-up manner
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// Take maximum of including or excluding current item
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]);
} else {
// Cannot include current item
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// Space-optimized version
int knapsackOptimized(int capacity, vector<int>& weights, vector<int>& values, int n) {
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
// Traverse in reverse to avoid using updated values
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// Function to print which items are selected
void printSelectedItems(int capacity, vector<int>& weights, vector<int>& values, int n) {
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// Build DP table
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
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];
}
}
}
// Backtrack to find selected items
int res = dp[n][capacity];
int w = capacity;
cout << "Selected items: ";
for (int i = n; i > 0 && res > 0; i--) {
if (res != dp[i - 1][w]) {
cout << "Item " << i << " (weight: " << weights[i - 1]
<< ", value: " << values[i - 1] << ") ";
res -= values[i - 1];
w -= weights[i - 1];
}
}
cout << endl;
}
};
int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50;
int n = values.size();
Knapsack ks;
// Test memoization approach
vector<vector<int>> memo(n + 1, vector<int>(capacity + 1, -1));
cout << "Maximum value (Memoization): "
<< ks.knapsackMemo(capacity, weights, values, n, memo) << endl;
// Test bottom-up DP
cout << "Maximum value (Bottom-up DP): "
<< ks.knapsackDP(capacity, weights, values, n) << endl;
// Test optimized version
cout << "Maximum value (Optimized): "
<< ks.knapsackOptimized(capacity, weights, values, n) << endl;
// Print selected items
ks.printSelectedItems(capacity, weights, values, n);
return 0;
}The knapsack DP table stores maximum values for different capacities and item subsets.
Longest Common Subsequence (LCS)
LCS finds the longest subsequence common to two sequences. It's used in diff algorithms, DNA analysis, and plagiarism detection.
Longest Common Subsequence
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class LCS {
public:
// Find length of LCS
int lcsLength(string text1, string text2) {
int m = text1.length();
int n = text2.length();
// Create DP table
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Build the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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];
}
// Find actual LCS string
string lcsString(string text1, string text2) {
int m = text1.length();
int n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Build the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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]);
}
}
}
// Backtrack to construct LCS
string lcs = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i - 1] == text2[j - 1]) {
lcs = text1[i - 1] + lcs;
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs;
}
// Space-optimized LCS (only length)
int lcsOptimized(string text1, string text2) {
int m = text1.length();
int n = text2.length();
// Use only two rows
vector<int> prev(n + 1, 0);
vector<int> curr(n + 1, 0);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = max(prev[j], curr[j - 1]);
}
}
prev = curr;
}
return curr[n];
}
void printDPTable(string text1, string text2) {
int m = text1.length();
int n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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]);
}
}
}
cout << "DP Table:" << endl;
cout << " ";
for (char c : text2) cout << " " << c;
cout << endl;
for (int i = 0; i <= m; i++) {
if (i == 0) cout << " ";
else cout << text1[i - 1] << " ";
for (int j = 0; j <= n; j++) {
cout << " " << dp[i][j];
}
cout << endl;
}
}
};
int main() {
LCS lcs;
string text1 = "ABCDGH";
string text2 = "AEDFHR";
cout << "Text 1: " << text1 << endl;
cout << "Text 2: " << text2 << endl;
cout << endl;
cout << "LCS Length: " << lcs.lcsLength(text1, text2) << endl;
cout << "LCS String: " << lcs.lcsString(text1, text2) << endl;
cout << "LCS Length (Optimized): " << lcs.lcsOptimized(text1, text2) << endl;
cout << endl;
lcs.printDPTable(text1, text2);
return 0;
}LCS builds a table where dp[i][j] represents LCS length of first i chars of text1 and first j chars of text2.