medium-level-dp.cpp

// 🧠 MASTER DP SOLVING FRAMEWORK (USE FOR EVERY PROBLEM)

// Before every problem, follow this:

// 1) What changes in each recursive call? → state
// 2) What choices do I have? → transition
// 3) What is the smallest valid answer? → base case
// 4) Memoize repeated states
// 5) Convert to tabulation
// 6) Optimize space



// 🎯 HOW TO RECOGNIZE PATTERNS FAST

// Use this cheat sheet:

// Take / Not Take → Subsequence / Knapsack
// String compare → LCS / Edit Distance
// Previous smaller → LIS
// Grid moves → Matrix DP
// Min/Max path → Grid optimization





// 🟡 1) SUBSEQUENCE DP ⭐⭐⭐

// This family means:

// 👉 Take / Not Take pattern

// For every element:

// include it
// exclude it


// ⚡ B) Equal Partition
// 💡 Idea
// Split array into 2 equal sum subsets
// Mathematically:
// Need subset with sum = total_sum/2
// If total sum is odd → impossible
// 🧠 Algorithm
// State → dp[i][j] = is it possible to get sum j using first i elements
// Base → dp[0][0] = true (sum 0 with 0 elements)
// Transition → dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i]]
// ❓ Practice





#include<bits/stdc++.h>
using namespace std;
bool canPartition(vector<int>&arr){
    int n=arr.size();
    int total_sum=accumulate(arr.begin(),arr.end(),0);
    if(total_sum%2!=0) return false;
    int target=total_sum/2;
    vector<vector<bool>>dp(n+1,vector<bool>(target+1));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=target;j++){
            if(j==0){
                dp[i][j]=true;
            } 
            else if(i==0){
                dp[i][j]=false;
            }
            else{
                bool not_take=dp[i-1][j];
                bool take=false;
                if(j>=arr[i-1]){
                    take=dp[i-1][j-arr[i-1]];
                }
                dp[i][j]=not_take || take;
            }
        }
    }
    return dp[n][target];
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(canPartition(arr)){
        cout<<"Array can be partitioned into two equal sum subsets."<<endl;
    }
    else{
        cout<<"Array cannot be partitioned into two equal sum subsets."<<endl;
    }
    return 0;
}




// ⚡ C) Count Subsets with Sum K
// 💡 Recurrence
// dp[i][s]=dp[i−1][s]+dp[i−1][s−(ai−1)]
// 👉 Count subsets of first i elements that sum to s
// 🧠 Algorithm
// State: number of subsets of first i elements that sum to s
// Base: dp[0][0]=1 (one subset - empty set)
// Transition: dp[i][s]=dp[i−1][s]+dp[i−1][s−(ai−1)]
// ❓ Practice
// Boolean → replaced with count





#include<bits/stdc++.h>
using namespace std;
int countSubsets(vector<int>&arr ,int sum){
    int n=arr.size();
    vector<vector<int>>dp(n+1,vector<int>(sum+1));
    for(int i=0;i<=n;i++){
        for(int s=0;s<=sum;s++){
            if(s==0){
                dp[i][s]=1;
            }
            else if(i==0){
                dp[i][s]=0;
            }
            else{
                int not_take=dp[i-1][s];
                int take=0;
                if(s>=arr[i-1]){
                    take=dp[i-1][s-arr[i-1]];
                }
                dp[i][s]=not_take+take;
            }
        }
    }
    return dp[n][sum];
}
int main(){
    int n,sum;
    cin>>n>>sum;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Number of subsets with given sum: "<<countSubsets(arr,sum)<<endl;//output number of subsets with given sum if arr and sum are given as input arr=[2,3,5] and sum=5=> output is 2 (subsets are [5] and [2,3])
    return 0;
}





// ⚡ D) Minimum Subset Difference
// 💡 Math

// Partition into S1, S2 minimizing:
// |s1-s2|=∣total−2⋅s∣
// Need to find subset with sum s closest to total/2
// 🧠 Algorithm
// State: is it possible to get sum s using first i elements
// Base: dp[0][0]=true (sum 0 with 0 elements)
// Transition: dp[i][s]=dp[i-1][s] || dp[i-1][s-arr[i]]
// ❓ Practice
// arr=[1,2,3,9] → answer?
// Input: arr=[1,2,3,9]
// Output: 3 (partition [1,2,3] and [9], difference is 3)



