Dynamic Programming¶
Dynamic Programming (DP) is a technique used to solve problems by breaking them into overlapping subproblems and storing their results to avoid recomputation.
Key ideas behind DP:
- Overlapping subproblems
- Optimal substructure
- Memoization (Top-Down)
- Tabulation (Bottom-Up)
- Space Optimization
1. Intro to DP¶
/*
QUESTION:-
Find the nth fibonacci number.
Approach:
1. We can use dynamic programming to calculate the nth Fibonacci number.
2. We define a helper function fibo(n, dp) that calculates the nth Fibonacci number using memoization.
3. The function checks if the nth Fibonacci number is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the nth Fibonacci number by recursively calling fibo(n-1, dp) and fibo(n-2, dp) and stores the result in dp.
5. The base cases are when n is 0 or 1, in which case the function returns n.
6. In the main function, we take the input for n and create a dp array of size n+1 initialized with -1.
7. We then call the fibo function passing n and the dp array as arguments.
8. Finally, we print the value of dp[n], which represents the nth Fibonacci number.
Complexity Analysis:
- The time complexity of the fibo function is O(n) because we are calculating and storing the Fibonacci numbers from 0 to n.
- The space complexity is also O(n) to store the dp array.
*/
// Memoization
int fibo(int n, vector<int>& dp) {
if (n == 0 || n == 1)
return dp[n] = n;
if (dp[n] != -1)
return dp[n];
return dp[n] = fibo(n - 1, dp) + fibo(n - 2, dp);
}
// Tabulation
int fiboTab(int 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];
}
int main() {
int n;
cin >> n;
vector<int> dp(n + 1, -1);
fibo(n, dp);
cout << dp[n];
return 0;
}
2. 1D DP¶
/*
QUESTION:-
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Approach:
1. We can use dynamic programming with memoization to calculate the number of distinct ways to climb the staircase.
2. We define a helper function fmemo(n, dp) that calculates the number of distinct ways to climb n steps using memoization.
3. The function checks if the number of ways to climb n steps is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the number of ways to climb n steps by recursively calling fmemo(n-1, dp) and fmemo(n-2, dp) and stores the result in dp.
5. The base cases are when n is 1 or 2, in which case the function returns n.
6. In the main function climbStairs(n), we check if n is 1 or 2. If yes, we directly return n as the number of distinct ways to climb.
7. Otherwise, we create a dp array of size n+1 initialized with -1 and call the fmemo function passing n and the dp array as arguments.
Complexity Analysis:
- The time complexity of the fmemo function is O(n) because we are calculating and storing the number of ways to climb n steps.
- The space complexity is also O(n) to store the dp array.
*/
// Memoization
int fmemo(int n, vector<int>& dp) {
if (n == 1 || n == 2)
return dp[n] = n;
if (dp[n] != -1)
return dp[n];
return dp[n] = fmemo(n - 1, dp) + fmemo(n - 2, dp);
}
// Tabulation
int ftab(int n){
vector<int> dp(n+1);
dp[1] = 1, dp[2] = 2;
for(int i=3; i<=n; i++)
dp[i] = dp[i-1]+dp[i-2];
return dp[n];
}
// Space Optimization
int fopt(int n){
int p1 = 1, p2 = 2, ans = 0;
for(int i=3; i<=n; i++){
ans = p1+p2;
p1 = p2, p2 = ans;
}
return ans;
}
int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
return fopt(n);
}
/*
QUESTION:-
Geek wants to climb from the 0th stair to the (n-1)th stair. At a time, the Geek can climb either one or two steps.
A height[N] array is also given. Whenever the geek jumps from stair i to stair j, the energy consumed in the jump is abs(height[i] - height[j]), where abs() means the absolute difference.
Return the minimum energy that can be used by the Geek to jump from stair 0 to stair N-1.
Approach:
1. We can use dynamic programming with memoization to find the minimum energy required to jump from the 0th stair to the (n-1)th stair.
2. We define a helper function fmemo(i, h, dp) that calculates the minimum energy required to jump from the 0th stair to the ith stair using memoization.
3. The function checks if the minimum energy for the ith stair is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the minimum energy by taking two possible jumps - either from (i-1)th stair or from (i-2)th stair - and stores the result in dp[i].
5. The base case is when i is 0, in which case the function returns 0 as the Geek is already at the 0th stair.
6. In the main function minimumEnergy(height, n), we create a dp array of size n initialized with -1 and call the fmemo function passing n-1 (last stair), the height array, and the dp array as arguments.
Complexity Analysis:
- The time complexity of the fmemo function is O(n) because we are calculating and storing the minimum energy for each stair.
- The space complexity is also O(n) to store the dp array.
*/
// Memoization
int fmemo(int i, vector<int>& h, vector<int>& dp) {
if (i == 0)
return dp[i] = 0;
if (dp[i] != -1)
return dp[i];
int s1 = INT_MAX, s2 = INT_MAX;
if (i - 1 >= 0)
s1 = fmemo(i - 1, h, dp) + abs(h[i - 1] - h[i]);
if (i - 2 >= 0)
s2 = fmemo(i - 2, h, dp) + abs(h[i - 2] - h[i]);
return dp[i] = min(s1, s2);
}
// Tabulation
int ftab(int n, vector<int>& h){
vector<int> dp(n);
dp[0] = 0;
for(int i=1; i<n; i++){
int s1 = INT_MAX, s2 = INT_MAX;
if(i-1>=0) s1 = dp[i-1]+abs(h[i-1]-h[i]);
if(i-2>=0) s2 = dp[i-2]+abs(h[i-2]-h[i]);
dp[i] = min(s1,s2);
}
return dp[n-1];
}
// Space Optimized
int fopt(int n, vector<int>& h){
int p1 = 0, p2 = 0, ans = 0;
for(int i=1; i<n; i++){
int s1 = INT_MAX, s2 = INT_MAX;
if(i-1>=0) s1 = p1+abs(h[i-1]-h[i]);
if(i-2>=0) s2 = p2+abs(h[i-2]-h[i]);
ans = min(s1,s2);
p2 = p1; p1 = ans;
}
return ans;
}
int minimumEnergy(vector<int>& height, int n) {
return fopt(n, height);
}
/*
QUESTION:-
Geek wants to climb from the 0th stair to the (n-1)th stair. At a time, the Geek can climb k steps.
A height[N] array is also given. Whenever the geek jumps from stair i to stair j, the energy consumed in the jump is abs(height[i] - height[j]), where abs() means the absolute difference.
Return the minimum energy that can be used by the Geek to jump from stair 0 to stair N-1.
Example:
Input:
4 2
10 40 30 10
Output:
40
Explanation:
For 'n' = 4, 'k' = 2, height = {10, 40, 30, 10}
Initially, we are present at stone 1 having height 10. We can reach stone 3 as 'k' is 2. So, the cost incurred is |10 - 30| = 20.
Now, we are present at stone 3, we can reach stone 4 as 'k' is 2. So, the cost incurred is |30 - 10| = 20. So, the total cost is 40. We can show any other path will lead to greater cost.
Approach:
1. We can use dynamic programming with memoization to find the minimum energy required to jump from the 0th stair to the (n-1)th stair.
2. We define a helper function fmemo(i, k, h, dp) that calculates the minimum energy required to jump from the 0th stair to the ith stair using memoization.
3. The function checks if the minimum energy for the ith stair is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the minimum energy by considering all possible jumps from i-j (where j varies from 1 to k) and stores the result in dp[i].
5. The base case is when i is 0, in which case the function returns 0 as the Geek is already at the 0th stair.
6. In the main function minimizeCost(n, k, height), we create a dp array of size n initialized with -1 and call the fmemo function passing n-1 (last stair), k, the height array, and the dp array as arguments.
Complexity Analysis:
- The time complexity of the fmemo function is O(n*k) because we are calculating and storing the minimum energy for each stair and considering k possible jumps at each stair.
- The space complexity is also O(n) to store the dp array.
*/
// Memoization
int fmemo(int i, int k, vector<int>& h, vector<int>& dp) {
if (i == 0)
return dp[i] = 0;
if (dp[i] != -1)
return dp[i];
int ans = INT_MAX, temp = INT_MAX;
for (int j = 1; j <= k; j++) {
if (i - j >= 0)
temp = fmemo(i - j, k, h, dp) + abs(h[i] - h[i - j]);
ans = min(ans, temp);
}
return dp[i] = ans;
}
// Tabulation
int ftab(int i, int k, vector<int>& h){
int n = h.size();
vector<int> dp(n,INT_MAX);
dp[0] = 0;
int temp = INT_MAX;
for(int i=1; i<n; i++){
for(int j=1; j<=k; j++){
if(i-j >= 0) temp = dp[i-j]+abs(h[i]-h[i-j]);
dp[i] = min(dp[i],temp);
}
}
return dp[n-1];
}
int minimizeCost(int n, int k, vector<int>& height) {
vector<int> dp(n, -1);
return fmemo(n - 1, k, height, dp);
}
/*
QUESTION:-
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Approach:
1. We can use dynamic programming with memoization to solve this problem.
2. We define a helper function fmemo(i, nums, dp) that calculates the maximum amount of money that can be robbed from the 0th to the ith house using memoization.
3. The function checks if the maximum amount for the ith house is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the maximum amount by considering two options:
a) Rob the current house and add the money with the maximum amount from the (i-2)th house (since adjacent houses cannot be robbed).
b) Skip the current house and take the maximum amount from the (i-1)th house.
5. The base case is when i is less than 0, in which case the function returns 0 as there are no houses to rob.
6. In the main function rob(nums), we create a dp array of size n initialized with -1 and call the fmemo function passing n-1 (last house), the nums array, and the dp array as arguments.
Complexity Analysis:
- The time complexity of the fmemo function is O(n) because we are calculating the maximum amount for each house only once and storing it in the dp array.
- The space complexity is also O(n) to store the dp array.
*/
//Memoization
int fmemo(int i, vector<int>& nums, vector<int>& dp) {
if (i < 0)
return 0;
if (i == 0)
return dp[i] = nums[i];
if (dp[i] != -1)
return dp[i];
int take = nums[i] + fmemo(i - 2, nums, dp);
int notake = fmemo(i - 1, nums, dp);
return dp[i] = max(take, notake);
}
//Tabulation
int ftab(int n, vector<int>& nums){
vector<int> dp(n);
dp[0] = nums[0];
for(int i=1; i<n; i++){
int take = nums[i];
if(i-2 >= 0) take += dp[i-2];
int notake = dp[i-1];
dp[i] = max(take,notake);
}
return dp[n-1];
}
//Space Optimization
int fopt(int n, vector<int>& nums){
int p1 = nums[0], p2 = 0, ans = p1;
for(int i=1; i<n; i++){
int take = nums[i];
if(i-2 >= 0) take += p2;
int notake = p1;
ans = max(take,notake);
p2 = p1; p1 = ans;
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, -1);
return fmemo(n - 1, nums, dp);
}
/*
QUESTION:-
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Approach:
1. Since the houses are arranged in a circle, the robber cannot rob the first and last house together as they are adjacent.
2. To solve this problem, we can divide it into two subproblems: one where the robber robs from the first house to the second-last house (excluding the last house), and another where the robber robs from the second house to the last house (excluding the first house).
3. We can use dynamic programming with memoization to calculate the maximum amount of money that can be robbed in each subproblem.
4. We define a helper function fmemo(e, i, nums, dp) that calculates the maximum amount of money that can be robbed from the e-th to the i-th house using memoization.
5. The function checks if the maximum amount for the i-th house is already calculated and stored in the dp array. If yes, it returns the value from dp.
6. Otherwise, it calculates the maximum amount by considering two options:
a) Rob the current house and add the money with the maximum amount from the (i-2)th house (since adjacent houses cannot be robbed).
b) Skip the current house and take the maximum amount from the (i-1)th house.
7. The base case is when i is less than e, in which case the function returns 0 as there are no houses to rob.
8. In the main function rob(nums), we first check if there is only one house. If yes, the robber can only rob that house, so we return the amount in that case.
9. Otherwise, we create a dp array of size n initialized with -1 and call the fmemo function twice: one for robbing from the first to the second-last house and the other for robbing from the second to the last house.
10. Finally, we return the maximum amount from the two subproblems, which gives the maximum amount the robber can rob without alerting the police.
Complexity Analysis:
- The time complexity of the fmemo function is O(n) because we are calculating the maximum amount for each house only once and storing it in the dp array.
- The space complexity is also O(n) to store the dp array.
*/
// Memoization
int fmemo(int e, int i, vector<int>& nums, vector<int>& dp) {
if (i < e)
return 0;
if (i == e)
return dp[i] = nums[i];
if (dp[i] != -1)
return dp[i];
int take = nums[i] + fmemo(e, i - 2, nums, dp);
int notake = fmemo(e, i - 1, nums, dp);
return dp[i] = max(take, notake);
}
// Tabulation
int ftab(int e, int n, vector<int>& nums){
vector<int> dp(n);
dp[e] = nums[e];
for(int i=e+1; i<n-(!e); i++){
int take = nums[i];
if(i-2>=e)
take += dp[i-2];
int notake = dp[i-1];
dp[i] = max(take,notake);
}
return dp[n-1-(!e)];
}
// Space Optimization
int fopt(int e, int n, vector<int>& nums){
int p1 = nums[e], p2 = 0, ans = 0;
for(int i=e+1; i<n-(!e); i++){
int take = nums[i];
if(i-2>=e)
take += p2;
int notake = p1;
ans = max(take,notake);
p2 = p1; p1 = ans;
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1)
return nums[0];
vector<int> dp(n, -1);
int s = fmemo(1, n - 1, nums, dp); // Rob from 1st to 2nd-last house
dp.assign(n, -1);
int e = fmemo(0, n - 2, nums, dp); // Rob from 2nd to last house
return max(s, e);
}
3. 2D DP¶
/*
QUESTION:-
Geek is going for n days training program, he can perform any one of these three activities Running, Fighting, and Learning Practice. Each activity has some point on each day. As Geek wants to improve all his skills, he can't do the same activity on two consecutive days. Help Geek to maximize his merit points as we were given a 2D array of n*3 points corresponding to each day and activity.
Example:
Input:
n = 3
points = [[1,2,5],[3,1,1],[3,3,3]]
Output:
11
Explanation:
Geek will learn a new move and earn 5 points on the first day,
then on the second day, he will do running and earn 3 points,
and on the third day, he will do fighting and earn 3 points.
So, the maximum points is 11.
Approach:
1. To maximize the merit points, we need to find the maximum sum of points such that the Geek can't perform the same activity on two consecutive days.
2. We can solve this problem using dynamic programming with memoization (top-down approach).
3. We define a helper function fmemo(n, prev, points, memo) that calculates the maximum points the Geek can earn from the nth day onwards, given that on the (n-1)th day, he performed the activity indexed by 'prev'.
4. The function checks if the maximum points for the (n-1)th day and 'prev' activity is already calculated and stored in the memo array. If yes, it returns the value from memo.
5. Otherwise, it calculates the maximum points for the nth day by considering all three activities except the one performed on the (n-1)th day. It then adds the points for the nth day and recursively calls the function for the (n-1)th day with the new activity and updates the maximum points.
6. The base case is when n is less than 0, in which case the function returns 0 as there are no days to earn points.
7. In the main function maximumPoints(points, n), we create a dp (memo) array of size n initialized with -1 and call the fmemo function for the nth day with the initial activity as -1 (since no activity is performed on the first day).
8. Finally, we return the maximum points obtained for all three possible starting activities (running, fighting, learning practice) as the result.
Complexity Analysis:
- The time complexity of the fmemo function is O(n) because we are calculating the maximum points for each day only once and storing it in the memo array.
- The space complexity is also O(n) to store the memo array.
*/
//Memoization
int fmemo(int n, int prev, vector<vector<int>>& points, vector<vector<int>>& memo) {
if (n < 0)
return 0;
if (prev != -1 && memo[n][prev] != -1) {
return memo[n][prev];
}
int ans = 0;
for (int i = 0; i < 3; i++) {
if (i != prev) {
int temp = points[n][i] + fmemo(n - 1, i, points, memo);
ans = max(ans, temp);
}
}
if (prev != -1) {
memo[n][prev] = ans;
}
return ans;
}
//Tbaulation
int ftab(int n, vector<vector<int>>& points) {
vector<vector<int>> dp(n, vector<int>(3, 0));
// Base case: for the first row, the maximum points for each column are the points in that row.
for (int i = 0; i < 3; i++) {
dp[0][i] = points[0][i];
}
// Calculate the maximum points for each row while considering the previous row's choices.
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j != k) {
dp[i][j] = max(dp[i][j], points[i][j] + dp[i - 1][k]);
}
}
}
}
// Find the maximum points among all choices for the last row.
int ans = 0;
for (int i = 0; i < 3; i++) {
ans = max(ans, dp[n - 1][i]);
}
return ans;
}
int maximumPoints(vector<vector<int>>& points, int n) {
vector<vector<int>> memo(n, vector<int>(3, -1));
return fmemo(n - 1, -1, points, memo);
}
/*
QUESTION:-
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Example 1:
Input: m = 3, n = 7
Output: 28
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, j, dp) that calculates the number of unique paths from the top-left corner (0, 0) to the cell (i, j) on the grid.
3. The function checks if the number of unique paths for the cell (i, j) is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. Otherwise, it calculates the number of unique paths for the cell (i, j) by adding the number of unique paths from the cell above (i-1, j) and the cell to the left (i, j-1).
5. The base case is when i or j is less than 0, in which case the function returns 0 as there are no paths to reach those cells.
6. In the main function uniquePaths(m, n), we create a dp array of size m x n initialized with -1 and call the fmemo function for the bottom-right cell (m-1, n-1).
7. Finally, we return the number of unique paths obtained for the bottom-right cell as the result.
Complexity Analysis:
- The time complexity of the fmemo function is O(m x n) because we are calculating the number of unique paths for each cell only once and storing it in the dp array.
- The space complexity is also O(m x n) to store the dp array.
Note: The given test cases are generated such that the answer will be less than or equal to 2 x 10^9.
*/
//Memeoization
int fmemo(int i, int j, vector<vector<int>>& dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
int top = fmemo(i - 1, j, dp);
int left = fmemo(i, j - 1, dp);
return dp[i][j] = top + left;
}
//Tabulation
int ftab(int m, int n){
vector<vector<int>> dp(m,vector<int>(n));
dp[0][0] = 1;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0) continue;
int top = 0, left = 0;
if(i-1>=0) top = top = dp[i-1][j];
if(j-1>=0) left = dp[i][j-1];
dp[i][j] = top+left;
}
}
return dp[m-1][n-1];
}
//Space Optimization
int fopt(int m, int n){
vector<int> prev(n);
prev[0] = 1;
for(int i=0; i<m; i++){
vector<int> curr(n);
curr[0] = 1;
for(int j=0; j<n; j++){
if(i==0 && j==0) continue;
int top = 0, left = 0;
if(i-1>=0) top = top = prev[j];
if(j-1>=0) left = curr[j-1];
curr[j] = top+left;
}
prev = curr;
}
return prev[n-1];
}
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, -1));
return fmemo(m - 1, n - 1, dp);
}
/*
QUESTION:-
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Example:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, j, grid, dp) that calculates the number of unique paths from the top-left corner (0, 0) to the cell (i, j) on the grid.
3. The function checks if the number of unique paths for the cell (i, j) is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. If the cell (i, j) contains an obstacle (i.e., grid[i][j] == 1), then there is no possible path through that cell, so the function returns 0.
5. Otherwise, it calculates the number of unique paths for the cell (i, j) by adding the number of unique paths from the cell above (i-1, j) and the cell to the left (i, j-1).
6. The base case is when i or j is less than 0, in which case the function returns 0 as there are no paths to reach those cells.
7. In the main function uniquePathsWithObstacles(obstacleGrid), we create a dp array of size m x n initialized with -1 and call the fmemo function for the bottom-right cell (m-1, n-1).
8. Finally, we return the number of unique paths obtained for the bottom-right cell as the result.
Complexity Analysis:
- The time complexity of the fmemo function is O(m x n) because we are calculating the number of unique paths for each cell only once and storing it in the dp array.
- The space complexity is also O(m x n) to store the dp array.
Note: The given test cases are generated such that the answer will be less than or equal to 2 x 10^9.
*/
// Memoization
int fmemo(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (grid[i][j] == 1)
return dp[i][j] = 0;
int top = fmemo(i - 1, j, grid, dp);
int left = fmemo(i, j - 1, grid, dp);
return dp[i][j] = top + left;
}
// Tabulation
int ftab(int m, int n, vector<vector<int>>& grid){
vector<vector<int>> dp(m,vector<int>(n));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0){
dp[i][j] = 1;
continue;
}
if(grid[i][j]==1){
dp[i][j] = 0;
continue;
}
int top = 0, left = 0;
if(i-1>=0) top = dp[i-1][j];
if(j-1>=0) left = dp[i][j-1];
dp[i][j] = top+left;
}
}
return dp[m-1][n-1];
}
// Space Optimization
int fopt(int m, int n, vector<vector<int>>& grid){
vector<int> prev(n);
for(int i=0; i<m; i++){
vector<int> curr(n);
for(int j=0; j<n; j++){
if(grid[i][j]==1){
curr[j]=0;
continue;
}
if(i==0 && j==0){
curr[j]=1;
continue;
}
int top = 0, left = 0;
if(i-1>=0) top = prev[j];
if(j-1>=0) left = curr[j-1];
curr[j] = top+left;
}
prev = curr;
}
return prev[n-1];
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
return 0;
vector<vector<int>> dp(m, vector<int>(n, -1));
return fmemo(m - 1, n - 1, obstacleGrid, dp);
}
/*
QUESTION:-
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, j, grid, dp) that calculates the minimum sum path to reach the cell (i, j) on the grid.
3. The function checks if the minimum sum path for the cell (i, j) is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. If i or j is less than 0 (out of bounds), the function returns a large value (e.g., 1e9) to represent an invalid path.
5. The base case is when i and j are both 0, in which case the function returns the value in the cell (0, 0) as the minimum sum path.
6. Otherwise, it calculates the minimum sum path for the cell (i, j) by taking the minimum of the minimum sum paths from the cell above (i-1, j) and the cell to the left (i, j-1), and then adding the value in the current cell (grid[i][j]).
7. The result is stored in the dp array to avoid recomputation when the function is called with the same parameters again.
Complexity Analysis:
- The time complexity of the fmemo function is O(m x n) because we are calculating the minimum sum path for each cell only once and storing it in the dp array.
- The space complexity is also O(m x n) to store the dp array.
*/
// Memoization
int fmemo(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& dp) {
if (i < 0 || j < 0)
return 1e9;
if (dp[i][j] != -1)
return dp[i][j];
if (i == 0 && j == 0)
return dp[i][j] = grid[i][j];
int top = fmemo(i - 1, j, grid, dp);
int left = fmemo(i, j - 1, grid, dp);
return dp[i][j] = min(top, left) + grid[i][j];
}
// Tabulation
int ftab(int m, int n, vector<vector<int>>& grid){
vector<vector<int>> dp(m,vector<int>(n));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0){
dp[i][j] = grid[i][j];
continue;
}
int top = 1e9, left = 1e9;
if(i-1>=0) top = dp[i-1][j];
if(j-1>=0) left = dp[i][j-1];
dp[i][j] = min(top,left)+grid[i][j];
}
}
return dp[m-1][n-1];
}
// Space Optimization
int fopt(int m, int n, vector<vector<int>>& grid){
vector<int> prev(n);
for(int i=0; i<m; i++){
vector<int> curr(n);
for(int j=0; j<n; j++){
if(i==0 && j==0){
curr[j] = grid[i][j];
continue;
}
int top = 1e9, left = 1e9;
if(i-1>=0) top = prev[j];
if(j-1>=0) left = curr[j-1];
curr[j] = min(top,left)+grid[i][j];
}
prev = curr;
}
return prev[n-1];
}
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, -1));
return fmemo(m - 1, n - 1, grid, dp);
}
/*
QUESTION:-
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, j, n, tri, dp) that calculates the minimum path sum from the current cell (i, j) to the bottom of the triangle.
3. The function checks if the minimum path sum for the current cell is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. If i is equal to n-1, it means we are at the last row of the triangle, so the minimum path sum is the value in the current cell (tri[i][j]).
5. Otherwise, the function calculates the minimum path sum for the current cell by taking the minimum of the minimum path sums from the cells directly below (i+1, j) and (i+1, j+1), and then adding the value in the current cell (tri[i][j]).
6. The result is stored in the dp array to avoid recomputation when the function is called with the same parameters again.
Complexity Analysis:
- The time complexity of the fmemo function is O(n^2) because we are calculating the minimum path sum for each cell only once and storing it in the dp array.
- The space complexity is also O(n^2) to store the dp array.
*/
// Memoization
int fmemo(int i, int j, int n, vector<vector<int>>& tri, vector<vector<int>>& dp) {
if (dp[i][j] != -1)
return dp[i][j];
if (i == n - 1)
return dp[i][j] = tri[i][j];
int a = fmemo(i + 1, j, n, tri, dp);
int b = fmemo(i + 1, j + 1, n, tri, dp);
return dp[i][j] = min(a, b) + tri[i][j];
}
// Tabulation
int ftab(int n, vector<vector<int>>& tri){
vector<vector<int>> dp(n,vector<int>(n));
for(int i=n-1; i>=0; i--){
for(int j=i; j>=0; j--){
if(i==n-1){
dp[i][j] = tri[i][j];
continue;
}
int a = dp[i+1][j];
int b = dp[i+1][j+1];
dp[i][j] = min(a,b)+tri[i][j];
}
}
return dp[0][0];
}
// Space Optimization
int fopt(int n, vector<vector<int>>& tri){
vector<int> prev(n);
for(int i=n-1; i>=0; i--){
vector<int> curr(n);
for(int j=i; j>=0; j--){
if(i==n-1){
curr[j] = tri[i][j];
continue;
}
int a = prev[j];
int b = prev[j+1];
curr[j] = min(a,b)+tri[i][j];
}
prev = curr;
}
return prev[0];
}
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return fmemo(0, 0, n, triangle, dp);
}
/*
QUESTION:-
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.
A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Example:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, j, mat, dp) that calculates the minimum sum of any falling path starting from cell (i, j).
3. The function checks if the minimum sum for the current cell (i, j) is already calculated and stored in the dp array. If yes, it returns the value from dp.
4. If i is 0, it means we are at the first row, so the minimum sum starting from this cell is the value in the current cell (mat[i][j]).
5. Otherwise, the function calculates the minimum sum for the current cell by taking the minimum of the minimum sums of the cells above it (i-1, j-1), (i-1, j), and (i-1, j+1), and then adding the value in the current cell (mat[i][j]).
6. The result is stored in the dp array to avoid recomputation when the function is called with the same parameters again.
7. Finally, we find the minimum falling path sum for all cells in the first row and return the smallest value.
Complexity Analysis:
- The time complexity of the fmemo function is O(n^2) since we are calculating the minimum sum for each cell only once and storing it in the dp array.
- The space complexity is also O(n^2) to store the dp array.
*/
// Memoization
int fmemo(int i, int j, vector<vector<int>>& mat, vector<vector<int>>& dp) {
if (j < 0 || j >= mat[0].size())
return 1e9;
if (dp[i][j] != -1)
return dp[i][j];
if (i == 0)
return dp[i][j] = mat[i][j];
int a = fmemo(i - 1, j - 1, mat, dp);
int b = fmemo(i - 1, j, mat, dp);
int c = fmemo(i - 1, j + 1, mat, dp);
return dp[i][j] = min(a, min(b, c)) + mat[i][j];
}
// Tabulation
int ftab(int n, vector<vector<int>>& mat){
vector<vector<int>> dp(n,vector<int>(n));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==0){
dp[i][j] = mat[i][j];
continue;
}
int a = 1e9, c = 1e9;
if(j-1>=0) a = dp[i-1][j-1];
int b = dp[i-1][j];
if(j+1<n) c = dp[i-1][j+1];
dp[i][j] = min(a,min(b,c))+mat[i][j];
}
}
int ans = INT_MAX;
for(auto i:dp[n-1]) ans = min(ans,i);
return ans;
}
// Space Optmization
int fopt(int n, vector<vector<int>>& mat){
vector<int> prev(n);
for(int i=0; i<n; i++){
vector<int> curr(n);
for(int j=0; j<n; j++){
if(i==0){
curr[j] = mat[i][j];
continue;
}
int a = 1e9, c = 1e9;
if(j-1>=0) a = prev[j-1];
int b = prev[j];
if(j+1<n) c = prev[j+1];
curr[j] = min(a,min(b,c))+mat[i][j];
}
prev = curr;
}
int ans = INT_MAX;
for(auto i:prev) ans = min(ans,i);
return ans;
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
int ans = 1e9;
for (int i = 0; i < n; i++) {
ans = min(ans, fmemo(n - 1, i, matrix, dp));
}
return ans;
}
4. DP on Subsequences¶
/*
QUESTION:-
Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 9
Output: 1
Explanation: Here there exists a subset with sum = 9, 4+3+2 = 9.
Approach:
1. We can solve this problem using dynamic programming with memoization (top-down approach).
2. We define a helper function fmemo(i, sum, arr, dp) that checks if there is a subset of elements up to index i whose sum is equal to the given sum.
3. The function checks if the target sum is 0. If yes, it means we have found a subset with the given sum and returns true.
4. If i is 0, it means we are at the first element, so the function checks if the first element is equal to the target sum.
5. If the dp value for the current index and sum is already calculated, it returns the stored value.
6. If the current element (arr[i]) is less than or equal to the target sum, the function recursively checks for two cases: including the current element in the subset (by reducing the sum) or excluding it (by not changing the sum).
7. If any of the above cases returns true, the dp value for the current index and sum is updated to true.
8. Finally, we return the dp value for the last index and the given sum.
Complexity Analysis:
- The time complexity of the fmemo function is O(n * sum), where n is the number of elements in the array and sum is the target sum. This is because the function calculates the result for each index and sum only once and stores it in the dp array.
- The space complexity is also O(n * sum) to store the dp array.
*/
// Memoization
bool fmemo(int i, int sum, vector<int>& arr, vector<vector<int>>& dp) {
if (sum == 0)
return true;
if (dp[i][sum] != -1)
return dp[i][sum];
if (i == 0)
return dp[i][sum] = (sum == arr[i]);
bool t = false;
if (arr[i] <= sum)
t = fmemo(i - 1, sum - arr[i], arr, dp);
bool nt = fmemo(i - 1, sum, arr, dp);
return dp[i][sum] = (t || nt);
}
// Tabulation
bool ftab(int n, int tar, vector<int>& arr){
vector<vector<int>> dp(n,vector<int>(tar+1));
for(int i=0; i<n; i++){
for(int sum=0; sum<=tar; sum++){
if(sum==0){
dp[i][sum] = true;
continue;
}
if(i==0){
dp[i][sum] = (sum==arr[i]);
continue;
}
bool t = false;
if(arr[i] <= sum) t = dp[i-1][sum-arr[i]];
bool nt = dp[i-1][sum];
dp[i][sum] = (t || nt);
}
}
return dp[n-1][tar];
}
// Space Optimization
bool fopt(int n, int tar, vector<int>& arr){
vector<int> prev(tar+1);
for(int i=0; i<n; i++){
vector<int> curr(tar+1);
for(int sum=0; sum<=tar; sum++){
if(sum==0){
curr[sum] = true;
continue;
}
if(i==0){
curr[sum] = (sum==arr[i]);
continue;
}
bool t = false;
if(arr[i] <= sum) t = prev[sum-arr[i]];
bool nt = prev[sum];
curr[sum] = (t || nt);
}
prev = curr;
}
return prev[tar];
}
bool isSubsetSum(vector<int> arr, int sum) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(sum + 1, -1));
return fmemo(n - 1, sum, arr, dp);
}
/*
QUESTION:
Given an integer array `nums`, return `true` if you can partition the array into two subsets such that the sum of the elements in both subsets is equal, or `false` otherwise.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
APPROACH:
- To solve this problem, we can use dynamic programming.
- We'll create a 2D DP array where `dp[i][j]` represents whether it's possible to select a subset from the first `i` elements of the `nums` array that sums up to `j`.
- The base case is when `j` is 0, in which case it's always possible to select an empty subset.
- For each element in the `nums` array, we have two choices: include it in the subset or exclude it.
- So, the recurrence relation becomes:
dp[i][j] = dp[i - 1][j] (exclude nums[i]) || dp[i - 1][j - nums[i]] (include nums[i])
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n * sum), where `n` is the number of elements in the `nums` array and `sum` is the sum of all elements.
CODE:
*/
// Memoization
bool fmemo(int i, int sum, vector<int>& arr, vector<vector<int>>& dp) {
if (sum == 0)
return true;
if (dp[i][sum] != -1)
return dp[i][sum];
if (i == 0)
return dp[i][sum] = (sum == arr[i]);
bool t = false;
if (arr[i] <= sum)
t = fmemo(i - 1, sum - arr[i], arr, dp);
bool nt = fmemo(i - 1, sum, arr, dp);
return dp[i][sum] = (t || nt);
}
// Tabulation
bool ftab(int n, int tar, vector<int>& arr){
vector<vector<int>> dp(n,vector<int>(tar+1));
for(int i=0; i<n; i++){
for(int sum=0; sum<=tar; sum++){
if(sum==0){
dp[i][sum] = true;
continue;
}
if(i==0){
dp[i][sum] = (sum==arr[i]);
continue;
}
bool t = false;
if(arr[i] <= sum) t = dp[i-1][sum-arr[i]];
bool nt = dp[i-1][sum];
dp[i][sum] = (t || nt);
}
}
return dp[n-1][tar];
}
// Space Optimization
bool fopt(int n, int tar, vector<int>& arr){
vector<int> prev(tar+1);
for(int i=0; i<n; i++){
vector<int> curr(tar+1);
for(int sum=0; sum<=tar; sum++){
if(sum==0){
curr[sum] = true;
continue;
}
if(i==0){
curr[sum] = (sum==arr[i]);
continue;
}
bool t = false;
if(arr[i] <= sum) t = prev[sum-arr[i]];
bool nt = prev[sum];
curr[sum] = (t || nt);
}
prev = curr;
}
return prev[tar];
}
bool canPartition(vector<int>& nums) {
int sum = 0, n = nums.size();
for(auto i:nums) sum+=i;
if(sum%2!=0) return false;
int k = sum/2;
vector<vector<int>> dp(n, vector<int>(k + 1, -1));
return fmemo(n-1,k,nums,dp);
}
/*
QUESTION:
Given an array arr of size n containing non-negative integers,
the task is to divide it into two sets S1 and S2 such that the absolute
difference between their sums is minimum and find the minimum difference
Example 1:
Input: N = 4, arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11
APPROACH:
- Calculate the sum of all elements in the array.
- Initialize a 2D dp array of size n x (sum + 1) to store if it is possible to achieve a sum 's' using the first 'i' elements.
- Initialize dp[i][0] to true, since an empty subset can have a sum of 0.
- For each element 'arr[i]' and each possible sum 's' from 1 to 'sum':
- Check if it's possible to achieve a sum of 's' using the first 'i-1' elements, or using 's - arr[i]' and the first 'i-1' elements.
- Update dp[i][s] accordingly.
- Iterate through the dp array for the last row and find the minimum absolute difference between the sum 's' and 'totalSum - s' for which dp[n-1][s] is true.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n * sum), where 'n' is the number of elements and 'sum' is the sum of all elements.
- The space complexity is O(n * sum) for the dp array.
CODE:
*/
bool ftab(int n, int tar, int arr[], vector<vector<int>>& dp){
for(int i = 0; i < n; i++){
for(int sum = 0; sum <= tar; sum++){
if(sum == 0){
dp[i][sum] = true;
continue;
}
if(i == 0){
dp[i][sum] = (sum == arr[i]);
continue;
}
bool t = false;
if(arr[i] <= sum) t = dp[i-1][sum - arr[i]];
bool nt = dp[i-1][sum];
dp[i][sum] = (t || nt);
}
}
return dp[n-1][tar];
}
int minDifference(int arr[], int n){
int totalSum = 0;
for(int i = 0; i < n; i++) totalSum += arr[i];
vector<vector<int>> dp(n, vector<int>(totalSum + 1));
ftab(n, totalSum, arr, dp);
int ans = INT_MAX;
for(int i = 0; i <= totalSum; i++){
if(dp[n-1][i])
ans = min(ans, abs(i - (totalSum - i)));
}
return ans;
}
/*
QUESTION:
Given an array arr[] of non-negative integers and an integer sum,
the task is to count all subsets of the given array with a sum
equal to a given sum.
Note: Answer can be very large, so, output answer modulo 10^9+7
Example 1:
Input: N = 6, arr[] = {2, 3, 5, 6, 8, 10}
sum = 10
Output: 3
Explanation: {2, 3, 5}, {2, 8}, {10}
APPROACH:
- We'll use a bottom-up dynamic programming approach using a 2D dp array.
- Initialize dp[i][j] as the number of subsets with sum 'j' using the first 'i' elements.
- Base cases:
- dp[0][0] = 1 since an empty subset has a sum of 0.
- dp[i][0] = 1 since there's always an empty subset.
- For each element 'arr[i]' and each possible sum 'j' from 1 to 'sum':
- dp[i][j] = dp[i-1][j] (not taking the current element)
- if 'arr[i]' is less than or equal to 'j', then dp[i][j] += dp[i-1][j-arr[i]] (taking the current element)
- Return dp[n][sum] which represents the number of subsets with sum 'sum' using all 'n' elements.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n * sum), where 'n' is the number of elements and 'sum' is the required sum.
- The space complexity is O(n * sum) for the dp array.
CODE:
*/
const int mod = 1e9 + 7;
// Memoization
int fmemo(int i, int tar, int arr[], vector<vector<int>>& dp){
if(i == 0){
if(tar == 0 && arr[i] == 0) return dp[i][tar] = 2;
if(tar == 0) return dp[i][tar] = 1;
return dp[i][tar] = (arr[i] == tar);
}
if(dp[i][tar] != -1) return dp[i][tar];
int take = 0;
if(arr[i] <= tar) take = fmemo(i - 1, tar - arr[i], arr, dp);
int notake = fmemo(i - 1, tar, arr, dp);
return dp[i][tar] = (take + notake) % mod;
}
// Tabulation
int ftab(int n, int sum, int arr[]){
vector<vector<int>> dp(n,vector<int>(sum+1));
for(int i=0; i<n; i++){
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) dp[i][tar] = 2;
else if(tar==0) dp[i][tar] = 1;
else dp[i][tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = dp[i-1][tar-arr[i]];
int notake = dp[i-1][tar];
dp[i][tar] = (take+notake)%mod;
}
}
return dp[n-1][sum];
}
// Space Optimization
int fopt(int n, int sum, int arr[]){
vector<int> prev(sum+1);
for(int i=0; i<n; i++){
vector<int> curr(sum+1);
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) curr[tar] = 2;
else if(tar==0) curr[tar] = 1;
else curr[tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = prev[tar-arr[i]];
int notake = prev[tar];
curr[tar] = (take+notake)%mod;
}
prev = curr;
}
return prev[sum];
}
int perfectSum(int arr[], int n, int sum){
vector<vector<int>> dp(n, vector<int>(sum + 1, -1));
return fmemo(n - 1, sum, arr, dp);
}
/*
QUESTION:
Given an array arr, partition it into two subsets(possibly empty)
such that their union is the original array. Let the sum of the
elements of these two subsets be S1 and S2.
Given a difference d, count the number of partitions in which S1 is
greater than or equal to S2 and the difference S1 and S2 is equal to d.
Since the answer may be large, return it modulo 10^9 + 7.
Example 1:
Input:
n = 4, d = 3
arr[] = {5, 2, 6, 4}
Output: 1
Explanation:
There is only one possible partition of this array.
Partition: {6, 4}, {5, 2}. The subset difference between subset sums is: (6 + 4) - (5 + 2) = 3.
APPROACH:
- We'll use a similar approach as used in the subset sum count problem.
- Initialize dp[i][j] as the number of subsets with sum 'j' using the first 'i' elements.
- Base cases:
- dp[0][0] = 1 since an empty subset has a sum of 0.
- dp[i][0] = 1 since there's always an empty subset.
- For each element 'arr[i]' and each possible sum 'j' from 1 to 'sum':
- dp[i][j] = dp[i-1][j] (not taking the current element)
- if 'arr[i]' is less than or equal to 'j', then dp[i][j] += dp[i-1][j-arr[i]] (taking the current element)
- Initialize 'ans' as 0.
- For each possible subset sum 'i':
- Check if the difference between (i - (sum - i)) is equal to 'd'.
- If it is, add the result of fmemo(n, i, arr, dp) to 'ans'.
- Return 'ans' % mod which represents the answer.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n * sum), where 'n' is the number of elements and 'sum' is the required sum.
- The space complexity is O(n * sum) for the dp array.
CODE:
*/
const int mod = 1e9 + 7;
// Memoization
int fmemo(int i, int tar, int arr[], vector<vector<int>>& dp){
if(i == 0){
if(tar == 0 && arr[i] == 0) return dp[i][tar] = 2;
if(tar == 0) return dp[i][tar] = 1;
return dp[i][tar] = (arr[i] == tar);
}
if(dp[i][tar] != -1) return dp[i][tar];
int take = 0;
if(arr[i] <= tar) take = fmemo(i - 1, tar - arr[i], arr, dp);
int notake = fmemo(i - 1, tar, arr, dp);
return dp[i][tar] = (take + notake) % mod;
}
// Tabulation
int ftab(int n, int sum, int arr[]){
vector<vector<int>> dp(n,vector<int>(sum+1));
for(int i=0; i<n; i++){
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) dp[i][tar] = 2;
else if(tar==0) dp[i][tar] = 1;
else dp[i][tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = dp[i-1][tar-arr[i]];
int notake = dp[i-1][tar];
dp[i][tar] = (take+notake)%mod;
}
}
return dp[n-1][sum];
}
// Space Optimization
int fopt(int n, int sum, int arr[]){
vector<int> prev(sum+1);
for(int i=0; i<n; i++){
vector<int> curr(sum+1);
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) curr[tar] = 2;
else if(tar==0) curr[tar] = 1;
else curr[tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = prev[tar-arr[i]];
int notake = prev[tar];
curr[tar] = (take+notake)%mod;
}
prev = curr;
}
return prev[sum];
}
int countPartitions(int n, int d, vector<int>& arr) {
int sum = 0, ans = 0;
for(auto i:arr) sum += i;
vector<vector<int>> dp(n, vector<int>(sum + 1, -1));
for(int i = 0; i <= sum; i++){
if(i - (sum - i) == d)
ans = (ans + fmemo(n - 1, i, arr, dp)) % mod;
}
return ans;
}
/*
QUESTION:
Given weights and values of 'N' items, the task is to put these
items in a knapsack of capacity 'W' to get the maximum total value
in the knapsack. The constraint is that each item can either be
picked completely or not at all (0-1 property).
Example:
Input:
N = 3
W = 4
values[] = {1, 2, 3}
weight[] = {4, 5, 1}
Output: 3
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the
maximum value that can be obtained using the first 'i' items
and having a knapsack capacity of 'j'.
- Base cases:
- dp[0][j] = 0 for all j (no items available)
- dp[i][0] = 0 for all i (no capacity)
- For each item 'i' and each possible capacity 'j':
- If the weight of the current item is less than or equal to 'j':
- dp[i][j] = max(dp[i-1][j], val[i] + dp[i-1][j-wt[i]])
- Otherwise, dp[i][j] = dp[i-1][j] (item cannot be included)
- The required answer will be dp[N][W] where 'N' is the number of items
and 'W' is the knapsack capacity.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(N * W), where 'N' is the
number of items and 'W' is the knapsack capacity.
- The space complexity is O(N * W) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int val[], int wt[], int W, vector<vector<int>>& dp){
if(i == 0){
if(W >= wt[i]) return dp[i][W] = val[i];
else return dp[i][W] = 0;
}
if(dp[i][W] != -1) return dp[i][W];
int take = INT_MIN;
if(W >= wt[i]) take = val[i] + fmemo(i-1, val, wt, W - wt[i], dp);
int notake = fmemo(i-1, val, wt, W, dp);
return dp[i][W] = max(take, notake);
}
// Tabulation
int ftab(int n, int val[], int wt[], int weight){
vector<vector<int>> dp(n,vector<int>(weight+1));
for(int i=0; i<n; i++){
for(int W=0; W<=weight; W++){
if(i==0){
if(W >= wt[i]) dp[i][W] = val[i];
else dp[i][W] = 0;
continue;
}
int take = INT_MIN;
if(W >= wt[i]) take = val[i]+dp[i-1][W-wt[i]];
int notake = dp[i-1][W];
dp[i][W] = max(take,notake);
}
}
return dp[n-1][weight];
}
// Space Optimization
int fopt(int n, int val[], int wt[], int weight){
vector<int> prev(weight+1);
for(int i=0; i<n; i++){
vector<int> curr(weight+1);
for(int W=0; W<=weight; W++){
if(i==0){
if(W >= wt[i]) curr[W] = val[i];
else curr[W] = 0;
continue;
}
int take = INT_MIN;
if(W >= wt[i]) take = val[i]+prev[W-wt[i]];
int notake = prev[W];
curr[W] = max(take,notake);
}
prev = curr;
}
return dp[n-1][weight];
}
int knapSack(int W, int wt[], int val[], int n) {
vector<vector<int>> dp(n, vector<int>(W + 1, -1));
return fmemo(n - 1, val, wt, W, dp);
}
/*
QUESTION:
Given an integer array 'coins' representing coins of different
denominations and an integer 'amount' representing a total amount
of money, the task is to return the fewest number of coins that
you need to make up that amount. If that amount of money cannot
be made up by any combination of the coins, return -1.
Example:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the minimum
number of coins needed to make up amount 'j' using the first 'i' coins.
- Base case:
- dp[i][0] = 0 for all 'i' (no coins needed to make 0 amount)
- dp[0][j] = 1e9 (no way to make up any amount using 0 coins)
- For each coin 'i' and each possible amount 'j':
- dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1)
- The required answer will be dp[n][amount] where 'n' is the number
of coins and 'amount' is the given total amount.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(N * amount), where 'N' is
the number of coins and 'amount' is the given total amount.
- The space complexity is O(N * amount) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int amt, vector<int>& coins, vector<vector<int>>& dp){
if(amt == 0) return 0;
if(i == 0){
if(amt % coins[i] == 0) return amt / coins[i];
else return 1e9;
}
if(dp[i][amt] != -1) return dp[i][amt];
int take = 1e9;
if(coins[i] <= amt) take = 1 + fmemo(i, amt - coins[i], coins, dp);
int notake = fmemo(i - 1, amt, coins, dp);
return dp[i][amt] = min(take, notake);
}
// Tabulation
int ftab(int n, int amount, vector<int>& coins){
vector<vector<int>> dp(n,vector<int>(amount+1));
for(int i=0; i<n; i++){
for(int amt=0; amt<=amount; amt++){
if(amt==0) {
dp[i][amt] = 0;
continue;
}
if(i==0){
if(amt%coins[i]==0) dp[i][amt] = amt/coins[i];
else dp[i][amt] = 1e9;
continue;
}
int take = 1e9;
if(coins[i]<=amt) take = 1+dp[i][amt-coins[i]];
int notake = dp[i-1][amt];
dp[i][amt] = min(take,notake);
}
}
return dp[n-1][amount];
}
// Space Optimization
int fopt(int n, int amount, vector<int>& coins){
vector<int> prev(amount+1);
for(int i=0; i<n; i++){
vector<int> curr(amount+1);
for(int amt=0; amt<=amount; amt++){
if(amt==0) {
curr[amt] = 0;
continue;
}
if(i==0){
if(amt%coins[i]==0) curr[amt] = amt/coins[i];
else curr[amt] = 1e9;
continue;
}
int take = 1e9;
if(coins[i]<=amt) take = 1+curr[amt-coins[i]];
int notake = prev[amt];
curr[amt] = min(take,notake);
}
prev = curr;
}
return prev[amount];
}
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n, vector<int>(amount + 1, -1));
int ans = fmemo(n - 1, amount, coins, dp);
return (ans == 1e9) ? -1 : ans;
}
/*
QUESTION:
Given an array 'nums' and an integer 'target', the task is to count
the number of ways to make the sum of elements of one subset equal
to 'target'.
Example:
Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 ways to achieve the target sum:
{1, 1, 1}, {1, 2}, {2, 1}, {1, 2}, {3}
APPROACH:
- The problem can be reduced to finding the count of subsets with a
given sum.
- Initialize dp[i][j] as the number of subsets with sum 'j' using
the first 'i' elements.
- Base cases:
- dp[0][0] = 1 since an empty subset has a sum of 0.
- dp[i][0] = 1 since there's always an empty subset.
- For each element 'nums[i]' and each possible sum 'j' from 1 to 'target':
- dp[i][j] = dp[i-1][j] (not taking the current element)
- if 'nums[i]' is less than or equal to 'j', then dp[i][j] += dp[i-1][j-nums[i]] (taking the current element)
- The required answer will be dp[n][target] where 'n' is the number
of elements in the array.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n * target), where 'n'
is the number of elements in the array.
- The space complexity is O(n * target) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int tar, int arr[], vector<vector<int>>& dp){
if(i == 0){
if(tar == 0 && arr[i] == 0) return dp[i][tar] = 2;
if(tar == 0) return dp[i][tar] = 1;
return dp[i][tar] = (arr[i] == tar);
}
if(dp[i][tar] != -1) return dp[i][tar];
int take = 0;
if(arr[i] <= tar) take = fmemo(i - 1, tar - arr[i], arr, dp);
int notake = fmemo(i - 1, tar, arr, dp);
return dp[i][tar] = (take + notake);
}
// Tabulation
int ftab(int n, int sum, int arr[]){
vector<vector<int>> dp(n,vector<int>(sum+1));
for(int i=0; i<n; i++){
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) dp[i][tar] = 2;
else if(tar==0) dp[i][tar] = 1;
else dp[i][tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = dp[i-1][tar-arr[i]];
int notake = dp[i-1][tar];
dp[i][tar] = (take+notake);
}
}
return dp[n-1][sum];
}
// Space Optimization
int fopt(int n, int sum, int arr[]){
vector<int> prev(sum+1);
for(int i=0; i<n; i++){
vector<int> curr(sum+1);
for(int tar=0; tar<=sum; tar++){
if(i==0){
if(tar==0 && arr[i]==0) curr[tar] = 2;
else if(tar==0) curr[tar] = 1;
else curr[tar] = (arr[i]==tar);
continue;
}
int take = 0;
if(arr[i] <= tar) take = prev[tar-arr[i]];
int notake = prev[tar];
curr[tar] = (take+notake);
}
prev = curr;
}
return prev[sum];
}
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size(), sum = 0;
for(auto i:nums) sum += i;
vector<vector<int>> dp(n, vector<int>(sum + 1, -1));
return fmemo(n - 1, target, nums, dp);
}
/*
QUESTION:
Given an integer array 'coins' representing coins of different
denominations and an integer 'amount' representing a total amount
of money, the task is to return the number of combinations that
make up that amount using the given coins. If that amount of money
cannot be made up by any combination of the coins, return 0.
Example:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four ways to make up the amount:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the number
of combinations to make up amount 'j' using the first 'i' coins.
- Base case:
- dp[i][0] = 1 for all 'i' (one way to make 0 amount with any coin)
- For each coin 'i' and each possible amount 'j':
- dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
- The required answer will be dp[n][amount] where 'n' is the number
of coins and 'amount' is the given total amount.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(N * amount), where 'N' is
the number of coins and 'amount' is the given total amount.
- The space complexity is O(N * amount) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int tar, vector<int>& arr, vector<vector<int>>& dp){
if(i == 0){
if(tar % arr[i] != 0) return 0;
return 1;
}
if(dp[i][tar] != -1) return dp[i][tar];
int take = 0;
if(arr[i] <= tar) take = fmemo(i, tar - arr[i], arr, dp);
int notake = fmemo(i - 1, tar, arr, dp);
return dp[i][tar] = (take + notake);
}
// Tabulation
int ftab(int n, int amount, vector<int>& arr){
vector<vector<int>> dp(n,vector<int>(amount+1));
for(int i=0; i<n; i++){
for(int tar=0; tar<=amount; tar++){
if(i == 0){
if(tar % arr[i]!=0) dp[i][tar] = 0;
else dp[i][tar] = 1;
continue;
}
int take = 0;
if(arr[i] <= tar) take = dp[i][tar-arr[i]];
int notake = dp[i-1][tar];
dp[i][tar] = (take + notake);
}
}
return dp[n-1][amount];
}
// Space Optimization
int fopt(int n, int amount, vector<int>& arr){
vector<int> prev(amount+1);
for(int i=0; i<n; i++){
vector<int> curr(amount+1);
for(int tar=0; tar<=amount; tar++){
if(i == 0){
if(tar % arr[i]!=0) curr[tar] = 0;
else curr[tar] = 1;
continue;
}
int take = 0;
if(arr[i] <= tar) take = curr[tar-arr[i]];
int notake = prev[tar];
curr[tar] = (take + notake);
}
prev = curr;
}
return prev[amount];
}
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> dp(n, vector<int>(amount + 1, -1));
return fmemo(n - 1, amount, coins, dp);
}
/*
QUESTION:
Given a set of N items, each with a weight and a value, represented
by the arrays w[] and val[] respectively, and a knapsack with weight
limit 'W', the task is to fill the knapsack in such a way that we
can get the maximum profit. Return the maximum profit.
Note: Each item can be taken any number of times.
Example:
Input: N = 2, W = 3
val[] = {1, 1}
wt[] = {2, 1}
Output: 3
Explanation:
1. Pick the 2nd element thrice.
2. Total profit = 1 + 1 + 1 = 3. Also the total weight = 1 + 1 + 1 = 3
which is <= W.
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the maximum
profit that can be obtained by using items from 0 to 'i' with a total
weight of 'j'.
- Base case: dp[0][j] = j / wt[0] * val[0] (maximum profit with only
the first item)
- For each item 'i' and each possible total weight 'j':
- dp[i][j] = max(dp[i-1][j], val[i] + dp[i][j - wt[i]])
- The required answer will be dp[N-1][W] where 'N' is the number of items
and 'W' is the given weight limit.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(N * W), where 'N' is the number
of items and 'W' is the given weight limit.
- The space complexity is O(N * W) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int val[], int wt[], int W, vector<vector<int>>& dp){
if(i == 0){
if(W >= wt[i]){
return dp[i][W] = (W / wt[i]) * val[i];
}
else return dp[i][W] = 0;
}
if(dp[i][W] != -1) return dp[i][W];
int take = INT_MIN;
if(W >= wt[i]) take = val[i] + fmemo(i, val, wt, W - wt[i], dp);
int notake = fmemo(i - 1, val, wt, W, dp);
return dp[i][W] = max(take, notake);
}
// Tabulation
int ftab(int n, int val[], int wt[], int weight){
vector<vector<int>> dp(n,vector<int>(weight+1));
for(int i=0; i<n; i++){
for(int W=0; W<=weight; W++){
if(i==0){
if(W >= wt[i]) dp[i][W] = (W/wt[i])*val[i];
else dp[i][W] = 0;
continue;
}
int take = INT_MIN;
if(W >= wt[i]) take = val[i]+dp[i][W-wt[i]];
int notake = dp[i-1][W];
dp[i][W] = max(take,notake);
}
}
return dp[n-1][weight];
}
// Space Optimization
int fopt(int n, int val[], int wt[], int weight){
vector<int> prev(weight+1);
for(int i=0; i<n; i++){
vector<int> curr(weight+1);
for(int W=0; W<=weight; W++){
if(i==0){
if(W >= wt[i]) curr[W] = (W/wt[i])*val[i];
else curr[W] = 0;
continue;
}
int take = INT_MIN;
if(W >= wt[i]) take = val[i]+curr[W-wt[i]];
int notake = prev[W];
curr[W] = max(take,notake);
}
prev = curr;
}
return dp[n-1][weight];
}
int knapSack(int N, int W, int val[], int wt[]){
vector<vector<int>> dp(N, vector<int>(W + 1, -1));
return fmemo(N - 1, val, wt, W, dp);
}
/*
QUESTION:
Given a rod of length 'N' inches and an array of prices 'price[]', where
price[i] denotes the value of a piece of length 'i', determine the maximum
value obtainable by cutting up the rod and selling the pieces.
Example:
Input: N = 8, Price[] = {1, 5, 8, 9, 10, 17, 17, 20}
Output: 22
Explanation: The maximum obtainable value is 22 by cutting in two pieces
of lengths 2 and 6, i.e., 5 + 17 = 22.
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the maximum
value obtainable by cutting a rod of length 'i' with available pieces
up to length 'j'.
- Base case: dp[0][j] = 0 (no rod, so value is 0)
- For each length 'i' and each possible total length 'j':
- dp[i][j] = max(dp[i-1][j], price[i] + dp[i][j - i])
- The required answer will be dp[N][N] where 'N' is the given length of
the rod.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(N^2), where 'N' is the length
of the rod.
- The space complexity is O(N^2) for the dp array.
CODE:
*/
// Memeoization
int fmemo(int i, int val[], int W, vector<vector<int>>& dp){
if(i == 1){
return (W / i) * val[i - 1];
}
if(dp[i][W] != -1) return dp[i][W];
int take = INT_MIN;
if(W >= i) take = val[i - 1] + fmemo(i, val, W - i, dp);
int notake = fmemo(i - 1, val, W, dp);
return dp[i][W] = max(take, notake);
}
// Tabulation
int ftab(int n, int val[]){
vector<vector<int>> dp(n+1,vector<int>(n+1));
for(int i=1; i<n; i++){
for(int W=0; W<=n; W++){
if(i==1){
dp[i][W] = (W / i) * val[i - 1];
continue;
}
int take = INT_MIN;
if(W >= i) take = val[i]+dp[i][W-i];
int notake = dp[i-1][W];
dp[i][W] = max(take,notake);
}
}
return dp[n][n];
}
int cutRod(int price[], int N) {
vector<vector<int>> dp(N + 1, vector<int>(N + 1, -1));
return fmemo(N, price, N, dp);
}
5. DP on Strings¶
/*
QUESTION:
Given two strings 'text1' and 'text2', return the length of their longest
common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original
string with some characters (can be none) deleted without changing the
relative order of the remaining characters.
Example:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the length of
the longest common subsequence between the prefixes text1[0..i] and
text2[0..j].
- Base case: dp[i][0] = 0 (empty second string) and dp[0][j] = 0
(empty first string).
- For each character at index 'i' in text1 and each character at index
'j' in text2:
- If text1[i] == text2[j], then dp[i][j] = dp[i-1][j-1] + 1
- Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- The required answer will be dp[n-1][m-1] where 'n' is the length of
text1 and 'm' is the length of text2.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n*m), where 'n' and 'm' are
the lengths of text1 and text2 respectively.
- The space complexity is O(n*m) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int j, string& s, string& r, vector<vector<int>>& dp){
if(i < 0 || j < 0) return 0;
if(dp[i][j] != -1) return dp[i][j];
if(s[i] == r[j]) return dp[i][j] = fmemo(i - 1, j - 1, s, r, dp) + 1;
else return dp[i][j] = max(fmemo(i - 1, j, s, r, dp), fmemo(i, j - 1, s, r, dp));
}
// Tabulation
int ftab(int n, int m, string& s, string& r){
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i-1]==r[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[n][m];
}
// Space Optimization
int fopt(int n, int m, string& s, string& r){
vector<int> prev(m+1,0);
for(int i=1; i<=n; i++){
vector<int> curr(m+1,0);
for(int j=1; j<=m; j++){
if(s[i-1]==r[j-1]) curr[j] = prev[j-1]+1;
else curr[j] = max(prev[j],curr[j-1]);
}
prev = curr;
}
return prev[m];
}
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
return fmemo(n - 1, m - 1, text1, text2, dp);
}
/*
QUESTION:
Print the Longest Common Subsequence between two strings.
APPROACH:
- We will use dynamic programming to find the longest common subsequence (LCS) between two strings.
- We will create a 2D array 'dp' of size (n+1) x (m+1), where n is the length of the first string and m is the length of the second string.
- dp[i][j] will store the length of LCS between the first i characters of string s1 and the first j characters of string s2.
- We will iterate through the strings and fill up the dp array as follows:
- If s1[i-1] matches s2[j-1], then dp[i][j] = dp[i-1][j-1] + 1, as we are extending the LCS by one character.
- Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]), taking the maximum length LCS till the previous characters.
- Once the dp array is filled, we will backtrack from the bottom-right corner (dp[n][m]) to reconstruct the LCS.
- We will start from dp[n][m] and go to dp[0][0], following the conditions mentioned above. If s1[i-1] matches s2[j-1], we add that character to the LCS.
- Finally, we reverse the obtained LCS to get the correct order.
COMPLEXITY ANALYSIS:
- The time complexity of the dynamic programming part is O(n * m), where n is the length of the first string and m is the length of the second string.
- The space complexity is also O(n * m) due to the dp array.
- The space required for storing the LCS is O(min(n, m)), which is the maximum length of the LCS.
- Overall, the algorithm runs in O(n * m) time and O(n * m) space.
CODE:
*/
void ftab(int n, int m, string &s1, string &s2, vector<vector<int>> &dp) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
string findLCS(int n, int m, string &s1, string &s2) {
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
ftab(n, m, s1, s2, dp);
int i = n, j = m;
string lcs = "";
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) {
lcs += s1[i - 1];
i = i - 1;
j = j - 1;
} else {
if (dp[i - 1][j] > dp[i][j - 1])
i = i - 1;
else
j = j - 1;
}
}
reverse(lcs.begin(), lcs.end());
return lcs;
}
/*
QUESTION:
Given two strings. The task is to find the length of the longest common substring.
Example:
Input: S1 = "ABCDGH", S2 = "ACDGHR", n = 6, m = 6
Output: 4
Explanation: The longest common substring is "CDGH" which has length 4.
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the length of
the longest common suffix of substrings S1[0..i-1] and S2[0..j-1].
- Initialize a variable 'maxi' to keep track of the maximum length found.
- For each character at index 'i' in S1 and each character at index 'j'
in S2:
- If S1[i] == S2[j], then dp[i][j] = dp[i-1][j-1] + 1
- Else, dp[i][j] = 0 (as no common suffix found)
- Update 'maxi' with dp[i][j]
- The required answer will be 'maxi'.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n*m), where 'n' and 'm' are
the lengths of S1 and S2 respectively.
- The space complexity is O(n*m) for the dp array.
CODE:
*/
int maxi = 0;
int fmemo(int i, int j, string& s, string& r, vector<vector<int>>& dp){
if(i < 0 || j < 0) return 0;
if(dp[i][j] != -1) return dp[i][j];
if(s[i] == r[j]){
dp[i][j] = fmemo(i - 1, j - 1, s, r, dp) + 1;
maxi = max(maxi, dp[i][j]);
}
else dp[i][j] = 0;
fmemo(i - 1, j, s, r, dp);
fmemo(i, j - 1, s, r, dp);
return dp[i][j];
}
int longestCommonSubstr(string S1, string S2, int n, int m){
vector<vector<int>> dp(n, vector<int>(m, -1));
fmemo(n - 1, m - 1, S1, S2, dp);
return maxi;
}
/*
QUESTION:
Given a string s, find the longest palindromic subsequence's length in s.
Example:
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
APPROACH:
- This problem can be solved using Dynamic Programming (DP).
- Initialize a 2D DP array 'dp' where dp[i][j] represents the length of
the longest palindromic subsequence in the substring s[i..j].
- For each character at index 'i' and each character at index 'j':
- If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2
- Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- The required answer will be dp[0][n-1], where 'n' is the length of 's'.
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n^2), where 'n' is the length of the input string.
- The space complexity is O(n^2) for the dp array.
CODE:
*/
// Memoization
int fmemo(int i, int j, string& s, string& r, vector<vector<int>>& dp){
if(i < 0 || j < 0) return 0;
if(dp[i][j] != -1) return dp[i][j];
if(s[i] == r[j]) return dp[i][j] = fmemo(i - 1, j - 1, s, r, dp) + 1;
else return dp[i][j] = max(fmemo(i - 1, j, s, r, dp), fmemo(i, j - 1, s, r, dp));
}
// Tabulation
int ftab(int n, int m, string& s, string& r){
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i-1]==r[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[n][m];
}
// Space Optimization
int fopt(int n, int m, string& s, string& r){
vector<int> prev(m+1,0);
for(int i=1; i<=n; i++){
vector<int> curr(m+1,0);
for(int j=1; j<=m; j++){
if(s[i-1]==r[j-1]) curr[j] = prev[j-1]+1;
else curr[j] = max(prev[j],curr[j-1]);
}
prev = curr;
}
return prev[m];
}
int longestPalindromeSubseq(string s) {
int n = s.size();
string r = s;
reverse(r.begin(),r.end());
vector<vector<int>> dp(n, vector<int>(n, -1));
return fmemo(n-1,n-1,s,r,dp);
}
/*
QUESTION:
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
APPROACH:
- The problem can be reduced to finding the minimum number of insertions needed to make a string a palindrome.
- We can find the Longest Common Subsequence (LCS) between the given string and its reverse.
- The length of the LCS gives us the length of the longest palindromic subsequence in the string.
- The minimum number of insertions required to make the string a palindrome is equal to the difference between the length of the string and the length of the LCS.
- Return this difference as the answer.
COMPLEXITY ANALYSIS:
- The time complexity of finding the LCS is O(n^2), where n is the length of the string.
- The space complexity is O(n^2) due to the dp array.
- Overall, the algorithm runs in O(n^2) time and O(n^2) space.
CODE:
*/
int fmemo(int i, int j, string &s, string &r, vector<vector<int>> &dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (s[i] == r[j])
return dp[i][j] = fmemo(i - 1, j - 1, s, r, dp) + 1;
else
return dp[i][j] = max(fmemo(i - 1, j, s, r, dp), fmemo(i, j - 1, s, r, dp));
}
int minInsertions(string s) {
int n = s.size();
string r = s;
reverse(r.begin(), r.end());
vector<vector<int>> dp(n, vector<int>(n, -1));
int lcs = fmemo(n - 1, n - 1, s, r, dp);
return n - lcs;
}
/*
QUESTION:
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
APPROACH:
- The problem can be reduced to finding the length of the Longest Common Subsequence (LCS) between the two strings.
- The idea is to find the length of the LCS and then subtracting it from the sum of the lengths of the two strings.
- The reason is that the characters not present in the LCS need to be deleted from both strings to make them the same.
- Therefore, the minimum number of steps required is equal to the sum of the lengths of the strings minus twice the length of the LCS.
COMPLEXITY ANALYSIS:
- The time complexity of finding the LCS is O(n*m), where n and m are the lengths of the two strings.
- The space complexity is O(n*m) due to the dp array.
- Overall, the algorithm runs in O(n*m) time and O(n*m) space.
CODE:
*/
int fmemo(int i, int j, string &s, string &r, vector<vector<int>> &dp) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (s[i] == r[j])
return dp[i][j] = fmemo(i - 1, j - 1, s, r, dp) + 1;
else
return dp[i][j] = max(fmemo(i - 1, j, s, r, dp), fmemo(i, j - 1, s, r, dp));
}
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
int lcs = fmemo(n - 1, m - 1, word1, word2, dp);
return (n + m) - 2 * lcs;
}
/*
QUESTION:
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.
If there are multiple valid strings, return any of them.
APPROACH:
- This problem can be solved using dynamic programming to find the length of the shortest common supersequence (SCS).
- The SCS is the shortest string that contains both str1 and str2 as subsequences.
- The idea is to first find the length of the SCS using a dynamic programming approach.
- Once the length is found, we can construct the SCS using the dp array and backtracking.
- We start from the last cell of the dp array and move either diagonally (when characters match) or towards the direction with the greater value.
- During backtracking, we append the characters from str1 or str2 to the SCS string based on the movement direction.
COMPLEXITY ANALYSIS:
- The time complexity of finding the length of the SCS is O(n*m), where n and m are the lengths of the two strings.
- The space complexity is O(n*m) due to the dp array.
- The backtracking process takes O(n + m) time.
- Overall, the algorithm runs in O(n*m) time and O(n*m) space.
CODE:
*/
string shortestCommonSupersequence(string str1, string str2) {
int n = str1.size(), m = str2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
int i = n, j = m;
string scs = "";
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
scs = str1[i - 1] + scs;
i--;
j--;
} else {
if (dp[i - 1][j] > dp[i][j - 1]) {
scs = str1[i - 1] + scs;
i--;
} else {
scs = str2[j - 1] + scs;
j--;
}
}
}
while (i > 0) {
scs = str1[i - 1] + scs;
i--;
}
while (j > 0) {
scs = str2[j - 1] + scs;
j--;
}
return scs;
}
/*
QUESTION:
Given two strings s and t, return the number of distinct subsequences of s which equals t.
APPROACH:
- The problem can be solved using dynamic programming.
- Let dp[i][j] represent the number of distinct subsequences of the first i characters of string s that match the first j characters of string t.
- If s[i] equals t[j], we have two choices: we can either include the current character (s[i]) in the subsequence, in which case we add dp[i-1][j-1] to our count, or we can exclude it and move on, so we add dp[i-1][j] to our count.
- If s[i] doesn't match t[j], we have no choice but to exclude s[i], so we add dp[i-1][j] to our count.
- Base cases: When j equals -1 (meaning we've matched all characters of t), return 1. When i equals -1 (meaning we've exhausted all characters of s), return 0.
- Return dp[n-1][m-1], where n is the length of s and m is the length of t.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n * m), where n is the length of string s and m is the length of string t.
- The space complexity is O(n * m) due to the dp array.
- Overall, the algorithm runs in O(n * m) time and O(n * m) space.
CODE:
*/
int fmemo(int i, int j, string& s, string& t, vector<vector<int>>& dp) {
if (j < 0) return 1;
if (i < 0) return 0;
if (dp[i][j] != -1) return dp[i][j];
if (s[i] == t[j])
return dp[i][j] = fmemo(i - 1, j - 1, s, t, dp) + fmemo(i - 1, j, s, t, dp);
else
return dp[i][j] = fmemo(i - 1, j, s, t, dp);
}
int ftab(int n, int m, string& s, string& t){
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
else dp[i][j] = dp[i-1][j];
}
}
return dp[n-1][m-1];
}
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
return fmemo(n - 1, m - 1, s, t, dp);
}
/*
QUESTION:
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
- '?' Matches any single character.
- '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
APPROACH:
- This problem can be solved using dynamic programming.
- Let dp[i][j] represent whether the substring of s up to index i can be matched with the substring of p up to index j.
- If s[i] equals p[j] or p[j] is '?', the characters match and we move diagonally to check the next characters.
- If p[j] is '*', we have two options:
1. Move vertically up (skip the '*').
2. Move horizontally left (count '*' as matching zero characters).
- Base cases: When both i and j are -1, return true. When only j is -1, check if the remaining characters in p are all '*'.
- Return dp[n-1][m-1], where n is the length of s and m is the length of p.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n * m), where n is the length of string s and m is the length of string p.
- The space complexity is O(n * m) due to the dp array.
- Overall, the algorithm runs in O(n * m) time and O(n * m) space.
CODE:
*/
bool allStars(int i, string& p) {
for (int j = i; j >= 0; j--) {
if (p[j] != '*') return false;
}
return true;
}
int fmemo(int i, int j, string& s, string& p, vector<vector<int>>& dp) {
if (i < 0 && j < 0) return true;
if (j < 0 && i >= 0) return false;
if (i < 0 && j >= 0) {
if (allStars(j, p)) return true;
return false;
}
if (dp[i][j] != -1) return dp[i][j];
if (s[i] == p[j] || p[j] == '?')
return dp[i][j] = fmemo(i - 1, j - 1, s, p, dp);
else {
if (p[j] == '*')
return dp[i][j] = (fmemo(i - 1, j, s, p, dp) || fmemo(i, j - 1, s, p, dp));
return dp[i][j] = false;
}
}
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
return fmemo(n - 1, m - 1, s, p, dp);
}
6. DP on Stocks¶
/*
QUESTION:
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
APPROACH:
- Initialize a variable minprice with the price on the first day and initialize ans to 0.
- Iterate through the array from the second day to the last day.
- Update ans with the maximum of its current value and the difference between the current price and minprice.
- Update minprice with the minimum of its current value and the current price.
- Return the final value of ans.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n), where n is the length of the prices array.
- The space complexity is O(1) as we are using constant extra space.
- Overall, the algorithm runs in O(n) time and O(1) space.
CODE:
*/
int maxProfit(vector<int>& prices) {
int minprice = prices[0];
int ans = 0;
for(int i = 1; i < prices.size(); i++){
ans = max(ans, prices[i] - minprice);
minprice = min(minprice, prices[i]);
}
return ans;
}
/*
QUESTION:
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time.
However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5 - 1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6 - 3 = 3.
Total profit is 4 + 3 = 7.
APPROACH:
- This problem can be solved using dynamic programming.
- We need to keep track of whether we are holding a stock or not on each day.
- Define a 2D DP array `dp` where dp[i][hold] represents the maximum profit achievable starting from day i while holding or not holding a stock.
- The base case is dp[n][0] = dp[n][1] = 0, where n is the number of days.
- Iterate through each day i in reverse order.
- If holding a stock, we can either sell the stock or continue holding.
- If not holding a stock, we can either buy the stock or continue not holding.
- Return dp[0][0], which represents the maximum profit achievable starting from day 0 while not holding a stock.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n), where n is the number of days.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n) time and O(n) space.
CODE:
*/
int fmemo(int i, int hold, vector<int>& prices, vector<vector<int>>& dp){
if(i == prices.size()) return 0;
if(dp[i][hold] != -1) return dp[i][hold];
if(hold){
// sell
int a = prices[i] + fmemo(i + 1, 0, prices, dp);
// not sell
int b = fmemo(i + 1, 1, prices, dp);
return dp[i][hold] = max(a, b);
}
else{
// buy
int a = -prices[i] + fmemo(i + 1, 1, prices, dp);
// not buy
int b = fmemo(i + 1, 0, prices, dp);
return dp[i][hold] = max(a, b);
}
}
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, -1));
return fmemo(0, 0, prices, dp);
}
/*
QUESTION:
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3 - 0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4 - 1 = 3.
APPROACH:
- This problem can be solved using dynamic programming.
- We need to keep track of the number of transactions completed so far (cap) and whether we are holding a stock or not on each day.
- Define a 3D DP array `dp` where dp[i][hold][cap] represents the maximum profit achievable starting from day i while holding or not holding a stock and having completed cap transactions.
- The base case is dp[n][0][0] = dp[n][0][1] = dp[n][0][2] = dp[n][1][0] = dp[n][1][1] = dp[n][1][2] = 0, where n is the number of days.
- Iterate through each day i in reverse order.
- If holding a stock, we can either sell the stock or continue holding.
- If not holding a stock, we can either buy the stock or continue not holding.
- Return dp[0][0][0], which represents the maximum profit achievable starting from day 0 while not holding a stock and having completed 0 transactions.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n), where n is the number of days.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n) time and O(n) space.
CODE:
*/
int fmemo(int i, int hold, int cap, vector<int>& prices, vector<vector<vector<int>>>& dp){
if(i == prices.size()) return 0;
if(cap == 3) return 0;
if(dp[i][hold][cap] != -1) return dp[i][hold][cap];
if(hold){
// sell
int a = prices[i] + fmemo(i + 1, 0, cap, prices, dp);
// not sell
int b = fmemo(i + 1, 1, cap, prices, dp);
return dp[i][hold][cap] = max(a, b);
}
else{
// buy
int a = -prices[i] + fmemo(i + 1, 1, cap + 1, prices, dp);
// not buy
int b = fmemo(i + 1, 0, cap, prices, dp);
return dp[i][hold][cap] = max(a, b);
}
}
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(3, -1)));
return fmemo(0, 0, 0, prices, dp);
}
/*
QUESTION:
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
Input: k = 2, prices = [2, 4, 1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4 - 2 = 2.
APPROACH:
- This problem can be solved using dynamic programming.
- We need to keep track of the number of transactions completed so far (cap) and whether we are holding a stock or not on each day.
- Define a 3D DP array `dp` where dp[i][hold][cap] represents the maximum profit achievable starting from day i while holding or not holding a stock and having completed cap transactions.
- The base case is dp[n][0][0] = dp[n][0][1] = ... = dp[n][0][k] = dp[n][1][0] = ... = dp[n][1][k] = 0, where n is the number of days and k is the given limit of transactions.
- Iterate through each day i in reverse order.
- If holding a stock, we can either sell the stock or continue holding.
- If not holding a stock, we can either buy the stock or continue not holding.
- Return dp[0][0][0], which represents the maximum profit achievable starting from day 0 while not holding a stock and having completed 0 transactions.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n * k), where n is the number of days and k is the given limit of transactions.
- The space complexity is O(n * k) due to the dp array.
- Overall, the algorithm runs in O(n * k) time and O(n * k) space.
CODE:
*/
int maxi;
int fmemo(int i, int hold, int cap, vector<int>& prices, vector<vector<vector<int>>>& dp){
if(i == prices.size()) return 0;
if(cap == maxi + 1) return 0;
if(dp[i][hold][cap] != -1) return dp[i][hold][cap];
if(hold){
// sell
int a = prices[i] + fmemo(i + 1, 0, cap, prices, dp);
// not sell
int b = fmemo(i + 1, 1, cap, prices, dp);
return dp[i][hold][cap] = max(a, b);
}
else{
// buy
int a = -prices[i] + fmemo(i + 1, 1, cap + 1, prices, dp);
// not buy
int b = fmemo(i + 1, 0, cap, prices, dp);
return dp[i][hold][cap] = max(a, b);
}
}
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
maxi = k;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(k + 1, -1)));
return fmemo(0, 0, 0, prices, dp);
}
/*
QUESTION:
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
APPROACH:
- This problem can be solved using dynamic programming.
- We need to keep track of whether we are holding a stock or not on each day.
- Define a 2D DP array `dp` where dp[i][hold] represents the maximum profit achievable starting from day i while holding or not holding a stock.
- The base case is dp[n][0] = dp[n][1] = 0, where n is the number of days.
- Iterate through each day i in reverse order.
- If holding a stock, we can either sell the stock or continue holding.
- If not holding a stock, we can either buy the stock or continue not holding.
- Return dp[0][0], which represents the maximum profit achievable starting from day 0 while not holding a stock.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n), where n is the number of days.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n) time and O(n) space.
CODE:
*/
int fmemo(int i, int hold, vector<int>& prices, vector<vector<int>>& dp){
if(i >= prices.size()) return 0;
if(dp[i][hold] != -1) return dp[i][hold];
if(hold){
// sell
int a = prices[i] + fmemo(i + 2, 0, prices, dp);
// not sell
int b = fmemo(i + 1, 1, prices, dp);
return dp[i][hold] = max(a, b);
}
else{
// buy
int a = -prices[i] + fmemo(i + 1, 1, prices, dp);
// not buy
int b = fmemo(i + 1, 0, prices, dp);
return dp[i][hold] = max(a, b);
}
}
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, -1));
return fmemo(0, 0, prices, dp);
}
/*
QUESTION:
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note:
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- The transaction fee is only charged once for each stock purchase and sale.
Example:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
APPROACH:
- This problem can be solved using dynamic programming.
- We need to keep track of whether we are holding a stock or not on each day.
- Define a 2D DP array `dp` where dp[i][hold] represents the maximum profit achievable starting from day i while holding or not holding a stock.
- The base case is dp[n][0] = dp[n][1] = 0, where n is the number of days.
- Iterate through each day i.
- If holding a stock, we can either sell the stock or continue holding.
- If not holding a stock, we can either buy the stock or continue not holding.
- Return dp[0][0], which represents the maximum profit achievable starting from day 0 while not holding a stock.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n), where n is the number of days.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n) time and O(n) space.
CODE:
*/
int f;
int fmemo(int i, int hold, vector<int>& prices, vector<vector<int>>& dp){
if(i == prices.size()) return 0;
if(dp[i][hold] != -1) return dp[i][hold];
if(hold){
// sell
int a = prices[i] - f + fmemo(i + 1, 0, prices, dp);
// not sell
int b = fmemo(i + 1, 1, prices, dp);
return dp[i][hold] = max(a, b);
}
else{
// buy
int a = -prices[i] + fmemo(i + 1, 1, prices, dp);
// not buy
int b = fmemo(i + 1, 0, prices, dp);
return dp[i][hold] = max(a, b);
}
}
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
f = fee;
vector<vector<int>> dp(n, vector<int>(2, -1));
return fmemo(0, 0, prices, dp);
}
7. DP on LIS¶
/*
QUESTION:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
APPROACH:
- This problem can be solved using dynamic programming.
- Let dp[i] represent the length of the longest increasing subsequence ending at index i.
- For each element at index i, we iterate through all the previous indices (prev) from 0 to i-1.
- If nums[prev] is smaller than nums[i], it means we can extend the increasing subsequence ending at prev by including nums[i].
- We update dp[i] as max(dp[prev] + 1, dp[i]).
- Initialize a variable ans to keep track of the maximum value in dp.
- Return ans as the length of the longest increasing subsequence.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the input array nums.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
int ftab(int n, vector<int>& nums) {
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int prev = 0; prev < i; prev++) {
if (nums[prev] < nums[i]) {
dp[i] = max(dp[prev] + 1, dp[i]);
}
}
}
int ans = -1;
for (auto i : dp) ans = max(ans, i);
return ans;
}
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
return ftab(n, nums);
}
/*
QUESTION:
Given an integer n and an array of integers, return the Longest Increasing Subsequence which is lexicographically smallest corresponding to the indices of the elements.
APPROACH:
- This problem can be solved using dynamic programming.
- Let dp[i] represent the length of the longest increasing subsequence ending at index i.
- Additionally, maintain a prevmap to track the previous index in the increasing subsequence.
- Iterate through the array and for each index i, iterate through all previous indices (prev) from 0 to i-1.
- If arr[prev] < arr[i] and dp[i] < dp[prev] + 1, update dp[i] and prevmap[i].
- Find the index i where dp has the maximum value.
- Construct the Longest Increasing Subsequence using the prevmap and the found index i.
- Return the LIS in reverse order to get the lexicographically smallest sequence.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the input array arr.
- The space complexity is O(n) due to the dp and prevmap arrays, as well as the lis vector.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
vector<int> ftab(int n, vector<int>& arr) {
vector<int> dp(n, 1);
vector<int> prevmap(n, -1);
for (int i = 0; i < n; i++) {
for (int prev = 0; prev < i; prev++) {
if (arr[prev] < arr[i] && dp[i] < dp[prev] + 1) {
dp[i] = dp[prev] + 1;
prevmap[i] = prev;
}
}
}
int i = max_element(dp.begin(), dp.end()) - dp.begin();
vector<int> lis;
while (i >= 0) {
lis.push_back(arr[i]);
i = prevmap[i];
}
reverse(lis.begin(), lis.end());
return lis;
}
vector<int> longestIncreasingSubsequence(int n, vector<int>& arr) {
return ftab(n, arr);
}
/*
QUESTION:
Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
- answer[i] % answer[j] == 0, or
- answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.
APPROACH:
- This problem can be solved using dynamic programming.
- Sort the input array nums in ascending order.
- Let dp[i] represent the size of the largest divisible subset ending at index i.
- Additionally, maintain a prevmap to track the previous index in the subset.
- Iterate through the sorted array and for each index i, iterate through all previous indices (prev) from 0 to i-1.
- If nums[i] is divisible by nums[prev] and dp[i] < dp[prev] + 1, update dp[i] and prevmap[i].
- Find the index i where dp has the maximum value.
- Construct the largest divisible subset using the prevmap and the found index i.
- Return the subset.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the input array nums.
- The space complexity is O(n) due to the dp and prevmap arrays, as well as the lis vector.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
vector<int> ftab(int n, vector<int>& nums) {
vector<int> dp(n, 1);
vector<int> prevmap(n, -1);
for (int i = 0; i < n; i++) {
for (int prev = 0; prev < i; prev++) {
if (nums[i] % nums[prev] == 0 && dp[i] < dp[prev] + 1) {
dp[i] = dp[prev] + 1;
prevmap[i] = prev;
}
}
}
int i = max_element(dp.begin(), dp.end()) - dp.begin();
vector<int> lis;
while (i >= 0) {
lis.push_back(nums[i]);
i = prevmap[i];
}
return lis;
}
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
return ftab(n, nums);
}
/*
QUESTION:
Given an array of positive integers, find the maximum length of a Bitonic subsequence.
A subsequence of an array is called Bitonic if it is first strictly increasing and then strictly decreasing.
APPROACH:
- This problem can be solved using dynamic programming.
- Compute two DP arrays: one from the left and another from the right.
- The left DP array, `left`, represents the length of the longest increasing subsequence ending at index i.
- The right DP array, `right`, represents the length of the longest decreasing subsequence starting at index i.
- Iterate through the array and compute the `left` DP array, considering elements from the left to the right.
- Iterate through the array again and compute the `right` DP array, considering elements from the right to the left.
- The maximum length of the Bitonic subsequence is the maximum sum of the corresponding elements from the `left` and `right` DP arrays minus 1 (to avoid double counting the element at the peak).
- Return the maximum length.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the input array nums.
- The space complexity is O(n) due to the left and right DP arrays.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
vector<int> fromLeft(int n, vector<int>& nums) {
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int prev = 0; prev < i; prev++) {
if (nums[prev] < nums[i]) {
dp[i] = max(dp[prev] + 1, dp[i]);
}
}
}
return dp;
}
vector<int> fromRight(int n, vector<int>& nums) {
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--) {
for (int prev = i + 1; prev < n; prev++) {
if (nums[prev] < nums[i]) {
dp[i] = max(dp[prev] + 1, dp[i]);
}
}
}
return dp;
}
int LongestBitonicSequence(vector<int> nums) {
int n = nums.size();
vector<int> left = fromLeft(n, nums);
vector<int> right = fromRight(n, nums);
int ans = -1;
for (int i = 0; i < n; i++) {
ans = max(ans, left[i] + right[i] - 1);
}
return ans;
}
/*
QUESTION:
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
APPROACH:
- This problem can be solved using dynamic programming.
- Compute two DP arrays: one for the length of the longest increasing subsequence ending at index i (`dp`) and another for the count of such subsequences (`cnt`).
- Iterate through the array and for each index i, iterate through all previous indices (prev) from 0 to i-1.
- If nums[prev] < nums[i], update the `dp` and `cnt` arrays accordingly.
- Find the maximum value in the `dp` array to get the length of the longest increasing subsequence (`lis`).
- Iterate through the `dp` array again and count the number of subsequences that have the length equal to `lis`.
- Return the total count of such subsequences.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the input array nums.
- The space complexity is O(n) due to the dp and cnt arrays.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
int ftab(int n, vector<int>& nums) {
vector<int> dp(n, 1);
vector<int> cnt(n, 1);
for (int i = 0; i < n; i++) {
for (int prev = 0; prev < i; prev++) {
if (nums[prev] < nums[i]) {
if (dp[i] == dp[prev] + 1) {
cnt[i] += cnt[prev];
} else if (dp[prev] + 1 > dp[i]) {
dp[i] = dp[prev] + 1;
cnt[i] = cnt[prev];
}
}
}
}
int lis = *max_element(dp.begin(), dp.end());
int ans = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == lis) {
ans += cnt[i];
}
}
return ans;
}
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
return ftab(n, nums);
}
8. DP on Partition¶
/*
QUESTION:
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications.
The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices + 1) where the ith matrix has the dimensions (arr[i-1] x arr[i]).
Example 1:
Input: N = 5
arr = {40, 20, 30, 10, 30}
Output: 26000
Explanation: There are 4 matrices of dimension
40x20, 20x30, 30x10, 10x30. Say the matrices are
named as A, B, C, D. Out of all possible combinations,
the most efficient way is (A*(B*C))*D.
The number of operations are -
20*30*10 + 40*20*10 + 40*10*30 = 26000.
APPROACH:
- This problem can be solved using dynamic programming.
- The dp[i][j] represents the minimum number of scalar multiplications required to compute the matrix chain multiplication of matrices from i to j.
- Iterate through the chain lengths from 2 to N (chain length of 2 means considering two matrices at a time).
- For each chain length, iterate through all possible starting matrices (i).
- For each starting matrix, calculate the cost of multiplying the matrices and update dp[i][j].
- Finally, return dp[1][N-1], which represents the minimum number of scalar multiplications needed for the entire matrix chain multiplication.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^3), where n is the length of the array arr.
- The space complexity is O(n^2) due to the dp array.
- Overall, the algorithm runs in O(n^3) time and O(n^2) space.
CODE:-
*/
int fmemo(int i, int j, int arr[], vector<vector<int>>& dp){
if(i==j) return 0;
if(dp[i][j] != -1) return dp[i][j];
int mini = INT_MAX;
for(int k=i; k<j; k++){
int cost = arr[i-1]*arr[k]*arr[j] + fmemo(i,k,arr,dp) + fmemo(k+1,j,arr,dp);
mini = min(cost,mini);
}
return dp[i][j] = mini;
}
int matrixMultiplication(int N, int arr[]){
int i=1, j = N-1;
vector<vector<int>> dp(N,vector<int>(N,-1));
return fmemo(i,j,arr,dp);
}
/*
QUESTION:
Given a wooden stick of length n units. The stick is labelled from 0 to n.
Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts.
Return the minimum total cost of the cuts.
Example:
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts [1, 3, 4, 5] as the order, the total cost is 1 + 3 + 3 + 4 + 5 = 16.
APPROACH:
- This problem can be solved using dynamic programming.
- Define a 2D DP array `dp` where dp[i][j] represents the minimum total cost to cut the stick between cuts[i] and cuts[j].
- Initialize dp[i][i] to 0 because there is no cost for a single cut.
- Iterate over the stick lengths from length 2 to the length of cuts + 1.
- For each stick length, iterate through all possible cut starting points (i).
- Calculate the cost for cutting the stick between cuts[i] and cuts[i + len - 1] and update the dp array.
- Finally, return dp[0][cuts.size() - 1], which represents the minimum total cost of the cuts.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^3), where n is the length of the cuts array.
- The space complexity is O(n^2) due to the dp array.
- Overall, the algorithm runs in O(n^3) time and O(n^2) space.
CODE:
*/
int fmemo(int i, int j, vector<int>& cuts, vector<vector<int>>& dp){
if(i > j) return 0;
if(dp[i][j] != -1) return dp[i][j];
int mini = 1e9;
for(int k = i; k <= j; k++){
int cost = (cuts[j + 1] - cuts[i - 1]) + fmemo(i, k - 1, cuts, dp) + fmemo(k + 1, j, cuts, dp);
mini = min(cost, mini);
}
return dp[i][j] = mini;
}
int minCost(int n, vector<int>& cuts) {
vector<int> cut;
cut.push_back(0);
for(auto i : cuts)
cut.push_back(i);
cut.push_back(n);
sort(cut.begin(), cut.end());
int s = cut.size();
vector<vector<int>> dp(s, vector<int>(s, -1));
int i = 1, j = cuts.size();
return fmemo(i, j, cut, dp);
}
/*
QUESTION:
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums.
You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins.
If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Example:
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation:
nums = [3, 1, 5, 8] --> [3, 5, 8] --> [3, 8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.
APPROACH:
- This problem can be solved using dynamic programming.
- Define a 2D DP array `dp` where dp[i][j] represents the maximum coins collected by bursting balloons between indices i and j.
- Iterate over the stick lengths from length 2 to the length of nums - 1.
- For each subarray length, iterate through all possible starting indices (i).
- Calculate the maximum coins collected by bursting balloons in the subarray between i and j, and update the dp array.
- Finally, return dp[1][n - 2], which represents the maximum coins collected by bursting all the balloons.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^3), where n is the length of the nums array.
- The space complexity is O(n^2) due to the dp array.
- Overall, the algorithm runs in O(n^3) time and O(n^2) space.
CODE:
*/
int fmemo(int i, int j, vector<int>& nums, vector<vector<int>>& dp){
if(j < i) return 0;
if(dp[i][j] != -1) return dp[i][j];
int ans = -1e9;
// the main curx is we are finding the last ballon remaining instead of the one bursting so that both sub problems remain independent
for(int k = i; k <= j; k++){
int coins = (nums[i - 1] * nums[k] * nums[j + 1]) + fmemo(i, k - 1, nums, dp) + fmemo(k + 1, j, nums, dp);
ans = max(ans, coins);
}
return dp[i][j] = ans;
}
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
int i = 1, j = n - 2;
vector<vector<int>> dp(n, vector<int>(n, -1));
return fmemo(i, j, nums, dp);
}
/*
QUESTION:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
APPROACH:
- This problem can be solved using dynamic programming.
- Define a 1D DP array `dp` where dp[i] represents the minimum cuts needed for a palindrome partitioning of s starting from index i.
- Iterate through each index i of the string.
- For each index i, iterate through all possible ending indices j such that j is in the range [i, n).
- Check if the substring from index i to j is a palindrome. If yes, update the dp[i] value by taking the minimum of its current value and dp[j + 1] + 1.
- Finally, return dp[0] - 1, which represents the minimum cuts needed for a palindrome partitioning of the entire string.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n^2), where n is the length of the string.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n^2) time and O(n) space.
CODE:
*/
bool isPalindrome(int i, int j, string& s){
while(i < j){
if(s[i] != s[j]) return false;
i++; j--;
}
return true;
}
int fmemo(int i, string& s, vector<int>& dp){
if(i == s.size()) return 0;
if(dp[i] != -1) return dp[i];
int ans = 1e9;
for(int j = i; j < s.size(); j++){
if(isPalindrome(i, j, s)){
int cost = 1 + fmemo(j + 1, s, dp);
ans = min(ans, cost);
}
}
return dp[i] = ans;
}
int minCut(string s) {
int n = s.size();
vector<int> dp(n, -1);
return fmemo(0, s, dp) - 1;
}
/*
QUESTION:
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k.
After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
Example:
Input: arr = [1, 15, 7, 9, 2, 5, 10], k = 3
Output: 84
Explanation: arr becomes [15, 15, 15, 9, 10, 10, 10]
APPROACH:
- This problem can be solved using dynamic programming.
- Define a 1D DP array `dp` where dp[i] represents the largest sum of the array after partitioning from index i to the end.
- Iterate through each index i of the array in reverse order.
- For each index i, iterate through all possible partition lengths from 1 to k.
- Calculate the maximum sum for the current partition, which is the maximum element within the partition multiplied by the length of the partition.
- Update dp[i] with the maximum value among all possible partition scenarios.
- Finally, return dp[0], which represents the largest sum of the array after partitioning.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(n * k), where n is the length of the array.
- The space complexity is O(n) due to the dp array.
- Overall, the algorithm runs in O(n * k) time and O(n) space.
CODE:
*/
int fmemo(int i, int k, vector<int>& arr, vector<int>& dp){
if(i == arr.size()) return 0;
if(dp[i] != -1) return dp[i];
int n = arr.size();
int maxi = 0, ans = 0;
for(int j = i; j < min(i + k, n); j++){
maxi = max(maxi, arr[j]);
int maxSum = maxi * (j - i + 1) + fmemo(j + 1, k, arr, dp);
ans = max(ans, maxSum);
}
return dp[i] = ans;
}
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n, -1);
return fmemo(0, k, arr, dp);
}
9. DP on Squares¶
/*
QUESTION:
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
APPROACH:
- This problem can be solved using dynamic programming.
- We need to find the largest square containing only 1's.
- Define a 2D DP array `dp` where dp[i][j] represents the side length of the largest square ending at (i, j).
- The base case is dp[i][0] = matrix[i][0] and dp[0][j] = matrix[0][j].
- Iterate through each cell (i, j) in the matrix starting from (1, 1).
- If matrix[i][j] is '1', update dp[i][j] as the minimum of (dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1.
- Update the maximum side length `maxSide` accordingly.
- Return `maxSide * maxSide`, which is the area of the largest square containing only 1's.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the matrix.
- The space complexity is O(m * n) due to the dp array.
- Overall, the algorithm runs in O(m * n) time and O(m * n) space.
CODE:
*/
int ftab(int m, int n, vector<vector<char>>& matrix){
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int maxSide = 0;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(matrix[i-1][j-1] == '1'){
int temp = min(dp[i-1][j], dp[i-1][j-1]);
dp[i][j] = min(dp[i][j-1], temp) + 1;
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
return ftab(m, n, matrix);
}
/*
QUESTION:
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
APPROACH:
- This problem can be solved using dynamic programming.
- We need to find the count of square submatrices with all ones.
- Define a 2D DP array `dp` where dp[i][j] represents the side length of the largest square ending at (i, j).
- The base case is dp[i][0] = matrix[i][0] and dp[0][j] = matrix[0][j].
- Iterate through each cell (i, j) in the matrix starting from (1, 1).
- If matrix[i][j] is 1, update dp[i][j] as the minimum of (dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1.
- Add dp[i][j] to the `ans` variable to keep track of the total count of squares.
- Return the `ans`.
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the matrix.
- The space complexity is O(m * n) due to the dp array.
- Overall, the algorithm runs in O(m * n) time and O(m * n) space.
CODE:
*/
int ftab(int m, int n, vector<vector<int>>& matrix){
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int ans = 0;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(matrix[i-1][j-1] == 1){
int temp = min(dp[i-1][j], dp[i-1][j-1]);
dp[i][j] = min(dp[i][j-1], temp) + 1;
ans += dp[i][j];
}
}
}
return ans;
}
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
return ftab(m, n, matrix);
}
DP Problem Solving Pattern¶
Standard DP Workflow
Common DP Categories¶
| Category | Example Problems |
|---|---|
| 1D DP | Fibonacci, Climbing Stairs |
| Grid DP | Unique Paths |
| Subsequence DP | Knapsack |
| String DP | LCS |
| Partition DP | MCM |
| Optimization DP | Stock Problems |