1. class Solution {
  2.     // similar to knapsack problem : consider length of rod array as weight array
  3.  
  4.     /** Recursion */
  5.     public int cutRod(int[] price) {
  6.         int n = price.length;
  7.  
  8.         // create a length array similar to weight array
  9.         // Lengths of corresponding rod pieces.
  10.         int[] length = new int[n];
  11.         for(int i=0; i<n; i++)
  12.         {
  13.             length[i] = i+1;
  14.         }
  15.  
  16.         int MaxLength = n;
  17.         return findMaxCost(MaxLength, price, length, n);
  18.     }
  19.  
  20.     public int findMaxCost(int maxLength, int[] price, int[] length, int n)
  21.     {
  22.         if(n == 0 || maxLength == 0)
  23.             return 0;
  24.  
  25.         if(length[n-1] <= maxLength)
  26.         {
  27.             int cut = price[n-1] + findMaxCost(maxLength - length[n-1], price, length, n);
  28.             int notCut = findMaxCost(maxLength, price, length, n-1);
  29.             return Math.max(cut, notCut);
  30.         }
  31.         return findMaxCost(maxLength, price, length, n-1);
  32.     }
  33.  
  34.     /** Top-down approach */
  35.     public int cutRod(int[] price) {
  36.         int n = price.length;
  37.  
  38.         // create a length array similar to weight array
  39.         // Lengths of corresponding rod pieces.
  40.         int[] length = new int[n];
  41.         for(int i=0; i<n; i++)
  42.         {
  43.             length[i] = i+1;
  44.         }
  45.  
  46.         int MaxLength = n;
  47.  
  48.         int[][] t = new int[n+1][MaxLength+1];
  49.  
  50.         // Base case: no rod or no length is present
  51.         for(int i=0; i<n+1; i++)
  52.         {
  53.             for(int j=0; j<MaxLength+1; j++)
  54.             {
  55.                 if(i == 0 || j == 0)
  56.                     t[i][j] = 0;
  57.             }
  58.         }
  59.  
  60.         for(int i=1; i<n+1; i++)
  61.         {
  62.             for(int j=1; j<MaxLength+1; j++)
  63.             {
  64.                 if(length[i-1] <= j)
  65.                 {
  66.                     int pick = price[i-1] + t[i][j - length[i-1]];
  67.                     int notPick = t[i-1][j];
  68.                     t[i][j] = Math.max(pick, notPick);
  69.                 }
  70.                 else
  71.                     t[i][j] = t[i-1][j];
  72.             }
  73.         }
  74.         return t[n][MaxLength];
  75.     }
  76. }