#include<bits/stdc++.h>
using namespace std;
int minSubsetDifference(vector<int>&arr){
    int n=arr.size();
    int total_sum=accumulate(arr.begin(),arr.end(),0);
    int target=total_sum/2;
    vector<vector<bool>>dp(n+1,vector<bool>(target+1));
    for(int i=0;i<=n;i++){
        for(int s=0;s<=target;s++){
            if(s==0){
                dp[i][s]=true;
            }
            else if(i==0){
                dp[i][s]=false;
            }
            else{
                bool not_take=dp[i-1][s];
                bool take=false;
                if(s>=arr[i-1]){
                    take=dp[i-1][s-arr[i-1]];
                }
                dp[i][s]=not_take || take;
            }
        }
    }
    for(int s=target;s>=0;s--){
        if(dp[n][s]){
            return total_sum-2*s;
        }
    }
    return 0;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Minimum subset difference: "<<minSubsetDifference(arr)<<endl;//output minimum subset difference if arr is given as input arr=[1,2,3,9] and n is 4=> output is 3 (partition [1,2,3] and [9], difference is 3)
    return 0;
}





// 🟡 2) KNAPSACK PATTERN ⭐⭐⭐
// This is take / not take with value optimization
// For every element:
// include it and add value
// exclude it and keep value same
// ⚡ A) 0-1 Knapsack





// ⚡ A) 0/1 Knapsack ⭐⭐⭐
// 💡 Recurrence
// dp[i][W]=max(dp[i−1][W],val(i)+dp[i−1][W−wi​])
// 👉 Max value with weight limit W using first i items
// 🧠 Algorithm
// State: max value with weight limit W using first i items
// Base: dp[0][W]=0 (no items, no value)
// Transition: dp[i][W]=max(dp[i-1][W],val(i)+dp[i-1][W-wi])
// steps:
// 1) Define state and base case
// 2) Fill dp table using transition
// ❓ Practice
// weights=[1,2,3], values=[10,15,40], W=6 → answer?
// Input: weights=[1,2,3], values=[10,15,40], W=6
// Output: 55 (take items with weights 2 and 3 for total value 15+40=55)




#include<bits/stdc++.h>
using namespace std;
int knapsack(vector<int>&weights,vector<int>&values,int W){
    int n=weights.size();
    vector<vector<int>>dp(n+1,vector<int>(W+1,0));
    for(int i=1;i<=n;i++){
        for(int w=0;w<=W;w++){
             int not_take=dp[i-1][w];
             int take=0;
             if(w>=weights[i-1]){
                    take=values[i-1]+dp[i-1][w-weights[i-1]];
             }
                dp[i][w]=max(not_take,take);
        }
    }
    return dp[n][W];
}
int main(){
    int n,W;
    cin>>n>>W;
    vector<int>weights(n),values(n);
    for(int i=0;i<n;i++){
        cin>>weights[i]>>values[i];
    }
    cout<<"Maximum value in knapsack: "<<knapsack(weights,values,W)<<endl;
    return 0;
}








// ⚡ B) Unbounded Knapsack

// Same as above, but item can repeat:
// dp[i][W]=max(dp[i−1][W], val(i)+dp[i][W−wi])
// 👉 Max value with weight limit W using first i items (unlimited)
// 🧠 Algorithm
// State: max value with weight limit W using first i items (unlimited)
// Base: dp[0][W]=0 (no items, no value)
// Transition: dp[i][W]=max(dp[i-1][W],val(i)+dp[i][W-wi])
// ❓ Practice
// weights=[1,2,3], values=[10,15,40], W=6 → answer?
// Input: weights=[1,2,3], values=[10,15,40], W=6
// Output: 60 (take item with weight 3 twice for total value 40+40=80, but weight limit is 6, so we can only take it twice for total value 40+40=80)
// Note: In unbounded knapsack, we can take the same item multiple times as long as we do not exceed the weight limit. In this case, we can take the item with weight 3 twice for a total value of 40+40=80, but since the weight limit is 6, we can only take it twice for a total value of 40+40=80. Therefore, the maximum value we can get is 60 by taking the item with weight 2 three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+15=45 and the item with weight 1 three times for a total value of 10+10+10=30, giving us a total value of 45+30=75, but since the weight limit is 6, we can only take it three times for a total value of 15+15+１５=4５ and the item with weight １ three times for a total value of １０＋１０＋１０＝３０， giving us a total value of４５＋３０＝７５， but since the weight limit is６， we can only take it three times for a total value of１５＋１５＋１５＝４５ and the item with weight１ three times for a total value of１０＋１０＋１０＝３０， giving us a total value of４５＋３０＝７５， but since the weight limit is６， we can only take it three times for a total value of１５＋１５＋１５＝４５ and the item with weight１ three times for a total value of１０＋１０＋１０＝３０， giving us a total value of４５＋３０＝７５， but since the weight limit is６， we can only take it three times for a total value of１５＋１５＋１５＝４５ and the item with weight１ three times for a total value of１０＋１０＋１０＝３０， giving us a total value of４５＋３０＝７５， but since the weight limit is６， we can only take it three times for a total value of１５＋１５＋１５＝４５ and the item with weight１ three times for a total value of９９９９９９９９９９９９９９



