DP

Climbing Stairs

class Solution {
public:
    int recursion(int n,vector<int> &dp){
        if(n==0 || n==1) return 1;
        if(dp[n]!=-1) return dp[n];
        return dp[n]=recursion(n-1,dp)+recursion(n-2,dp);
    }
    int climbStairs(int n) {
        vector<int> dp(n+1,-1);
        return recursion(n,dp);

    }
};

Frog Jump Coding Ninjas

Recursion

#include <bits/stdc++.h>
int recursion(int ind,vector<int> &v){
     if(ind==0) return 0;
     int l=recursion(ind-1,v)+abs(v[ind]-v[ind-1]);
     int r=INT_MAX;
     if(ind>1) r=recursion(ind-2,v)+abs(v[ind]-v[ind-2]);
     return min(l,r);
}
int frogJump(int n, vector<int> &v)
{
    return recursion(n-1,v);
}

Memoization

#include <bits/stdc++.h>
int recursion(int ind,vector<int> &v,vector<int> &dp){
     if(ind==0) return 0;
     if(dp[ind]!=-1) return dp[ind];
     int l=recursion(ind-1,v,dp)+abs(v[ind]-v[ind-1]);
     int r=INT_MAX;
     if(ind>1) r=recursion(ind-2,v,dp)+abs(v[ind]-v[ind-2]);
     return dp[ind]=min(l,r);
}
int frogJump(int n, vector<int> &v)
{
     vector<int> dp(n,-1);
    return recursion(n-1,v,dp);
}

Tabulation

int frogJump(int n, vector<int> &v)
{
     vector<int> dp(n,-1);
     dp[0]=0;
     for(int i=1;i<n;i++){
          int fs=dp[i-1]+abs(v[i]-v[i-1]);
          int ss=INT_MAX;
          if(i>1)
          ss= dp[i-2]+abs(v[i]-v[i-2]);
          dp[i]=min(fs,ss);
     }
     return dp[n-1];
}

Space Optimized

int frogJump(int n, vector<int> &v)
{
     int prev=0,prev2=0;
     for(int i=1;i<n;i++){
          int fs=prev+abs(v[i]-v[i-1]);
          int ss=INT_MAX;
          if(i>1)
          ss= prev2+abs(v[i]-v[i-2]);
          int curr=min(fs,ss);
          prev2=prev;
          prev=curr;
     }
     return prev;
}

Frog Jump with k distances

int minimizeCost(int n, int k, vector<int> &v){
    // Write your code here.
    vector<int> dp(n);
    dp[0]=0;
    for(int i=1;i<n;i++){
        int minSteps=INT_MAX;
        for(int j=1;j<=k;j++){
            if((i-j)>=0){
                int steps=dp[i-j]+abs(v[i]-v[i-j]);
                minSteps=min(minSteps,steps);
            }
        }
        dp[i]=minSteps;
    }
    return dp[n-1];
}

Frog Jump Leetcode

class Solution {
public:
     bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> dp;
        for(auto position: stones)dp[position]=unordered_set<int>();
        dp[0].insert(0);
        for(auto position:stones){
            for(auto k:dp[position]){
                if(k-1>0 && dp.find(position+k-1)!=dp.end())
                dp[position+k-1].insert(k-1);
                if(dp.find(position+k)!=dp.end())
                dp[position+k].insert(k);
                if(dp.find(position+k+1)!=dp.end())
                dp[position+k+1].insert(k+1);
            }
        }
        return !dp[stones.back()].empty();
    }
};

Maximum Sum Of NonAdjacent Elements

Recursion+Memoization

#include <bits/stdc++.h>
int recursion(int ind,vector<int> &dp,vector<int> &nums){
    if(ind==0) return nums[ind];
    if(ind<0) return 0;
    if(dp[ind]!=-1) return dp[ind];
    int pick=nums[ind]+recursion(ind-2,dp,nums);
    int notPick=0+recursion(ind-1,dp,nums);
    return dp[ind]=max(pick,notPick);
}
int maximumNonAdjacentSum(vector<int> &nums){
    // Write your code here.
    int n=nums.size();
    vector<int> dp(n,-1);
    return recursion(n-1,dp,nums);
}

Tabulation

int maximumNonAdjacentSum(vector<int> &nums){
    // Write your code here.
    int n=nums.size();
    vector<int> dp(n,-1);
    dp[0]=nums[0];
    for(int i=1;i<n;i++){
        int pick=nums[i];
        if(i>1)
        pick=nums[i]+dp[i-2];
        int nonPick=0+dp[i-1];
        dp[i]=max(pick,nonPick);
    }
    return dp[n-1];
}

Space Optimized

int maximumNonAdjacentSum(vector<int> &nums){
    // Write your code here.
    int n=nums.size();
    int prev=nums[0];
    int prev2=0;
    for(int i=1;i<n;i++){
        int pick=nums[i];
        if(i>1)
        pick=nums[i]+prev2;
        int nonPick=0+prev;
        int curr=max(pick,nonPick);
        prev2=prev;
        prev=curr;
    }
    return prev;
}

House Robber

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,-1);
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
            int pick=nums[i];
            if(i>1)
            pick=nums[i]+dp[i-2];
            int nonPick=0+dp[i-1];
            dp[i]=max(pick,nonPick);
        }
        return dp[n-1];
    }
};

House Robber II

#define ll long long int
class Solution {
public:
    ll solve(vector<int> &nums){
        int n=nums.size();
        vector<ll> dp(n,-1);
        dp[0]=nums[0]*1LL;
        for(int i=1;i<n;i++){
            ll pick=nums[i];
            if(i>1) pick=nums[i]+dp[i-2];
            ll nonPick=0+dp[i-1];
            dp[i]=max(pick,nonPick);
        }
        return dp[n-1];
    }
    int rob(vector<int>& nums) {
        vector<int> nums1,nums2;
        int n=nums.size();
        if(n==1) return nums[0];
        for(int i=0;i<n;i++){
            if(i!=0) nums1.push_back(nums[i]);
            if(i!=n-1) nums2.push_back(nums[i]);
        }
        return max(solve(nums1),solve(nums2));
    }
};

Starting 2D DP

Ninja's Training

recursion

int recursion(vector<vector<int>>&points,int day,int lastIndex){
    if(day==0){
        int maxi=0;
        for(int i=0;i<3;i++){
            if(i!=lastIndex){
                maxi=max(maxi,points[day][i]);
            }
        }
        return maxi;
    }
    int maxi=0;
    for(int i=0;i<3;i++){
        if(i!=lastIndex){
            int pointsToday=points[day][i]+recursion(points,day-1,i);
            maxi=max(maxi,pointsToday);
        }

    }
    return maxi;
}
int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    vector<vector<int>> dp(n,vector<int>(3,0));
    return recursion(points,n-1,4);

}

Memoization

int recursion(vector<vector<int>>&points,int day,int lastIndex,vector<vector<int>>&dp){
    if(day==0){
        int maxi=0;
        for(int i=0;i<3;i++){
            if(i!=lastIndex){
                maxi=max(maxi,points[day][i]);
            }
        }
        return maxi;
    }
    if(dp[day][lastIndex]!=-1) return dp[day][lastIndex];
    int maxi=0;
    for(int i=0;i<3;i++){
        if(i!=lastIndex){
            int pointsToday=points[day][i]+recursion(points,day-1,i,dp);
            maxi=max(maxi,pointsToday);
        }

    }
    // return maxi;
    return dp[day][lastIndex]=maxi;
}
int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    vector<vector<int>> dp(n,vector<int>(4,-1));
    return recursion(points,n-1,3,dp);

}

Tabulation

int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    vector<vector<int>> dp(n,vector<int>(4,-1));
    dp[0][0]=max(points[0][1],points[0][2]);
    dp[0][1]=max(points[0][0],points[0][2]);
    dp[0][2]=max(points[0][0],points[0][1]);
    dp[0][3] = max(points[0][1], max(points[0][2], points[0][0]));
    for(int day=1;day<n;day++){
        for(int lastIndex=0;lastIndex<4;lastIndex++){
            dp[day][lastIndex]=0;
            int maxi=0;
            for(int task=0;task<3;task++){
                if(lastIndex!=task){
                    int pointToday=points[day][task]+dp[day-1][task];
                    maxi=max(pointToday,maxi);
                }
            }
            dp[day][lastIndex]=maxi;
        }
    }
    return dp[n-1][3];

}

Space Optimized

int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    vector<int> dp(4,-1);
    dp[0]=max(points[0][1],points[0][2]);
    dp[1]=max(points[0][0],points[0][2]);
    dp[2]=max(points[0][0],points[0][1]);
    dp[3]=max(points[0][0],max(points[0][1],points[0][2]));
    for(int day=1;day<n;day++){
        vector<int> temp(4,-1);
        for(int lastIndex=0;lastIndex<4;lastIndex++){
            temp[lastIndex]=0;
            int maxi=0;
            for(int task=0;task<3;task++){
                if(lastIndex!=task){
                    int pointToday=points[day][task]+dp[task];
                    maxi=max(pointToday,maxi);
                }
            }
            temp[lastIndex]=maxi;
        }
        dp=temp;
    }
    return dp[3];

}

Unique Paths

