로드 절단 문제(무제한 배낭과 유사)

import java.util.*;
public class Solution {
    public static int cutRod(int price[], int n) {
        //intuition 
        /*
        Since, we have to maximize the profit by cutting the rod in different length
        let say length of the rod is 5
        and the prices for cutting in different lengths are : 2 5 7 8 10
        so we will have to keep on picking lengths(we could take a length any 
        no of times to maximize the profit of selling the rod) until there is no more length is left to be picked from;
        This is exactly similar to unbounded knapsack problem:
        */
        int dp[][] = new int[n][n+1];
        for(int row []: dp) Arrays.fill(row,-1);
        return maxProfit(n-1,price,n,dp);
    }
    public static int maxProfit(int index, int[] price,int target,int dp[][]){
        if(index==0){
            return (target/(index+1))*price[index];
        }
        if(dp[index][target]!=-1) return dp[index][target];
        int take = 0;
        if(target>=index+1){
            take  = price[index]+maxProfit(index,price,target-(index+1),dp);
        }
        int dontTake = 0 + maxProfit(index-1,price,target,dp);
        return dp[index][target] = Integer.max(take,dontTake);
    }
}