Dynamic Programming
Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems and storing the solutions to those subproblems to avoid redundant computations. It is particularly useful for problems where the solution can be recursively defined in terms of solutions to overlapping subproblems. By efficiently storing and reusing intermediate results, DP can drastically improve the efficiency of algorithms that would otherwise be computationally expensive. This guide explores the foundational concepts of Dynamic Programming, its key components like memoization and tabulation, and provides insights into applying DP to various problem types, ranging from sequence alignment and shortest path calculations to resource allocation and scheduling problems.
0/1 Knapsack Problem
This problem is a classic dynamic programming problem.
Here's the Solution class for the "0/1 Knapsack Problem" in C++:
class Solution {
public:
int knapsack(int W, vector<int>& weights, vector<int>& values) {
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 = 0; w <= W; ++w) {
if (weights[i - 1] <= w) {
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];
}
}
}
return dp[n][W];
}
};
Subset Sum
This problem is a variation of the 0/1 knapsack problem.
Here's the Solution class for the "Subset Sum" problem in C++:
class Solution {
public:
bool subsetSum(vector<int>& nums, int S) {
int n = nums.size();
vector<vector<bool>> dp(n + 1, vector<bool>(S + 1, false));
for (int i = 0; i <= n; ++i) {
dp[i][0] = true;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= S; ++j) {
if (nums[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][S];
}
};
Coin Change
This question is part of Leetcode problems, question no. 322.
Here's the Solution class for the "Coin Change" problem in C++:
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 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];
}
};
Rod Cutting Problem
Here's the Solution class for the "Rod Cutting Problem" in C++:
#include <vector>
#include <algorithm>
#include <climits>
class Solution {
public:
int rodCutting(int length, vector<int>& prices) {
vector<int> dp(length + 1, 0);
for (int i = 1; i <= length; ++i) {
int maxProfit = INT_MIN;
for (int j = 1; j <= i; ++j) {
maxProfit = max(maxProfit, prices[j - 1] + dp[i - j]);
}
dp[i] = maxProfit;
}
return dp[length];
}
};
Nth Tribonacci Number
This question is part of Leetcode problems, question no. 1137.
Here's the Solution class for the "Nth Tribonacci Number" problem in C++:
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int dp[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
};
Climbing Stairs
This question is part of Leetcode problems, question no. 70.
Here's the Solution class for the "Climbing Stairs" problem in C++:
class Solution {
public:
int climbStairs(int n) {
if (n == 0 || n == 1) return 1;
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
House Robber
This question is part of Leetcode problems, question no. 198.
Here's the Solution class for the "House Robber" problem in C++:
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector<int> 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];
}
};
Longest Common Subsequence
This question is part of Leetcode problems, question no. 1143.
Here's the Solution class for the "Longest Common Subsequence" problem in C++:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
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]);
}
}
}
return dp[m][n];
}
};
Longest Increasing Subsequence
This question is part of Leetcode problems, question no. 300.
Here's the Solution class for the "Longest Increasing Subsequence" problem in C++:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int maxLength = 1;
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);
}
}
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
};
Equal Subset Sum Partition
This question is part of Leetcode problems, question no. 416.
Here's the Solution class for the "Equal Subset Sum Partition" problem in C++:
class Solution {
public:
bool canPartition(vector<int>& nums) {
int totalSum = accumulate(nums.begin(), nums.end(), 0);
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; --j) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
};
Practice these questions diligently to enhance your problem-solving skills. Remember, consistent practice is key to mastering these concepts. If you find yourself stuck or in need of further clarification, be sure to check out video references and tutorials to clear up any doubts.
Top comments (0)