Recursion

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==1 && n==1) return 1;
        if(m<0 || n<0) return 0;
        int l=uniquePaths(m-1,n);
        int r=uniquePaths(m,n-1);
        return l+r;
    }
};

Memoization

class Solution {
public:
    int recursion(int m,int n ,vector<vector<int>> &dp){
        if(m==1 && n==1) return 1;
        if(m<0 || n<0) return 0;
        if(dp[m][n]!=-1) return dp[m][n];
        int l=recursion(m-1,n,dp);
        int r=recursion(m,n-1,dp);
        return dp[m][n]=l+r;
    }
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
        return recursion(m,n,dp);
    }
};

Tabulation

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0)
                dp[i][j]=1;
                else
                {
                int l=0,r=0;
                if(i>0) l=dp[i-1][j];
                if(j>0) r=dp[i][j-1];
                dp[i][j]=l+r;
                }
            }
        }
        return dp[m-1][n-1];
    }
};

Minimum Path Sum

Recursion+Memoization

class Solution {
public:
    int recursion(int m,int n,vector<vector<int>> &grid,vector<vector<int>>&dp){
        if(m==0 && n==0) return grid[m][n];
        if(m<0 || n<0) return INT_MAX;
        if(dp[m][n]!=-1) return dp[m][n];
        int l=recursion(m-1,n,grid,dp);
        int r=recursion(m,n-1,grid,dp);
        return dp[m][n]=grid[m][n]+min(l,r);
    }
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m==0) return 0;
        int n=grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,-1));
        return recursion(m-1,n-1,grid,dp);
    }
};

Tabulation

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m==0) return 0;
        int n=grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        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];
               else {
                   int l=INT_MAX,r=INT_MAX;
                   if(i>0) l=grid[i][j]+dp[i-1][j];
                   if(j>0) r=grid[i][j]+dp[i][j-1];
                    dp[i][j]=min(l,r);
               }

            }
        }
        return dp[m-1][n-1];
    }
};

Unique Paths II

Recursion+Memoization

class Solution {
public:
    int recursion(int m,int n,vector<vector<int>> &dp,vector<vector<int>> &grid){
        if(m==0 && n==0) return 1;
        if(m<0 || n<0 || grid[m][n]==1) return 0;
        int l=0,r=0;
        if(dp[m][n]!=-1) return dp[m][n];
        if(m>0) l=recursion(m-1,n,dp,grid);
        if(n>0) r=recursion(m,n-1,dp,grid);
        return dp[m][n]=l+r;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m==0) return 0;
        int n=grid[0].size();
        if(grid[m-1][n-1]) return 0;
        if(grid[0][0]) return 0;
        vector<vector<int>> dp(m,vector<int>(n,-1));
        return recursion(m-1,n-1,dp,grid);
    }
};

Tabulation

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m==0) return 0;
        int n=grid[0].size();
        if(grid[m-1][n-1]) return 0;
        if(grid[0][0]) return 0;
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0) dp[i][j]=1;
                else {
                    if(grid[i][j]==1) dp[i][j]=0;
                    else {
                        int l=0,r=0;
                        if(i>0) l=dp[i-1][j];
                        if(j>0) r=dp[i][j-1];
                        dp[i][j]=l+r;
                    }
                }
            }
        }
        return dp[m-1][n-1];
    }
};

Unique Paths III

class Solution {
public:
    int recursion(int i,int j,int fi,int fj,vector<vector<int>>&grid,int n,int m,int toVisit,vector<vector<int>> &dp){
        if(i==fi && j==fj){
            return (toVisit==1)?1:0;
        }
        if(i<0 || j <0 || i>=m || j >=n ||grid[i][j]==-1) return 0;
        // if(dp[i][j]!=-1) return dp[i][j];
        grid[i][j]=-1;
        int l=0,r=0,u=0,d=0;
        if(i>0) l=recursion(i-1,j,fi,fj,grid,n,m,toVisit-1,dp);
        if(j>0) r=recursion(i,j-1,fi,fj,grid,n,m,toVisit-1,dp);
        if(i<m) u=recursion(i+1,j,fi,fj,grid,n,m,toVisit-1,dp);
        if(j<n) d=recursion(i,j+1,fi,fj,grid,n,m,toVisit-1,dp);
        grid[i][j]=0;
        return r+l+u+d;
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
     int m=grid.size();
     if(m==0) return 0;
     int n=grid[0].size();
     int toVisit = 0;
     pair<int,int> start={-1,-1},end={-1,-1};
     vector<vector<int>> dp(n,vector<int>(m,-1));
     for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    start = {i, j};
                }
                if (grid[i][j] == 2) {
                    end = {i, j};
                }
                if (grid[i][j] != -1) {
                    toVisit++;
                }
            }
        }
     return recursion(start.first, start.second, end.first, end.second, grid, n, m,toVisit,dp);



    }
};

Triangle

Recursion

class Solution {
public:
    int recursion(vector<vector<int>>& triangle,vector<vector<int>>&dp,int i,int j,int n){
        if(i==n-1) return triangle[n-1][j];
        int d=recursion(triangle,dp,i+1,j,n);
        int dg=recursion(triangle,dp,i+1,j+1,n);
        return triangle[i][j]+min(d,dg);
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n,-1));
        return recursion(triangle,dp,0,0,n);
    }
};

Memoization

class Solution {
public:
    int recursion(vector<vector<int>>& triangle,vector<vector<int>>&dp,int i,int j,int n){
        if(i==n-1) return triangle[n-1][j];
        if(dp[i][j]!=-1) return dp[i][j];
        int d=recursion(triangle,dp,i+1,j,n);
        int dg=recursion(triangle,dp,i+1,j+1,n);
        return dp[i][j]=triangle[i][j]+min(d,dg);
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n,-1));
        return recursion(triangle,dp,0,0,n);
    }
};

Tabulation

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int j=0;j<n;j++) dp[n-1][j]=triangle[n-1][j];
        for(int i=n-2;i>=0;i--){
            for(int j=i;j>=0;j--){
                 int d=dp[i+1][j];
                 int dg=dp[i+1][j+1];
                 dp[i][j]=triangle[i][j]+min(d,dg);
            }
        }
        return dp[0][0];
    }
};

Minimum Falling Path Sum

Recursion + Memoization

class Solution {
public:
    int recursion(vector<vector<int>> &dp, vector<vector<int>>& mat, int row, int col, int n) {
        if (col < 0 || col >= n || row >= n) return 1e9;
        if (row == n - 1) return mat[row][col];
        if (dp[row][col] != -1) return dp[row][col];
        int down = recursion(dp, mat, row + 1, col, n);
        int downDiag = recursion(dp, mat, row + 1, col + 1, n);
        int upperDiag = recursion(dp, mat, row + 1, col - 1, n);
        return dp[row][col] = mat[row][col] + min({down, downDiag, upperDiag});
    }
    int minFallingPathSum(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        int ans = 1e9;
        for (int col = 0; col < n; col++) {
            ans = min(ans, recursion(dp, mat, 0, col, n));
        }

        return ans;
    }
};

Recursion + Memoization(Reverse)

class Solution {
public:
    int recursion(vector<vector<int>> &dp, vector<vector<int>>& mat, int row, int col, int n) {
        if (col < 0 || col >= n) return 1e9;
        if (row == 0) return mat[row][col];
        if (dp[row][col] != -1) return dp[row][col];
        int down = recursion(dp, mat, row - 1, col, n);
        int downDiag = recursion(dp, mat, row - 1, col - 1, n);
        int upperDiag = recursion(dp, mat, row - 1, col + 1, n);
        return dp[row][col] = mat[row][col] + min({down, downDiag, upperDiag});
    }
    int minFallingPathSum(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));

        int ans = 1e9;
        for (int col = 0; col < n; col++) {
            ans = min(ans, recursion(dp, mat, n-1, col, n));
        }

        return ans;
    }
};

Tabulation

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<vector<int>> dp(n, vector<int>(n, 1e9));
        for(int j=0;j<n;j++) dp[0][j]= mat[0][j];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==0) continue;
                int down=INT_MAX,downDiag=INT_MAX,upperDiag=INT_MAX;
                down=dp[i-1][j];
                if(j>0) downDiag=dp[i-1][j-1];
                if(j<n-1)upperDiag=dp[i-1][j+1];
                dp[i][j]=mat[i][j]+min({down,downDiag,upperDiag});
            }
        }
        int ans = 1e9;
        for (int col = 0; col < n; col++) {
            ans=min(ans,dp[n-1][col]);
        }

        return ans;
    }
};

Chocolated Pickup 3D DP

