0 1 Knapsack - DP on Subsequence

Problem Link:

https://www.codingninjas.com/studio/problems/0-1-knapsack_920542?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

My approach:

Code:

Memoization:

// TIME COMPLEXITY : O(N^2)
// SPACE COMPLEXITY: O(N*W) + Auxiliary Stack space

int helper(vector<int> &weight, vector<int> &value, int i, int maxWeight, vector<vector<int>> &dp){

    if(i==0){
        if(weight[0]<=maxWeight){
            return value[0];
        }
        return 0;
    }

    if(dp[i][maxWeight]!=-1){
        return dp[i][maxWeight];
    }

    int notPick = helper(weight,value,i-1,maxWeight,dp);
    int pick = INT_MIN;
    if(weight[i]<=maxWeight){
        pick = value[i]+helper(weight,value,i-1,maxWeight-weight[i],dp);
    }

    dp[i][maxWeight] = max(pick,notPick);
    return max(pick, notPick);
}

int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) 
{
    // Write your code here
    vector<vector<int>> dp(n, vector<int>(maxWeight+1,-1));
    return helper(weight,value,n-1,maxWeight,dp);
}

Tabulation:

// TIME COMPLEXITY : O(N^2)
// SPACE COMPLEXITY: O(N*W) + Auxiliary Stack space
int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) 
{
    // Write your code here
    vector<vector<int>> dp(n, vector<int>(maxWeight+1,0));

    for(int i=weight[0];i<=maxWeight;i++){
        dp[0][i] = value[0];
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<=maxWeight;j++){
            int notPick = dp[i-1][j];
            int pick = INT_MIN;
            if(weight[i]<=j){
                pick = value[i]+dp[i-1][j-weight[i]];
            }

            dp[i][j] = max(pick, notPick);
        }
    }

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