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); } }