Recursion

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    int recursion(int i,int j1,int j2,int n,int m,vector<vector<int>> &grid){
        if(j1<0 || j2<0 || j1>=m || j2>=m) return -1e8;
        if(i==n-1){
            if(j1==j2) return grid[i][j1];
            else return grid[i][j1]+grid[i][j2];
        }
        int maxi=-1e8;
    // there will be 9 ways (+1,0,-1)*3 then writting in the loop;
        for(int dj1=-1;dj1<=1;dj1++){
            for(int dj2=-1;dj2<=1;dj2++){
                int value=0;
                if(j1==j2) value=grid[i][j1];
                else value=grid[i][j1]+grid[i][j2];
                value+=recursion(i+1,j1+dj1,j2+dj2,n,m,grid);
                maxi=max(maxi,value);
            }
        }
        return maxi;
    }
    int solve(int n, int m, vector<vector<int>>& grid) {
        // code
        return recursion(0,0,m-1,n,m,grid);
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> grid;
        for (int i = 0; i < n; i++) {
            vector<int> temp;
            for (int j = 0; j < m; j++) {
                int x;
                cin >> x;
                temp.push_back(x);
            }
            grid.push_back(temp);
        }

        Solution obj;
        cout << obj.solve(n, m, grid) << "\n";
    }
    return 0;
}
// } Driver Code Ends

Memoization

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    int recursion(int i,int j1,int j2,int n,int m,vector<vector<int>> &grid,vector<vector<vector<int>>>&dp){
        if(j1<0 || j2<0 || j1>=m || j2>=m) return -1e8;
        if(i==n-1){
            if(j1==j2) return grid[i][j1];
            else return grid[i][j1]+grid[i][j2];
        }
        if(dp[i][j1][j2]!=-1) return dp[i][j1][j2];
        int maxi=-1e8;
    // there will be 9 ways (+1,0,-1)*3 then writting in the loop;
        for(int dj1=-1;dj1<=1;dj1++){
            for(int dj2=-1;dj2<=1;dj2++){
                int value=0;
                if(j1==j2) value=grid[i][j1];
                else value=grid[i][j1]+grid[i][j2];
                value+=recursion(i+1,j1+dj1,j2+dj2,n,m,grid,dp);
                maxi=max(maxi,value);
            }
        }
        return dp[i][j1][j2]=maxi;
    }
    int solve(int n, int m, vector<vector<int>>& grid) {
        // code
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int>(m,-1)));
        return recursion(0,0,m-1,n,m,grid,dp);
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> grid;
        for (int i = 0; i < n; i++) {
            vector<int> temp;
            for (int j = 0; j < m; j++) {
                int x;
                cin >> x;
                temp.push_back(x);
            }
            grid.push_back(temp);
        }

        Solution obj;
        cout << obj.solve(n, m, grid) << "\n";
    }
    return 0;
}
// } Driver Code Ends

Tabulation

class Solution {
  public:
    int recursion(int i,int j1,int j2,int n,int m,vector<vector<int>> &grid,vector<vector<vector<int>>>&dp){
        if(j1<0 || j2<0 || j1>=m || j2>=m) return -1e8;
        if(i==n-1){
            if(j1==j2) return grid[i][j1];
            else return grid[i][j1]+grid[i][j2];
        }
        if(dp[i][j1][j2]!=-1) return dp[i][j1][j2];
        int maxi=-1e8;
        for(int dj1=-1;dj1<=1;dj1++){
            for(int dj2=-1;dj2<=1;dj2++){
                int value=0;
                if(j1==j2) value=grid[i][j1];
                else value=grid[i][j1]+grid[i][j2];
                value+=recursion(i+1,j1+dj1,j2+dj2,n,m,grid,dp);
                maxi=max(maxi,value);
            }
        }
        return dp[i][j1][j2]=maxi;
    }
    int solve(int n, int m, vector<vector<int>>& grid) {
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(m, -1e8)));
        for (int j1 = 0; j1 < m; j1++) {
            for (int j2 = 0; j2 < m; j2++) {
                if (j1 == j2) {
                    dp[n-1][j1][j2] = grid[n-1][j1];
                } else {
                    dp[n-1][j1][j2] = grid[n-1][j1] + grid[n-1][j2];
                }
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j1 = 0; j1 < m; j1++) {
                for (int j2 = 0; j2 < m; j2++) {
                    int maxi = -1e8;
                    for (int dj1 = -1; dj1 <= 1; dj1++) {
                        for (int dj2 = -1; dj2 <= 1; dj2++) {
                            int value = 0;
                            if (j1 == j2) {
                                value = grid[i][j1];
                            } else {
                                value = grid[i][j1] + grid[i][j2];
                            }
                            int newJ1 = j1 + dj1;
                            int newJ2 = j2 + dj2;
                            if (newJ1 >= 0 && newJ1 < m && newJ2 >= 0 && newJ2 < m) {
                                value += dp[i+1][newJ1][newJ2];
                            } else {
                                value += -1e8;
                            }

                            maxi = max(maxi, value);
                        }
                    }
                    dp[i][j1][j2] = maxi;
                }
            }
        }

        return dp[0][0][m-1];
    }

};

Subset Sum Problem

Recursion + Memoization

    bool recursion(vector<int> &arr,int ind,int target,vector<vector<int>> &dp){
        if(target==0) return true;
        if(ind==0) return arr[ind]==target;
        if(dp[ind][target]!=-1) return dp[ind][target]==1;
        bool notTake=recursion(arr,ind-1,target,dp);
        bool take=false;
        if(target>=arr[ind]){
            take=recursion(arr,ind-1,target-arr[ind],dp);
        }
        bool ans=(take || notTake);
        dp[ind][target]=(ans==true)?1:0;
        return dp[ind][target]==1?true:false;
    }
    bool isSubsetSum(vector<int>arr, int sum){
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(sum+1,-1));
        return recursion(arr,n-1,sum,dp);
    }

Tabulation

bool isSubsetSum(vector<int>arr, int sum){
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(sum+1,0));
        for(int i=0;i<n;i++) dp[i][0]=1;
        if(arr[0]<=sum)
        dp[0][arr[0]]=1;
        for(int i=1;i<n;i++){
            for(int j=1;j<=sum;j++){
                bool notTake=(dp[i-1][j]==1);
                bool take=false;
                if(j>=arr[i]){
                    take=(dp[i-1][j-arr[i]]==1);
                }
                bool ans=(take || notTake);
                dp[i][j]=(ans==true)?1:0;
            }
        }
        return dp[n-1][sum]==1;
    }

Partition Equal Subset Sum

class Solution {
public:
    bool recursion(vector<int> &nums,int sum,int ind,vector<vector<int>> &dp){
        if(sum==0) return true;
        if(ind<0 || sum<0) return false;
        if(ind==0) return sum==nums[0];
        if(dp[ind][sum]!=-1) return dp[ind][sum];
        bool notTake=recursion(nums,sum,ind-1,dp);
        bool take=recursion(nums,sum-nums[ind],ind-1,dp);
        bool ans=(take || notTake);
        dp[ind][sum]=((ans==true)?1:0);
        return dp[ind][sum]==1;

    }
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(begin(nums),end(nums),0);
        if(sum&1) return false;
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(sum/2+1,-1));
        return recursion(nums,sum/2,n-1,dp);
    }
};

Array partition with minimum difference

bool recursion(vector<vector<int>> &dp,vector<int>&arr,int ind,int target){
	if(target==0) return true;
	if(ind<0 || target<0) return false;
	bool notTake=recursion(dp,arr,ind-1,target);
	bool take=false;
        if (target >= arr[ind]) {
          take = recursion(dp, arr, ind - 1, target - arr[ind]);
        }
        int ans=(take|| notTake);
		dp[ind][target]=(ans==true)?1:0;
		return dp[ind][target]==1;
}
int minSubsetSumDifference(vector<int>& arr, int n)
{
	int sum=accumulate(begin(arr),end(arr),0LL);
	vector<vector<bool>> dp(n,vector<bool>(sum+1,0));
    for(int i=0;i<n;i++) dp[i][0]=1;
	if(arr[0]<=sum) dp[0][arr[0]]=1;
	for(int ind=1;ind<n;ind++){
		for(int target=1;target<=sum;target++){
			bool notTake=dp[ind-1][target];
			bool take=false;
			if(arr[ind]<=target) take=dp[ind-1][target-arr[ind]];
			dp[ind][target]=(take | notTake);

		}
	}
	// recursion(dp,arr,n-1,sum);
	int mini=1e9;
	for(int s1=0;s1<=sum/2;s1++){
		if(dp[n-1][s1]==1){
			 mini = min(mini, abs((sum - s1) - s1));
		}
	}
	return mini;
}

GFG Minimum sum partition

int minDifference(int arr[], int n)  {
	    // Your code goes here
	    int sum=accumulate(arr,arr+n,0);
	    vector<vector<bool>> dp(n,vector<bool>(sum,0));
	    for(int i=0;i<n;i++) dp[i][0]=true;
	    if(arr[0]<=sum) dp[0][arr[0]]=true;
	    for(int ind=1;ind<n;ind++){
	        for(int target=1;target<=sum;target++){
	            bool take=false;
	            bool notTake=dp[ind-1][target];
	            if(target>=arr[ind]) take=dp[ind-1][target-arr[ind]];
	            dp[ind][target]=(take | notTake);
	        }
	    }
	    int mini=1e9;
	    for(int s1=0;s1<=sum/2;s1++){
	        if(dp[n-1][s1]){
	            mini=min(mini,abs((sum-s1)-s1));
	        }
	    }
	    return mini;

	}

