Rod cutting problem - DP on Subsequences

Problem Link:

https://www.codingninjas.com/studio/problems/rod-cutting-problem_800284?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

My approach:

Code:

Memoization:

int helper(vector<int> price, int i, int size, vector<vector<int>> &dp){

    if(i==0){
        if(size>=i+1){
            return price[0]*size;
        }
        return 0;
    }

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

    int notTake = helper(price, i-1, size,dp);
    int take = 0;
    if(i+1<=size){
        take = price[i]+helper(price,i,size-i-1,dp);
    }

    dp[i][size] = max(notTake,take);
    return max(notTake, take);
}

int cutRod(vector<int> &price, int n)
{
    // Write your code here.

    vector<vector<int>> dp(n, vector<int>(n+1, -1));
    return helper(price,n-1,n,dp);
}

Tabulation:

int cutRod(vector<int> &price, int n)
{
    // Write your code here.

    vector<vector<int>> dp(n, vector<int>(n+1, 0));

    for(int i=1;i<=n;i++){
        dp[0][i] = price[0]*i;
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            int notTake = dp[i-1][j];
            int take = 0;
            if(j>=i+1){
                take = price[i] + dp[i][j-i-1];
            }

            dp[i][j] = max(take, notTake);
        }
    }

    return dp[n-1][n];

}