class Solution {
    // similar to knapsack problem : consider length of rod array as weight array
    
    /** Recursion */
    public int cutRod(int[] price) {
        int n = price.length;
        
        // create a length array similar to weight array
        // Lengths of corresponding rod pieces.
        int[] length = new int[n];
        for(int i=0; i<n; i++)
        {
            length[i] = i+1;
        }
        
        int MaxLength = n;
        return findMaxCost(MaxLength, price, length, n);
    }
    
    public int findMaxCost(int maxLength, int[] price, int[] length, int n)
    {
        if(n == 0 || maxLength == 0)
            return 0;
        
        if(length[n-1] <= maxLength)
        {
            int cut = price[n-1] + findMaxCost(maxLength - length[n-1], price, length, n);
            int notCut = findMaxCost(maxLength, price, length, n-1);
            return Math.max(cut, notCut);
        }
        return findMaxCost(maxLength, price, length, n-1);
    }
    
    /** Top-down approach */
    public int cutRod(int[] price) {
        int n = price.length;
        
        // create a length array similar to weight array
        // Lengths of corresponding rod pieces.
        int[] length = new int[n];
        for(int i=0; i<n; i++)
        {
            length[i] = i+1;
        }
        
        int MaxLength = n;
        
        int[][] t = new int[n+1][MaxLength+1];
        
        // Base case: no rod or no length is present
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<MaxLength+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }
        
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<MaxLength+1; j++)
            {
                if(length[i-1] <= j)
                {
                    int pick = price[i-1] + t[i][j - length[i-1]];
                    int notPick = t[i-1][j];
                    t[i][j] = Math.max(pick, notPick);
                }
                else
                    t[i][j] = t[i-1][j];
            }
        }
        return t[n][MaxLength];
    }
}