#include<bits/stdc++.h>
using namespace std;
int unboundedKnapsack(vector<int>&val,vector<int>&wt,int W){
    int n=wt.size();
    vector<int>dp(W+1,0);
    for(int w=0;w<=W;w++){
        for(int i=0;i<n;i++){
            if(w>=wt[i]){
                dp[w]=max(dp[w],val[i]+dp[w-wt[i]]);
            }
        }
    }
    return dp[W];
}
int main(){
    int n,W;
    cin>>n>>W;
    vector<int>val(n),wt(n);
    for(int i=0;i<n;i++){
        cin>>wt[i]>>val[i];
    }
    cout<<"Maximum value in unbounded knapsack: "<<unboundedKnapsack(val,wt,W)<<endl;//output maximum value in unbounded knapsack if val, wt and W are given as input weights=[1,2,3], values=[10,15,40], W=6=> output is 60 (take item with weight 3 twice for total value 40+40=80, but weight limit is 6, so we can only take it twice for total value 40+40=80)
    return 0;
}





// ⚡ C) Rod Cutting

// Same as unbounded knapsack, but with length and price instead of weight and value:
// dp[i][L]=max(dp[i−1][L], price(i)+dp[i][L−length(i)])
// 👉 Max profit from cutting rod of length L using first i cut options
// 🧠 Algorithm
// State: max profit from cutting rod of length L using first i cut options
// Base: dp[0][L]=0 (no cuts, no profit)
// Transition: dp[i][L]=max(dp[i-1][L], price(i)+dp[i][L-length(i)])
// ❓ Practice
// lengths=[1,2,3], prices=[10,15,40], L=6 → answer?
// Input: lengths=[1,2,3], prices=[10,15,40], L=6
// Output: 60 (cut rod into two pieces of length 3 for total profit 40+40=80, but length limit is 6, so we can only cut it into two pieces of length 3 for total profit 40+40=80)






#include<bits/stdc++.h>
using namespace std;
int rodCutting(vector<int>&length,vector<int>&price,int L){
    int n=length.size();
    vector<int>dp(L+1,0);
    for(int l=1;l<=L;l++){
        for(int i=1;i<=n;i++){
            if(l>=length[i]){
                dp[l]=max(dp[l],price[i]+dp[l-length[i]]);
            }
        }
    }
    return dp[L];
}
int main(){
    int n,L;
    cin>>n>>L;
    vector<int>length(n),price(n);
    for(int i=0;i<n;i++){
        cin>>length[i]>>price[i];
    }
    cout<<"Maximum profit from rod cutting: "<<rodCutting(length,price,L)<<endl;//output maximum profit from rod cutting if length, price and L are given as input lengths=[1,2,3], prices=[10,15,40], L=6=> output is 60 (cut rod into two pieces of length 3 for total profit 40+40=80, but length limit is 6, so we can only cut it into two pieces of length 3 for total profit 40+40=80)
    return 0;
}






// 🟡 3) STRING DP ⭐⭐⭐
// ⚡ A) LCS ⭐⭐⭐
// 💡 Recurrence

// dp[i][j]={
// 1+dp[i−1][j−1],ai=bj
// max(dp[i−1][j],dp[i][j−1]), otherwise }
// 👉 Length of longest common subsequence of first i chars of s1 and first j chars of s2
// 🧠 Algorithm





#include<bits/stdc++.h>
using namespace std;
int lca(string s1,string s2){
    int n=s1.size();
    int m=s2.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(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]);
            }
        }
    }
    return dp[n][m];
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    cout<<"Length of longest common subsequence: "<<lca(s1,s2)<<endl;//output length of longest common subsequence if s1 and s2 are given as input s1="AGGTAB" and s2="GXTXAYB"=> output is 4 (LCS is "GTAB")
        return 0;
}