1.Why if(arr[0] <= sum) dp[0][arr[0]] = true;:
This is initializing the first element of the dp array. It means that if the first element arr[0] is less than or equal to the total sum, then it is possible to form a subset with this sum. This initialization is necessary to handle the base case for dynamic programming when processing subsequent elements.
2.Why if(dp[n-1][s1]) mini = min(mini, abs((sum-s1) - s1));:
Here, dp[n-1][s1] checks whether it’s possible to form a subset with sum s1 using all elements (up to index n-1). If so, you compute the absolute difference between sum - s1 (the sum of the other subset) and s1 and update the minimum difference (mini). The goal is to minimize the difference between the two subset sums.
3.Why use n-1:
n-1 represents the last element in the array arr when using 0-based indexing. The dynamic programming table dp has size n, where dp[i][target] tells if it’s possible to form the sum target using elements from arr[0] to arr[i]. Thus, dp[n-1] checks if it’s possible to form the sum using all elements from the array.

Optimized

int minSubsetSumDifference(vector<int>& arr, int n) {
    int sum = accumulate(arr.begin(), arr.end(), 0);
    vector<bool> dp(sum / 2 + 1, false);

    dp[0] = true;
    for (int num : arr) {
        for (int target = sum / 2; target >= num; target--) {
            dp[target] = dp[target] || dp[target - num];
        }
    }
    int mini = INT_MAX;
    for (int s1 = sum / 2; s1 >= 0; s1--) {
        if (dp[s1]) {
            mini = min(mini, abs((sum - s1) - s1));
        }
    }

    return mini;
}

Partition Equal Subset Sum

class Solution {
public:
    bool recursion(vector<int> &nums,int sum,int ind,vector<vector<int>> &dp){
        if(sum==0) return true;
        if(ind<0 || sum<0) return false;
        if(ind==0) return sum==nums[0];
        if(dp[ind][sum]!=-1) return dp[ind][sum];
        bool notTake=recursion(nums,sum,ind-1,dp);
        bool take=recursion(nums,sum-nums[ind],ind-1,dp);
        bool ans=(take || notTake);
        dp[ind][sum]=((ans==true)?1:0);
        return dp[ind][sum]==1;

    }
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(begin(nums),end(nums),0);
        if(sum&1) return false;
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(sum/2+1,-1));
        return recursion(nums,sum/2,n-1,dp);
    }
};

Partition to K Equal Sum Subsets

// class Solution {
// public:
//     bool recursion(vector<vector<int>> &dp,vector<int> &nums,int k,int ind,int target){
//           if(k==0) return true;
//           if(ind<0) return false;
//           if(dp[ind][target]!=-1) return dp[ind][target]==1;
//           if(target==0) {
//             bool x=recursion(dp,nums,k-1,ind,target);
//             dp[ind][target]=(x==true?1:0);
//             return x;
//            }
//            bool pick=false;
//            bool nonPick=recursion(dp,nums,k,ind-1,target);
//            if(target>=nums[ind]) pick=recursion(dp,nums,k,ind-1,target-nums[ind]);
//            bool ans=(pick || nonPick);
//            dp[ind][target]=(ans==true?1:0);
//            return ans;

//     }
//     bool canPartitionKSubsets(vector<int>& nums, int k) {
//         int n=nums.size();
//         sort(nums.begin(), nums.end(), greater<int>());

//         int sum=accumulate(begin(nums),end(nums),0);
//         int target=sum/k;
//         if (nums[0] > target) return false;
//         if(sum % k !=0) return false;
//         vector<vector<int>> dp(n,vector<int>(target+1,-1));
//         return recursion(dp,nums,k,n-1,target);
//     }
// };
class Solution {
public:
    bool canPartitionHelper(vector<int>& nums, vector<bool>& used, int target, int k, int start, int currSum) {
        if (k == 1) return true;
        if (currSum == target)
            return canPartitionHelper(nums, used, target, k - 1, 0, 0);

        for (int i = start; i < nums.size(); ++i) {
            if (!used[i] && currSum + nums[i] <= target) {
                used[i] = true;
                if (canPartitionHelper(nums, used, target, k, i + 1, currSum + nums[i]))
                    return true;
                used[i] = false;
            }
        }

        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false;

        vector<bool> used(nums.size(), false);
        return canPartitionHelper(nums, used, target, k, 0, 0);
    }
};

Perfect Sum Problem

int recursion(int sum,int ind,int arr[],vector<vector<int>> &dp){
	    if(ind<0) {
	        if(sum==0) return 1;
	        return 0;
	    }
	    if(dp[ind][sum]!=-1) return dp[ind][sum];
	    int pick=0;
	    int notPick=recursion(sum,ind-1,arr,dp);
	    if(sum>=arr[ind]) pick=recursion(sum-arr[ind],ind-1,arr,dp);
	    return dp[ind][sum]=(pick+notPick)%mod;

	}
	int perfectSum(int arr[], int n, int sum)
	{
	    vector<vector<int>> dp(n,vector<int>(sum+1,-1));
        return recursion(sum,n-1,arr,dp);
	}

Partitions with Given Difference

Same Problem on CN

int recursion(vector<vector<int>> &dp, vector<int> &arr, int ind, int target) {
    if(ind<0) {
         if (target == 0) return 1;
         return 0;
    }
    if (dp[ind][target] != -1) return dp[ind][target];

    int notPick = recursion(dp, arr, ind - 1, target);
    int pick = 0;
    if (target >= arr[ind]) pick = recursion(dp, arr, ind - 1, target - arr[ind]);

    return dp[ind][target] = (pick + notPick)%mod;
}

int countPartitions(int n, int d, vector<int>& arr) {
    int sum = accumulate(arr.begin(), arr.end(), 0);
    if ((sum + d) % 2 != 0) return 0;

    int target = (sum + d) / 2;
    vector<vector<int>> dp(n, vector<int>(target + 1, -1));

    return recursion(dp, arr, n - 1, target);
}

0-1 KnapSack Problem

int recursion(int target,vector<int> &wt,vector<int> &val,int ind,vector<vector<int>> &dp){
        if(ind==0){
            if(wt[0]<=target) return val[0];
            return 0;
        }
        if(dp[ind][target]!=-1) return dp[ind][target];
        int pick=INT_MIN;
        int notPick=0+recursion(target,wt,val,ind-1,dp);
        if(wt[ind]<=target) pick=val[ind]+recursion(target-wt[ind],wt,val,ind-1,dp);
        return dp[ind][target]=max(pick,notPick);

    }
    int knapSack(int target, vector<int>& wt, vector<int>& val) {
        // Your code here
        int n=wt.size();
        vector<vector<int>> dp(n,vector<int>(target+1,-1));
        return recursion(target,wt,val,n-1,dp);

    }

Coin Change Problem

Recursion+Memoization

class Solution {
public:
    int recursion(vector<int> &coins,vector<vector<int>>&dp,int ind,int amt){
        if(amt==0) return 0;
        if(ind< 0 || amt<0) return 1e9;
        if(dp[ind][amt]!=-1) return dp[ind][amt];
        int notPick=recursion(coins,dp,ind-1,amt);
        int pick=1e9;
        if(amt>=coins[ind]) pick=1+recursion(coins,dp,ind,amt-coins[ind]);
        return dp[ind][amt]=min(pick,notPick);
    }
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<vector<int>> dp(n,vector<int> (amount+1,-1));
        int result=recursion(coins,dp,n-1,amount);
        return result==1e9?-1:result;
    }
};

Tabulation

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<vector<int>> dp(n,vector<int> (amount+1,1e9));
        for(int i=0;i<n;i++) dp[i][0]=0;
        for(int i=0;i<n;i++){
            for(int amt=1;amt<=amount;amt++){
                 int notPick = (i > 0) ? dp[i - 1][amt] : 1e9;
                 int pick=1e9;
                 if(amt>=coins[i]) pick=1+dp[i][amt-coins[i]];
                 dp[i][amt]=min(pick,notPick);
            }
        }
       int result= dp[n-1][amount];
       return result==1e9?-1:result;
    }
};

Target Sum

class Solution {
public:
    int recursion(vector<vector<int>> &dp,vector<int> &nums,int ind,int target){
          if(ind==0) {
            if(target==0 && nums[0]==0) return 2;
            if(target==nums[0] || target==0) return 1;
            return 0;
          }
          if(dp[ind][target]!=-1) return dp[ind][target];
          int pick=0;
          int notPick=recursion(dp,nums,ind-1,target);
          if(target>=nums[ind]) pick=recursion(dp,nums,ind-1,target-nums[ind]);
          return dp[ind][target]=(pick+notPick);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=accumulate(begin(nums),end(nums),0);
         if (sum < abs(target) || (sum + target) % 2 != 0) return 0;
        int n=nums.size();
        target=(sum+target)/2;
        vector<vector<int>> dp(n,vector<int>(target+1,-1));
        return recursion(dp,nums,n-1,target);
    }
};

Longest Common Subsequence

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.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Recursion

class Solution {
public:
    int recursion(int i,int j,string text1,string text2){
        if(i<0 || j<0) return 0;
        if(text1[i]==text2[j]) return 1+recursion(i-1,j-1,text1,text2);
        return max(recursion(i-1,j,text1,text2),recursion(i,j-1,text1,text2));
    }
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        return recursion(n-1,m-1,text1,text2);
    }
};

Memoization

