Concepts to Remember

23/3/26

  1)If in any problem we are given to try all combinations :

    the go to solution is recursion/backtracking (like-  target-sum problem,0/1 knapsnack,        0/1 unbounded knapsnack),

    we optimize the recursion time complecity then by applying dynamic programming            aprroach

    EXAMPLE WITH A PRBLEM:

  

     

   suppose along the exmaple the rid is size 8,

   SEE IN the Question we can either cut the rod into the n(8)size and take the price,

    we can also do cut into n-1(7) size and 1size and can take both profits , or can cut 1sizes     of n(8) times gives us n pices we can also do that , can also do 4,3,1 or 4,4 or 4,2,1,1 

by for loop we cant decide the size of poitners, we use recursion here and dp 

and solutin becomes:

// User function Template for C++

class Solution {

  public:

    int MaxPrice(int cs,int rsize,vector<int>&price,vector<vector<int>>&dp){

        if(rsize==0)return 0;

        if(cs==0)return 0;

        if(dp[cs][rsize]!=-1)return dp[cs][rsize];

        int nt=MaxPrice(cs-1,rsize,price,dp);

        int take=0;

        if(cs<=rsize){

            take=price[cs]+MaxPrice(cs,rsize-cs,price,dp);

        }

        return dp[cs][rsize]=max(nt,take);

    }

    int cutRod(vector<int> &price) {

        // code here

        

        

        int n=price.size();

        vector<int>pr(n+1);

        for(int i=1;i<n+1;i++){

            pr[i]=price[i-1];

        }

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

        return MaxPrice(n,n,pr,dp);

    }

};