Q24 Rod Cutting | Practice | GeeksforGeeks

    class Solution{
    public int cutRod(int price[], int n) {
        
        
        // return solve(price , n-1 , n , new Integer[n][n+1]);
        
        //tabulization -> n*n | sc- n*n
        int dp[][] = new int[n][n+1];
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ;j < n+1 ; j++){
                if( i== 0)
                dp[i][j] = j/(i+1)*price[i];
                
                else{
                    int rodlength =i+1;
                    int notake = 0 + dp[i-1][j];
        
                    int take = (int)-1e9;
                    
                    if(j-rodlength >= 0)
                    take = price[i] + dp[i][j-rodlength];
                    
                    dp[i][j]= Math.max(take , notake);
                }
            }
        }
        return dp[n-1][n];
    }
    
    //treat this as same unbounded knapsack , we can take rod length 1 infinite times
    //till it makes length n , so no index change recursion call
    
    //Recursion-> exponential(can't determine no. of options) | 
    //Memoization -> n*n Sc-> n*n + amt(stack height)
    public int solve(int price[] , int i , int n , Integer[][]dp){
        
        if(i == 0){
            return (n/(i+1))*price[i];
        }
        if(dp[i][n] != null)
        return dp[i][n];
        
        int rodlength =i+1;
        int notake = 0 + solve (price , i-1 , n ,dp);
        
        int take = (int)-1e9;
        
        if(n-rodlength >= 0)
        take = price[i] + solve(price , i , n-rodlength,dp );
        
        return dp[i][n]= Math.max(take , notake);
    }
}