class Solution {
public:
    int recursion(int i,int j,string text1,string text2,vector<vector<int>> &dp){
        if(i<0 || j<0) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(text1[i]==text2[j]) return dp[i][j]=1+recursion(i-1,j-1,text1,text2,dp);
        return dp[i][j]= max(recursion(i-1,j,text1,text2,dp),recursion(i,j-1,text1,text2,dp));
    }
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        vector<vector<int>> dp(n,vector<int>(m,-1));
        return recursion(n-1,m-1,text1,text2,dp);
    }
};

Shifted Memoization

class Solution {
public:
    int recursion(int i,int j,string text1,string text2,vector<vector<int>> &dp){
        if(i==0 || j==0) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(text1[i-1]==text2[j-1]) return dp[i][j]=1+recursion(i-1,j-1,text1,text2,dp);
        return dp[i][j]= max(recursion(i-1,j,text1,text2,dp),recursion(i,j-1,text1,text2,dp));
    }
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
        return recursion(n,m,text1,text2,dp);
    }
};

Why Shifted Memoization

1. Why is the memoization array shifted by 1?
The memoization array is shifted by 1 because the base case of the recursion is when i or j becomes 0. In the recursion, we are using 0-based indexing, so we need to shift the indices by 1 to match the base case of the recursion.

Tabulation

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=0;i<n;i++) dp[i][0]=0;
        for(int j=0;j<m;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(text1[i-1]==text2[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};

Space Optimized Tabulation

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        vector<int> prev(m+1,0),curr(m+1,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(text1[i-1]==text2[j-1]) curr[j]=1+prev[j-1];
                else curr[j]=max(prev[j],curr[j-1]);
            }
            prev=curr;
        }
        return curr[m];
    }
};

Print LCS

Method 1

string findLCS(int n, int m,string &s1, string &s2){
	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(s1[i-1]==s2[j-1]) dp[i][j]=1+dp[i-1][j-1];
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int len=dp[n][m];
	int i=n,j=m;
	string ans;
	int ind=len-1;
	while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
		ans.push_back(s1[i-1]);
		   ind--;
		   i--;
		   j--;
		}
		else if(dp[i-1][j]>dp[i][j-1]){
            i--;
		}
		else {
           j--;
		}
	}
	reverse(begin(ans),end(ans));
	return ans;
}

Method 2

string findLCS(int n, int m,string &s1, string &s2){
	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(s1[i-1]==s2[j-1]) dp[i][j]=1+dp[i-1][j-1];
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int len=dp[n][m];
	int i=n,j=m;
	string ans(len,'-');
	int ind=len-1;
	while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
           ans[ind]=s1[i-1];
		   ind--;
		   i--;
		   j--;
		}
		else if(dp[i-1][j]>dp[i][j-1]){
            i--;
		}
		else {
           j--;
		}
	}
	return ans;
}

Print all LCS sequences

You are given two strings s and t. Now your task is to print all longest common subsequences in lexicographical order.

Note: A subsequence is derived from another string by deleting some or none of the elements without changing the order of the remaining elements.

Example 1:

Input: s = abaaa t = baabaca

Output:

aaaa
abaa
baaa

Explanation: Length of LCS is 4. In lexicographical order, the longest common subsequences are: aaaa, abaa, baaa

Example 2:

Input: s = aaa t = a

Output:

a

Your Task:

You do not need to read or print anything. Your task is to complete the function all_longest_common_subsequences() which takes strings s and t as first and second parameters respectively and returns a list of strings that contains all possible longest common subsequences in lexicographical order.

Expected Time Complexity:

O(n <sup>3 </sup>)

Expected Space Complexity:

O(k * n) where k is a constant less than n.

Constraints:

• 1 ≤ Length of both strings ≤ 50

TLE

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    void recursion(vector<string> &ans,string &ds,int i,int j,vector<vector<int>> &dp,string s,string t){
        if(i==0 && j==0){
            reverse(begin(ds),end(ds));
            ans.push_back(ds);
            reverse(begin(ds),end(ds));
            return;
        }
        if(s[i-1]==t[j-1]){
            ds.push_back(s[i-1]);
            recursion(ans,ds,i-1,j-1,dp,s,t);
            ds.pop_back();
        }
       else {
    if (i > 0 && dp[i-1][j] == dp[i][j]) recursion(ans, ds, i-1, j, dp, s, t);
    if (j > 0 && dp[i][j-1] == dp[i][j]) recursion(ans, ds, i, j-1, dp, s, t);
}
    }
    vector<string> all_longest_common_subsequences(string s, string t) {
        int n=s.size(),m=t.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(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        vector<string> ans;
        string ds;
        recursion(ans,ds,n,m,dp,s,t);
        set<string> st(ans.begin(),ans.end());
        vector<string> ans2(st.begin(),st.end());
        return ans2;
    }
};


//{ Driver Code Starts.
int main() {
    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        Solution ob;
        vector<string> ans = ob.all_longest_common_subsequences(s, t);
        for (auto i : ans)
            cout << i << " ";
        cout << "\n";
    }
    return 0;
}

// } Driver Code Ends

Again TLE

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    void recursion(vector<vector<set<string>>> &memo,string &ds,int i,int j,vector<vector<int>> &dp,string s,string t,set<string>&temp){
        if(i==0 && j==0){
            reverse(begin(ds),end(ds));
            temp.insert(ds);
            reverse(begin(ds),end(ds));
            return;
        }
        if(!memo[i][j].empty()) {
            // temp.insert(memo[i][j].begin(),memo[i][j].end());
            // return;
            for (const string &subseq : memo[i][j]) {
                temp.insert(subseq);
            }
            return;
        }
        if(s[i-1]==t[j-1]){
            ds.push_back(s[i-1]);
            recursion(memo,ds,i-1,j-1,dp,s,t,temp);
            ds.pop_back();
        }
       else {
    if (i > 0 && dp[i-1][j] == dp[i][j]) recursion(memo, ds, i-1, j, dp, s, t,temp);
    if (j > 0 && dp[i][j-1] == dp[i][j]) recursion(memo, ds, i, j-1, dp, s, t,temp);
        }
        temp.insert(memo[i][j].begin(),memo[i][j].end());
    }
    vector<string> all_longest_common_subsequences(string s, string t) {
        int n=s.size(),m=t.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(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }

        string ds;
        vector<vector<set<string>>> memo(n+1,vector<set<string>>(m+1));
        set<string>temp;
        recursion(memo,ds,n,m,dp,s,t,temp);
        return vector<string>(temp.begin(), temp.end());
    }
};


//{ Driver Code Starts.
int main() {
    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        Solution ob;
        vector<string> ans = ob.all_longest_common_subsequences(s, t);
        for (auto i : ans)
            cout << i << " ";
        cout << "\n";
    }
    return 0;
}

// } Driver Code Ends

Optimized with Map

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    void recursion(unordered_map<string,bool> &mp,string &ds,int i,int j,vector<vector<int>> &dp,string s,string t,set<string>&temp){
        if(i==0 && j==0){
            reverse(begin(ds),end(ds));
            temp.insert(ds);
            reverse(begin(ds),end(ds));
            return;
        }
        string key=to_string(i)+','+to_string(j)+ds;
        if(mp.find(key)!=mp.end()) return;
        mp[key]=true;
        if(s[i-1]==t[j-1]){
            ds.push_back(s[i-1]);
            recursion(mp,ds,i-1,j-1,dp,s,t,temp);
            ds.pop_back();
        }
       else {
    if (i > 0 && dp[i-1][j] == dp[i][j]) recursion(mp, ds, i-1, j, dp, s, t,temp);
    if (j > 0 && dp[i][j-1] == dp[i][j]) recursion(mp, ds, i, j-1, dp, s, t,temp);
        }
    }
    vector<string> all_longest_common_subsequences(string s, string t) {
        int n=s.size(),m=t.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(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }

        string ds;
        unordered_map<string,bool> mp;
        set<string>temp;
        recursion(mp,ds,n,m,dp,s,t,temp);
        return vector<string>(temp.begin(), temp.end());
    }
};


//{ Driver Code Starts.
int main() {
    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        Solution ob;
        vector<string> ans = ob.all_longest_common_subsequences(s, t);
        for (auto i : ans)
            cout << i << " ";
        cout << "\n";
    }
    return 0;
}

// } Driver Code Ends

Longest Common Substring

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    int longestCommonSubstr(string s, string t) {
        // your code here
        int n=s.size();
        int m=t.size();
        int ans=0;
        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]==t[j-1]) {
                    dp[i][j]=1+dp[i-1][j-1];
                    ans=max(ans,dp[i][j]);
                }
            }
        }
        return ans;
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s1, s2;
        cin >> s1 >> s2;
        Solution ob;

        cout << ob.longestCommonSubstr(s1, s2) << endl;
    }
}
// } Driver Code Ends

Longest Palindromic Subsequence

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t=s;
        reverse(begin(t),end(t));
        int n=s.size();
        vector<vector<int>>dp(n+1,vector<int>(n+1,0));
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            if(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max({dp[i-1][j],dp[i][j-1]});
          }
        }
        return dp[n][n];
    }
};

Delete Operation for Two Strings

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=1+dp[i-1][j-1];
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return m+n-2*dp[m][n];

    }
};

Shortest Common Supersequence

