14. Rod Cutting Problem

GFG problem  practice link -->> https://practice.geeksforgeeks.org/problems/rod-cutting0840/1


//{ Driver Code Starts
// Initial Template for C++

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


// } Driver Code Ends
// User function Template for C++

class Solution{
  public:
  
  int solve(int price[],int n,int s,int l[],vector<vector<int>> &dp){
      
      if(n==0 || s==0){
          return 0;
      }
      
      if(dp[n][s]!=-1){
          return dp[n][s];
      }
      
      if(l[n-1]<=s){
          return dp[n][s]=max(price[n-1]+ solve(price,n,s-l[n-1],l,dp) , solve(price,n-1,s,l,dp) );
      }
      else{
          return dp[n][s]=solve(price,n-1,s,l,dp);
      }
      
      
  }
  
    int cutRod(int price[], int n) {
        //code here
        
        int l[n];
        for(int i=0;i<n;i++){
            l[i]=i+1;
        }
        
        vector<vector<int>> dp (n+1,vector<int> (n+1,-1));
        
        return solve(price,n,n,l,dp);
        
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++) 
            cin >> a[i];
            
        Solution ob;

        cout << ob.cutRod(a, n) << endl;
    }
    return 0;
}
// } Driver Code Ends