Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- 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 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];
- }
- else
- t[i][j] = t[i-1][j];
- }
- }
- return t[n][MaxLength];
- }
- }
RAW Paste Data
Copied
