Barclays | SDE | Coding OA Questions and Solutions | Set - 8 | 2022 | DP

Question

Answer 1

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
ll dp[200005][5];
int main() {
    
    ll n ; 
    cin>>n ;
    ll v ; 
    cin>>v ; 
    
    ll easy[n+1] = {0};
    ll hard[n+1] = {0};
    
    
    ll i = 1 ; 
    while(i<=n){
        
        cin>>easy[i];
        cin>>hard[i];
        i++;
    }
    
    dp[1][1] = easy[1] ; //dp[][1]====easy 
    dp[1][2] = hard[1] ; //dp[][2]=====hrd
    dp[1][3] = 0 ; 
    
    i = 2 ; 
    while(i<=n){
        
        dp[i][1] = easy[i] + max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]));
        dp[i][2] = hard[i] + dp[i-1][3] ; //did nothing on i-1 dy
        dp[i][3] = 0 + max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]));
        
        
        i++;
    }
    
    cout<<max(dp[n][1],max(dp[n][2],dp[n][3]));
    
    
    return 0 ; 
}

Answer 2

Similar to Kumar SIr approach:

 

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n;
    cin>>n;
    vector<vector<int>>vec(n,vector<int>(2));
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            cin>>vec[i][j];
        }
    }
    vector<vector<int>>dp(n,vector<int>(3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(i==0){
                if(j==0)
                dp[i][j]=0;
                else if(j==1)
                dp[i][j]=vec[i][0];
                else
                dp[i][j]=vec[i][1];
            }
            else if(j==2)
            dp[i][j]=dp[i-1][0]+vec[i][1];
            else if(j==0)
            dp[i][j]=max(dp[i-1][1],dp[i-1][2]);
            else
            dp[i][j]=max(dp[i-1][1],dp[i-1][2])+vec[i][0];
        }
    }
    cout<<max(dp[n-1][2],dp[n-1][1])<<endl;
    return 0;
}

Answer 3

This is my approch of above problem

memoization technique

 

0--not preform any task

1--perform easy task

2--preform hard task

     public static void main(String[] args) {
        System.out.print("hi");
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int type=sc.nextInt();
        int[]ep=new int[n];
        int[]dp= new int[n];
        for(int i=0;i<n;i++) {
            ep[i]=sc.nextInt();
            dp[i]=sc.nextInt();
        }
        
        int[][]dpp=new int[ep.length][3];
        for(int[]d:dpp) {
            Arrays.fill(d, -1);
        }
        System.out.print(check(ep,dp,0,0,dpp));
        
         
    }
    public static int  check(int[]easy,int[]diff,int prev,int i,int[][]dpp) {
        if(i==easy.length) {
            return 0;
        }
        if(dpp[i][prev]!=-1)return dpp[i][prev];
        int notpick=check(easy,diff,0,i+1,dpp);
        
        int easypick=easy[i]+check(easy,diff,1,i+1,dpp);
        int diffpick=Integer.MIN_VALUE;
        if(prev==0) {
            diffpick=diff[i]+check(easy,diff,2,i+1,dpp);
        }
        return  dpp[i][prev]=Math.max(notpick, Math.max(easypick, diffpick));
        
    }

Answer 4

Porblem Description. : 

Comments

sir can we take the hard task amount and sort them and add the max and remove before number and add the number before the number we removed now and soon and add it to the variable

---

Thats greedy strategy it will not pass for all cases

---

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n;
    cin>>n;
    vector<vector<int>>vec(n,vector<int>(2));
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            cin>>vec[i][j];
        }
    }
    vector<vector<int>>dp(n,vector<int>(3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(i==0){
                if(j==0)
                dp[i][j]=0;
                else if(j==1)
                dp[i][j]=vec[i][0];
                else
                dp[i][j]=vec[i][1];
            }
            else if(j==2)
            dp[i][j]=dp[i-1][0]+vec[i][1];
            else if(j==0)
            dp[i][j]=max(dp[i-1][1],dp[i-1][2]);
            else
            dp[i][j]=max(dp[i-1][1],dp[i-1][2])+vec[i][0];
        }
    }
    cout<<max(dp[n-1][2],dp[n-1][1])<<endl;
    return 0;
}