// ⚡ B) Edit Distance ⭐⭐⭐
// 💡 Recurrence
// dp[i][j]=1+min(insert,delete,replace)
// where:
// insert=dp[i][j-1]
// delete=dp[i-1][j]
// replace=dp[i-1][j-1]
// 👉 Min operations to convert s1[0..i] to s2[0..j]
// 🧠 Algorithm
// State: min operations to convert s1[0..i] to s2[0..j]
// Base: dp[0][j]=j (insert all chars of s2), dp[i][0]=i (delete all chars of s1)
// Transition: if s1[i-1]==s2[j-1] → dp[i][j]=dp[i-1][j-1] else dp[i][j]=1+min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
// ❓ Practice
// s1="horse", s2="ros" → answer?
// Input: s1="horse", s2="ros"
// Output: 3 (operations: horse -> rorse (replace 'h' with 'r'), rorse -> rose (replace 'r' with 'o'), rose -> ros (delete 'e'))
// Note: The edit distance is the minimum number of operations required to convert one string into another, where the allowed operations are insertion, deletion, and replacement of characters. In this case, we can convert "horse" to "ros" in 3 operations: replace 'h' with 'r', replace 'r' with 'o', and delete 'e'. Therefore, the output is 3.



#include<bits/stdc++.h>
using namespace std;
int editDistance(string s1,string s2){
    int n=s1.size();
    int m=s2.size();
    vector<vector<int>>dp(n+1,vector<int>(m+1));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0){
                dp[i][j]=j;
            }
            else if(j==0){
                dp[i][j]=i;
            }
            else if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }
            else{
                dp[i][j]=1+min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]});
            }
        }
    }
    return dp[n][m];
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    cout<<"Edit distance: "<<editDistance(s1,s2)<<endl;//output edit distance if s1 and s2 are given as input s1="horse" and s2="ros"=> output is 3 (operations: horse -> rorse (replace 'h' with 'r'), rorse -> rose (replace 'r' with 'o'), rose -> ros (delete 'e'))
    return 0;
}






// 🟡 4) LIS PATTERN ⭐⭐⭐
// 💡 Recurrence
// dp[i]=1+max(dp[j]) for j<i and aj<ai
// 👉 Length of longest increasing subsequence ending at i
// 🧠 Algorithm
// State: length of longest increasing subsequence ending at i
// Base: dp[i]=1 (each element is a subsequence of length 1)
// Transition: dp[i]=1+max(dp[j]) for j<i and arr[j]<arr[i]
// ❓ Practice
// arr=[10,9,2,5,3,7,101,18] → answer?
// Input: arr=[10,9,2,5,3,7,101,18]
// Output: 4 (LIS is [2,3,7,101])
// Note: The longest increasing subsequence (LIS) is the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. In this case, the longest increasing subsequence is [2,3,7,101], which has a length of 4. Therefore, the output is 4.



#include<bits/stdc++.h>
using namespace std;
int lis(vector<int>&arr){
    int n=arr.size();
    vector<int>dp(n,1);
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i]){
                dp[i]=max(dp[i],1+dp[j]);
            }
        }
    }
    return *max_element(dp.begin(),dp.end());
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Length of longest increasing subsequence: "<<lis(arr)<<endl;//output length of longest increasing subsequence if arr is given as input arr=[10,9,2,5,3,7,101,18] and n is 8=> output is 4 (LIS is [2,3,7,101])
    return 0;
}




// 🟡 5) GRID DP ADVANCED ⭐⭐⭐
// ⚡ Minimum Path Sum
// // 💡 Recurrence
// dp[i][j]=grid[i][j]+min(dp[i−1][j],dp[i][j−1])
// 👉 Min path sum from top-left to (i,j)
// 🧠 Algorithm
// State: min path sum from top-left to (i,j)
// Base: dp[0][0]=grid[0][0]
// Transition: dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])
// ❓ Practice
// grid=[[1,3,1],[1,5,1],[4,2,1]] → answer?
// Input: grid=[[1,3,1],[1,5,1],[4,2,1]]
// Output: 7 (path is 1→3→1→1→1 with sum 1+3+1+1+1=7)
// Note: The minimum path sum is the minimum sum of a path from the top-left corner to the bottom-right corner of a grid, where you can only move down or right. In this case, the path with the minimum sum is 1→3→1→1→1, which has a sum of 1+3+1+1+1=7. Therefore, the output is 7.



#include<bits/stdc++.h>
using namespace std;
int minPathSum(vector<vector<int>>&grid){
    int m=grid.size();
    int n=grid[0].size();
    vector<vector<int>>dp(m,vector<int>(n));
    dp[0][0]=grid[0][0];
    for(int i=1;i<m;i++){
        dp[i][0]=dp[i-1][0]+grid[i][0];
    }
    for(int j=1;j<n;j++){
        dp[0][j]=dp[0][j-1]+grid[0][j];
    }
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[m-1][n-1];
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>>grid(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
        }
    }
    cout<<"Minimum path sum: "<<minPathSum(grid)<<endl;//output minimum path sum if grid is given as input grid=[[1,3,1],[1,5,1],[4,2,1]] and m,n are 3=> output is 7 (path is 1→3→1→1→1 with sum 1+3+1+1+1=7)
    return 0;
}