Dynamic Programming Problems
Fibonacci Series (Bottom-Up and Top-Down)
Top-Down
int fib(int n, vector& dp) {
if (n <= 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
}
Bottom-Up
int fib(int n) {
vector dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Longest Common Subsequence
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
vector> dp(m + 1, vector(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]);
}
}
return dp[m][n];
}
Longest Increasing Subsequence
int lengthOfLIS(vector& nums) {
if (nums.empty()) return 0;
vector dp(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
}
}
return *max_element(dp.begin(), dp.end());
}
Edit Distance
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector> dp(m + 1, vector(n + 1, 0));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
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];
else dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
return dp[m][n];
}
Coin Change Problem
int coinChange(vector& coins, int amount) {
vector dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int coin : coins) {
if (i >= coin) dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
Knapsack Problem (0/1 Knapsack)
int knapsack(int W, vector& weights, vector& values) {
int n = weights.size();
vector> dp(n + 1, vector(W + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 1; w <= W; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
Unbounded Knapsack Problem
int unboundedKnapsack(int W, vector& weights, vector& values) {
vector dp(W + 1, 0);
for (int w = 1; w <= W; ++w) {
for (int i = 0; i < weights.size(); ++i) {
if (weights[i] <= w) dp[w] = max(dp[w], values[i] + dp[w - weights[i]]);
}
}
return dp[W];
}
Matrix Chain Multiplication
int matrixChainOrder(vector& dims) {
int n = dims.size();
vector> dp(n, vector(n, 0));
for (int len = 2; len < n; ++len) {
for (int i = 1; i < n - len + 1; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k <= j - 1; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]);
}
}
}
return dp[1][n - 1];
}
Longest Palindromic Subsequence
int longestPalindromeSubseq(string s) {
int n = s.size();
vector> dp(n, vector(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
Palindromic Substring
int countSubstrings(string s) {
int n = s.size(), count = 0;
vector> dp(n, vector(n, false));
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
count++;
}
}
}
return count;
}
Partition Problem (Subset Sum Problem)
bool canPartition(vector& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
sum /= 2;
vector dp(sum + 1, false);
dp[0] = true;
for (int num : nums) {
for (int i = sum; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[sum];
}
Minimum Path Sum in a Grid
int minPathSum(vector>& grid) {
int m = grid.size(), n = grid[0].size();
vector> dp(m, vector(n, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
Minimum Coin Change
int coinChange(vector& coins, int amount) {
vector dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int coin : coins) {
if (i >= coin) dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
Count All Possible Paths in a Grid
int countPaths(int m, int n) {
vector> dp(m, vector(n, 1));
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
Rod Cutting Problem
int cutRod(vector& price, int n) {
vector dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] = max(dp[i], price[j] + dp[i - j - 1]);
}
}
return dp[n];
}
Word Break Problem
bool wordBreak(string s, unordered_set& wordDict) {
vector dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && wordDict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
Find the Maximum Sum Increasing Subsequence
int maxSumIS(vector& arr) {
int n = arr.size();
vector dp(n);
dp[0] = arr[0];
for (int i = 1; i < n; ++i) {
dp[i] = arr[i];
for (int j = 0; j < i; ++j) {
if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);
}
}
return *max_element(dp.begin(), dp.end());
}
Maximum Subarray Sum (Kadane’s Algorithm)
int maxSubArray(vector& nums) {
int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.size(); ++i) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
House Robber Problem
int rob(vector& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}