class Solution {
public:
    string shortestCommonSupersequence(string s, string t) {
        int n=s.size(),m=t.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(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        int i=n,j=m;
        string ans;
        while(i>0 && j>0){
           if(s[i-1]==t[j-1]){
             ans+=s[i-1];
             i--;
             j--;
           }
           else {
            if(dp[i-1][j]>dp[i][j-1]){
                ans+=s[i-1];
                i--;
            }
            else {
                ans+=t[j-1];
                j--;
            }
           }
        }
        while(i>0){
          ans+=s[i-1];
          i--;
        }
        while(j>0){
            ans+=t[j-1];
            j--;
        }
        reverse(begin(ans),end(ans));
        return ans;
    }
};

Distinct Subsequences

Recursion

class Solution {
public:
    int recursion(string s,string t,int i,int j){
        if(j<0) return 1;
        if(i<0) return 0;
        if(s[i]==t[j]){
            return recursion(s,t,i-1,j-1)+recursion(s,t,i-1,j);
        }
        return recursion(s,t,i-1,j);
    }
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        return recursion(s,t,n-1,m-1);
    }
};

Memoization

class Solution {
public:
    int recursion(string s,string t,int i,int j,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]=recursion(s,t,i-1,j-1,dp)+recursion(s,t,i-1,j,dp);
        }
        return dp[i][j]=recursion(s,t,i-1,j,dp);
    }
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n,vector<int>(m,-1));
        return recursion(s,t,n-1,m-1,dp);
    }
};

Shifted Memoization

class Solution {
public:
    int recursion(string s,string t,int i,int j,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-1]==t[j-1]){
            return dp[i][j]=recursion(s,t,i-1,j-1,dp)+recursion(s,t,i-1,j,dp);
        }
        return dp[i][j]=recursion(s,t,i-1,j,dp);
    }
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
        return recursion(s,t,n,m,dp);
    }
};

Tabulation

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<double>> dp(n+1,vector<double>(m+1,0));
        for(int i=0;i<=n;i++) dp[i][0]=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 (int)dp[n][m];
    }
};

Space Optimized Tabulation

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<double> prev(m+1,0),curr(m+1,0);
        prev[0]=curr[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i-1]==t[j-1]) curr[j]=prev[j-1]+prev[j];
                else curr[j]=prev[j];
            }
            prev=curr;
        }
        return (int)prev[m];
    }
};

Edit Distance

Recursive

class Solution {
public:
    int recursion(int i,int j,string s,string t){
        if(i<0) return j+1;
        if(j<0) return i+1;
        if(s[i]==t[j]) return 0+recursion(i-1,j-1,s,t);
        int insertion=1+recursion(i,j-1,s,t);
        int deletion=1+recursion(i-1,j,s,t);
        int replacement=1+recursion(i-1,j-1,s,t);
        return min({insertion,deletion,replacement});
    }
    int minDistance(string s, string t) {
        int n=s.size();
        int m=t.size();
        return recursion(n-1,m-1,s,t);
    }
};

Memoization

class Solution {
public:
    int recursion(int i,int j,string s,string t,vector<vector<int>> &dp){
        if(i<0) return j+1;
        if(j<0) return i+1;
        if(dp[i][j]!=-1) return dp[i][j];
        if(s[i]==t[j]) return dp[i][j]=0+recursion(i-1,j-1,s,t,dp);
        int insertion=1+recursion(i,j-1,s,t,dp);
        int deletion=1+recursion(i-1,j,s,t,dp);
        int replacement=1+recursion(i-1,j-1,s,t,dp);
        return dp[i][j]=min({insertion,deletion,replacement});
    }
    int minDistance(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n,vector<int>(m,-1));
        return recursion(n-1,m-1,s,t,dp);
    }
};

Shifted Memoization

class Solution {
public:
    int recursion(int i,int j,string s,string t,vector<vector<int>> &dp){
        if(i==0) return j;
        if(j==0) return i;
        if(dp[i][j]!=-1) return dp[i][j];
        if(s[i-1]==t[j-1]) return dp[i][j]=0+recursion(i-1,j-1,s,t,dp);
        int insertion=1+recursion(i,j-1,s,t,dp);
        int deletion=1+recursion(i-1,j,s,t,dp);
        int replacement=1+recursion(i-1,j-1,s,t,dp);
        return dp[i][j]=min({insertion,deletion,replacement});
    }
    int minDistance(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
        return recursion(n,m,s,t,dp);
    }
};

Tabulation

class Solution {
public:
    int minDistance(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=0;i<=n;i++) dp[i][0]=i;
        for(int j=0;j<=m;j++) dp[0][j]=j;
        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];
                else dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
        return dp[n][m];
    }
};

Space Optimized Tabulation

class Solution {
public:
    int minDistance(string s, string t) {
        int n=s.size();
        int m=t.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        vector<int> prev(m+1,0),curr(m+1,0);
        for(int j=0;j<=m;j++) prev[j]=j;
        for(int i=1;i<=n;i++){
            curr[0]=i;
            for(int j=1;j<=m;j++){
                if(s[i-1]==t[j-1]) curr[j]=prev[j-1];
                else curr[j]=min({prev[j],curr[j-1],prev[j-1]})+1;
            }
            prev=curr;
        }
        return prev[m];
    }
};

Wildcard Matching

Recursion

class Solution {
public:
    bool recursion(int i,int j,string p,string s){
       if(i<0 && j<0) return true;
       if(i<0 && j>=0) return false;
       if(j<0 && i>=0) {
        for(int x=0;x<=i;x++){
            if(p[x]!='*') return false;
        }
        return true;
       }
       if(p[i]==s[j] || p[i]=='?') return recursion(i-1,j-1,p,s);
       if(p[i]=='*'){
        return recursion(i-1,j,p,s) || recursion(i,j-1,p,s);
       }
       return false;
    }
    bool isMatch(string s, string p) {
        int n=s.size();
        int m=p.size();
        return recursion(m-1,n-1,p,s);
    }
};

Memoization

MLE(Memory Limit Exceeded)

class Solution {
public:
    bool recursion(int i,int j,string p,string s,vector<vector<int>> &dp){
       if(i<0 && j<0) return true;
       if(i<0 && j>=0) return false;
       if(j<0 && i>=0) {
        for(int x=0;x<=i;x++){
            if(p[x]!='*') return false;
        }
        return true;
       }
       if(dp[i][j]!=-1) return dp[i][j]==1;
       if(p[i]==s[j] || p[i]=='?') return dp[i][j]=recursion(i-1,j-1,p,s,dp);
       if(p[i]=='*'){
        return dp[i][j]=(recursion(i-1,j,p,s,dp) || recursion(i,j-1,p,s,dp));
       }
       return dp[i][j]=false;
    }
    bool isMatch(string s, string p) {
        int n=s.size();
        int m=p.size();
        vector<vector<int>> dp(m,vector<int> (n,-1));
        return recursion(m-1,n-1,p,s,dp);
    }
};

Shifted Memoization

MLE(Memory Limit Exceeded)

class Solution {
public:
    bool recursion(int i,int j,string p,string s,vector<vector<int>> &dp){
       if(i==0 && j==0) return true;
       if(i==0 && j>0) return false;
       if(j==0 && i>0) {
        for(int x=0;x<i;x++){
            if(p[x]!='*') return false;
        }
        return true;
       }
       if(dp[i][j]!=-1) return dp[i][j]==1;
       if(p[i-1]==s[j-1] || p[i-1]=='?') return dp[i][j]=recursion(i-1,j-1,p,s,dp);
       if(p[i-1]=='*'){
        return dp[i][j]=(recursion(i-1,j,p,s,dp) || recursion(i,j-1,p,s,dp));
       }
       return dp[i][j]=false;
    }
    bool isMatch(string s, string p) {
        int n=s.size();
        int m=p.size();
        vector<vector<int>> dp(m+1,vector<int> (n+1,-1));
        return recursion(m,n,p,s,dp);
    }
};

Tabulation

class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size();
        int m=p.size();
        vector<vector<bool>> dp(m+1,vector<bool> (n+1,0));
        dp[0][0]=true;
        for(int j=1;j<=n;j++) dp[0][j]=false;
        for(int i=1;i<=m;i++){
            int flag=true;
            for(int x=0;x<i;x++){
                if(p[x]!='*') {
                    flag=false;
                    break;
                }
            }
             dp[i][0]=flag;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p[i-1]==s[j-1] || p[i-1]=='?') dp[i][j]=dp[i-1][j-1];
                if(p[i-1]=='*') dp[i][j]= (dp[i-1][j] || dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

Space Optimized Tabulation

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=p.size();
        int n=s.size();
        vector<bool> prev(n+1,0),curr(n+1,0);
        prev[0]=1;
        for(int j=1;j<=n;j++) prev[j]=false;
        for(int i=1;i<=m;i++){
            bool flag=true;
            for(int x=1;x<=i;x++){
                if(p[x-1]!='*') {
                    flag=false;
                    break;
                }
            }
             curr[0]=flag;
            for(int j=1;j<=n;j++){
                if(p[i-1]==s[j-1] || p[i-1]=='?') curr[j]=prev[j-1];
                else if(p[i-1]=='*') curr[j]= (prev[j] || curr[j-1]);
                else curr[j]=false;
            }
            prev=curr;
        }
        return prev[n];
    }
};

DP on Stocks

Best Time to Buy and Sell Stock

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mini=INT_MAX;
        int ans=0;
        for(int i=0;i<prices.size();i++){
            ans=max(ans,prices[i]-mini);
            mini=min(mini,prices[i]);
        }
        return ans;
    }
};

Best Time to Buy and Sell Stock II

Recursive

class Solution {
public:
    int recursion(int i,int n,bool buy,vector<int> &prices){
        if(i==n) return 0;
        if(buy){
             // buying here iska matlab pesa jayega
            int take=-prices[i]+recursion(i+1,n,false,prices); //profit
            int notTake=0+recursion(i+1,n,true,prices);
            return max(take,notTake);
        }
        else {
            // selling here iska matlab pesa aayega
            int take=prices[i]+recursion(i+1,n,true,prices);  //profit
            int notTake=recursion(i+1,n,false,prices);
            return max(take,notTake);
        }
    }
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        return recursion(0,n,true,prices);
    }
};
### Memoization
```cpp
class Solution {
public:
    int recursion(int i,int n,bool buy,vector<int> &prices,vector<vector<int>> &dp){
        if(i==n) return 0;
        if(dp[i][buy]!=-1) return dp[i][buy];
        if(buy){
             // buying here iska matlab pesa jayega
            int take=-prices[i]+recursion(i+1,n,false,prices,dp); //profit
            int notTake=0+recursion(i+1,n,true,prices,dp);
            return dp[i][buy]=max(take,notTake);
        }
        else {
            // selling here iska matlab pesa aayega
            int take=prices[i]+recursion(i+1,n,true,prices,dp);  //profit
            int notTake=recursion(i+1,n,false,prices,dp);
            return dp[i][buy]=max(take,notTake);
        }
    }
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2,-1));
        return recursion(0,n,true,prices,dp);
    }
};

Tabulation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n+1,vector<int>(2,0));
        for(int i=n-1;i>=0;i--){
           for(int j=0;j<2;j++){
            if(j==1){
                int take=-prices[i]+dp[i+1][false];
                int notTake=dp[i+1][true];
                dp[i][j]=max(take,notTake);
            }
            else {
                int take=prices[i]+dp[i+1][true];
                int notTake=dp[i+1][false];
                dp[i][j]=max(take,notTake);
            }
           }
        }
        return dp[0][1];
    }
};

Space Optimized Tabulation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> prev(2,0),curr(2,0);
        for(int i=n-1;i>=0;i--){
           for(int j=0;j<2;j++){
            if(j==1){
                int take=-prices[i]+prev[false];
                int notTake=prev[true];
                curr[j]=max(take,notTake);
            }
            else {
                int take=prices[i]+prev[true];
                int notTake=prev[false];
                curr[j]=max(take,notTake);
            }
           }
           prev=curr;
        }
        return prev[1];
    }
};

Best Time to Buy and Sell Stock III

Recursive + Memoization

class Solution {
public:
    int recursion(int i,bool buy,int cap,vector<int> &prices,vector<vector<vector<int>>> &dp){
        if(cap==0) return 0;
        if(i==prices.size()) return 0;
        if(dp[i][buy][cap]!=-1) return dp[i][buy][cap];
        if(buy){
            int take=-prices[i]+recursion(i+1,false,cap,prices,dp);
            int notTake=recursion(i+1,true,cap,prices,dp);
            return dp[i][buy][cap]=max(take,notTake);
        }
        else {
            int take=prices[i]+recursion(i+1,true,cap-1,prices,dp);
            int notTake=recursion(i+1,false,cap,prices,dp);
            return dp[i][buy][cap]=max(take,notTake);
        }
    }
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(2,vector<int>(3,-1)));
        return recursion(0,true,2,prices,dp);
    }
};

Tabulation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0 || n == 1)
            return 0;
        vector<vector<vector<int>>> dp(
            n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
        for (int i = n - 1; i >= 0; i--) {
            for (int buy = 0; buy < 2; buy++) {
                for (int cap = 1; cap <=2; cap++) {
                    if (buy) {
                        int take = -prices[i] + dp[i + 1][false][cap];
                        int notTake = dp[i + 1][true][cap];
                        dp[i][buy][cap] = max(take, notTake);
                    } else {
                        int take = prices[i] + dp[i + 1][true][cap - 1];
                        int notTake = dp[i + 1][false][cap];
                        dp[i][buy][cap] = max(take, notTake);
                    }
                }
            }
        }
        return dp[0][1][2];
    }
};

Space Optimized Tabulation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0 || n == 1)
            return 0;
        vector<vector<int>> prev(2,vector<int>(3,0)),curr(2,vector<int>(3,0));
        for (int i = n - 1; i >= 0; i--) {
            for (int buy = 0; buy < 2; buy++) {
                for (int cap = 1; cap <=2; cap++) {
                    if (buy) {
                        int take = -prices[i] + prev[false][cap];
                        int notTake = prev[true][cap];
                        curr[buy][cap] = max(take, notTake);
                    } else {
                        int take = prices[i] + prev[true][cap - 1];
                        int notTake = prev[false][cap];
                        curr[buy][cap] = max(take, notTake);
                    }
                }
            }
            prev=curr;
        }
        return prev[1][2];
    }
};

Best Optimized

Memoization-

int f(int ind,int ts,int n,vector<int>&prices,vector<vector<int>>&dp)
{
    //base cases
    if(ind == n || ts ==4) return 0;
    if(dp[ind][ts] !=-1) return dp[ind][ts];
    if(ts%2==0)
    {
        return dp[ind][ts] = max(-prices[ind]+f(ind+1,ts+1,n,prices,dp),f(ind+1,ts,n,prices,dp));
    }
    else
    {
        return dp[ind][ts] = max(prices[ind]+f(ind+1,ts+1,n,prices,dp),f(ind+1,ts,n,prices,dp));
    }
}

int maxProfit(vector<int>& prices, int n)
{
    // Write your code here.
    vector<vector<int>>dp(n,vector<int>(4,-1));
    return f(0,0,n,prices,dp);
}

Tabulation-----

int maxProfit(vector<int>& prices, int n)
{
    // Write your code here.
    vector<vector<int>>dp(n+1,vector<int>(5,-1));
    for(int i=0;i<=4;i++)
    {
        dp[n][i] = 0;
    }
    for(int i=0;i<=n;i++)
    {
        dp[i][4]=0;
    }
    for(int ind=n-1;ind>=0;ind--)
    {
        for(int ts = 3;ts>=0;ts--)
        {
            if(ts%2==0)
            {
                dp[ind][ts] = max(-prices[ind]+dp[ind+1][ts+1],dp[ind+1][ts]);
            }
            else
            {
                dp[ind][ts] = max(prices[ind]+dp[ind+1][ts+1],dp[ind+1][ts]);
            }
        }
    }
    return dp[0][0];
}

1-D Space Optimisation-------

int maxProfit(vector<int>& prices, int n)
{
    // Write your code here.
   vector<int>ahead(5,-1),cur(5,-1);
    for(int i=0;i<=4;i++)
    {
        ahead[i] = 0;
    }
    cur[4]=0;
    for(int ind=n-1;ind>=0;ind--)
    {
        for(int ts = 3;ts>=0;ts--)
        {
            if(ts%2==0)
            {
                cur[ts] = max(-prices[ind]+ahead[ts+1],ahead[ts]);
            }
            else
            {
                cur[ts] = max(prices[ind]+ahead[ts+1],ahead[ts]);
            }
        }
        ahead = cur;
    }
    return ahead[0];
}

Best Time to Buy and Sell Stock IV

Direct Tabulation with previous learned concepts

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(2,vector<int>(k+1,0)));
        for(int i=n-1;i>=0;i--){
            for(int buy=0;buy<=1;buy++){
                for(int cap=1;cap<=k;cap++){
                    if(buy){
                        dp[i][buy][cap]=max(-prices[i]+dp[i+1][false][cap],dp[i+1][true][cap]);
                    }
                    else {
                        dp[i][buy][cap]=max(prices[i]+dp[i+1][true][cap-1],dp[i+1][false][cap]);
                    }
                }
            }
        }
        return dp[0][1][k];
    }
};

Best Time to Buy and Sell Stock with Cooldown

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        vector<vector<int>> dp(n+2,vector<int>(2,0));
        for(int i=n-1;i>=0;i--){
                    dp[i][1]=max(-prices[i]+dp[i+1][false],dp[i+1][true]);
                    dp[i][0]=max(prices[i]+dp[i+2][true],dp[i+1][false]);
        }
        return dp[0][1];
    }
};

Space Optimized

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> next1(2,0),curr(2,0),next2(2,0);
        for(int i=n-1;i>=0;i--){
                    curr[1]=max(-prices[i]+next1[false],next1[true]);
                    curr[0]=max(prices[i]+next2[true],next1[false]);
                    next2=next1;
                    next1=curr;
        }
        return next1[1];
    }
};

Best Time to Buy and Sell Stock with Transaction Fee

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<vector<int>> dp(n+1,vector<int>(2,0));
        for(int i=n-1;i>=0;i--){
            dp[i][1]=max(-prices[i]+dp[i+1][0],dp[i+1][1]);
             dp[i][0]=max(prices[i]+dp[i+1][1]-fee,dp[i+1][0]);
        }
        return dp[0][1];
    }
};

Space Optimized

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<int> next(2,0),curr(2,0);
        for(int i=n-1;i>=0;i--){
            curr[1]=max(-prices[i]+next[0],next[1]);
            curr[0]=max(prices[i]+next[1]-fee,next[0]);
            next=curr;
        }
        return next[1];
    }
};

DP on LIS

Longest Increasing Subsequence

Recursive

class Solution {
public:
    int recursion(int idx,int prevIdx,vector<int> &nums){
        if(idx==nums.size()) return 0;
        int notTake=recursion(idx+1,prevIdx,nums);
        int take=0;
        if(prevIdx==-1 || nums[idx]>nums[prevIdx]) take=1+recursion(idx+1,idx,nums);
        return max(take,notTake);
    }
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        return recursion(0,-1,nums);
    }
};

Memoization

class Solution {
public:
    int recursion(int idx,int prevIdx,vector<int> &nums,vector<vector<int>> &dp){
        if(idx==nums.size()) return 0;
        if(dp[idx][prevIdx+1]!=-1) return dp[idx][prevIdx+1];
        int notTake=recursion(idx+1,prevIdx,nums,dp);
        int take=0;
        if(prevIdx==-1 || nums[idx]>nums[prevIdx]) take=1+recursion(idx+1,idx,nums,dp);
        return dp[idx][prevIdx+1]=max(take,notTake);
    }
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(n+1,-1));
        return recursion(0,-1,nums,dp);
    }
};

Tabulation

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(n + 1, 0));
        for (int idx = n - 1; idx >= 0; idx--) {
            for (int prevIdx = idx-1; prevIdx >= -1; prevIdx--) {
                int notTake = dp[idx + 1][prevIdx+1];
                int take = 0;
                if (prevIdx == -1 || nums[idx] > nums[prevIdx])
                    take = 1 + dp[idx + 1][idx+1] ;
                dp[idx][prevIdx + 1] =max(take, notTake);
            }
        }
        return dp[0][0];
    }
};

Space Optimised Tabulation

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(n + 1, 0));
        vector<int> next(n+1,0),curr(n+1,0);
        for (int idx = n - 1; idx >= 0; idx--) {
            for (int prevIdx = idx-1; prevIdx >= -1; prevIdx--) {
                int notTake = next[prevIdx+1];
                int take = 0;
                if (prevIdx == -1 || nums[idx] > nums[prevIdx])
                    take = 1 + next[idx+1] ;
                curr[prevIdx + 1] =max(take, notTake);
            }
            next=curr;
        }
        return next[0];
    }
};

Best Optimized

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1,1);
        int maxi=1;
        for(int i=0;i<n;i++){
            for(int prev=0;prev<i;prev++){
                 if(nums[prev]<nums[i]){
                    dp[i]=max(dp[i],1+dp[prev]);
                 }
            }
            maxi=max(maxi,dp[i]);
        }
        return maxi;
    }
};

Print Longest Increasing Subsequence

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution {
  public:
    vector<int> longestIncreasingSubsequence(int n, vector<int>& arr) {
        // Code here
        vector<int> ans;
        vector<int> dp(n,1);
        vector<int> hash(n,0);
        int lastIndex=0;
        int maxi=1;
        for(int i=0;i<n;i++){
            hash[i]=i;
            for(int prev=0;prev<i;prev++){
                if(arr[i]>arr[prev] && 1+dp[prev]>dp[i]){
                    dp[i]=1+dp[prev];
                    hash[i]=prev;
                }
            }
            if(dp[i]>maxi){
                maxi=dp[i];
                lastIndex=i;
            }
        }
        vector<int> lis;
        lis.push_back(arr[lastIndex]);
        int index=1;
        while(hash[lastIndex]!=lastIndex){
            lastIndex=hash[lastIndex];
            lis.push_back(arr[lastIndex]);
        }
        reverse(begin(lis),end(lis));
        return lis;
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        vector<int> arr(N);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        Solution obj;
        vector<int> res = obj.longestIncreasingSubsequence(N, arr);
        for (auto x : res)
            cout << x << " ";
        cout << "\n";
    }
    return 0;
}
// } Driver Code Ends

LIS using Binary Search

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> temp;
        temp.push_back(nums[0]);
        for (int i = 1; i < n; i++) {
            if (nums[i] > temp.back())
                temp.push_back(nums[i]);
            else {
                int ind =
                    lower_bound(begin(temp), end(temp), nums[i]) - begin(temp);
                temp[ind] = nums[i];
            }
        }
        return temp.size();
    }
};

Largest Divisible Subset

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> dp(n,1);
        vector<int> hash(n);
        iota(hash.begin(),hash.end(),0);
        int maxi=0;
        int lastIndex=0;
        for(int i=0;i<n;i++){
            for(int prev=0;prev<i;prev++){
               if(nums[i]%nums[prev]==0 && dp[prev]+1>dp[i]){
                   dp[i]=dp[prev]+1;
                   hash[i]=prev;
               }
            }
            if(dp[i]>maxi){
                maxi=dp[i];
                lastIndex=i;
            }
        }
        vector<int> ans;
        ans.push_back(nums[lastIndex]);
        while(hash[lastIndex]!=lastIndex){
             lastIndex=hash[lastIndex];
             ans.push_back(nums[lastIndex]);
        }
        reverse(begin(ans),end(ans));
        return ans;
    }
};

Longest String Chain

class Solution {
public:
    static bool cmp(string &s1,string &s2){
        return s1.size()<s2.size();
    }
    bool checkPossible(string s1,string s2){
         if (s1.size() != s2.size() + 1) return false;
        int f=0,s=0;
        while(f<s1.size()){
            if(s<s2.size() && s1[f]==s2[s]){
                s++;
            }
            f++;
        }
        return s == s2.size();
    }
    int longestStrChain(vector<string>& words) {
        sort(begin(words),end(words),cmp);
        int n=words.size();
        vector<int> dp(n,1);
        int maxi=1;
        for(int i=0;i<n;i++){
            for(int prev=0;prev<i;prev++){
                if(checkPossible(words[i],words[prev]) && dp[i]<dp[prev]+1){
                     dp[i]=dp[prev]+1;
                }
            }
            if(dp[i]>maxi){
                maxi=max(dp[i],maxi);
            }
        }
        return maxi;
    }
};

Longest Bitonic Sequence

int longestBitonicSubsequence(vector<int>& arr, int n)
{
	// Write your code here.
        vector<int> dp1(n,1),dp2(n,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
				if(arr[i]>arr[j])
                dp1[i]=max(dp1[i],dp1[j]+1);
            }
        }
        for(int i=n-1;i>=0;i--){
            for(int j=n-1;j>i;j--){
				if(arr[i]>arr[j])
                dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            ans=max(ans,dp1[i]+dp2[i]-1);
        }
        return ans;
}

Number of Longest Increasing Subsequence

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1);
        vector<int> cnt(n,1);
        int maxi=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
               if(nums[i]>nums[j] && dp[i]<dp[j]+1){
                   dp[i]=dp[j]+1;
                   cnt[i]=cnt[j];
               }
               else if(nums[i]>nums[j] && dp[i]==dp[j]+1){
                   cnt[i]+=cnt[j];
               }
            }
            maxi=max(maxi,dp[i]);
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(dp[i]==maxi) ans+=cnt[i];
        }
        return ans;

    }
};

MCM(Matrix Chain Multiplication)

Matrix Chain Multiplication

Recursion

    int recursion(int i,int j,int arr[]){
        if(i==j) return 0;
        int mini=1e9;
        for(int k=i;k<j;k++){
            int steps=arr[i-1]*arr[k]*arr[j]+recursion(i,k,arr)+recursion(k+1,j,arr);
            mini=min(mini,steps);
        }
        return mini;
    }
    int matrixMultiplication(int N, int arr[])
    {
        // code here
        return recursion(1,N-1,arr);
    }

Memoisation

int recursion(int i,int j,int arr[],vector<vector<int>> &dp){
        if(i==j) return 0;
        int mini=1e9;
        if(dp[i][j]!=-1) return dp[i][j];
        for(int k=i;k<j;k++){
            int steps=arr[i-1]*arr[k]*arr[j]+recursion(i,k,arr,dp)+recursion(k+1,j,arr,dp);
            mini=min(mini,steps);
        }
        return dp[i][j]=mini;
    }
    int matrixMultiplication(int N, int arr[])
    {
        // code here
        vector<vector<int>> dp(N,vector<int>(N,-1));
        return recursion(1,N-1,arr,dp);
    }

Tabulation

int matrixMultiplication(int N, int arr[])
    {
        vector<vector<int>> dp(N,vector<int>(N,0));
        for(int i=N-1;i>=1;i--){
            for(int j=i+1;j<N;j++){
            int mini=1e9;
            for(int k=i;k<j;k++){
            int steps=arr[i-1]*arr[k]*arr[j]+dp[i][k]+dp[k+1][j];
            mini=min(mini,steps);
        }
         dp[i][j]=mini;
            }
        }
        return dp[1][N-1];
    }