// This algorithm solves this problem:

// + "Given a rod of length n and an array that contains prices of all pieces of size

// smaller than n. Determine the maximum value obtainable by cutting up the rod and selling

// the pieces."

public class RodCutting

{

// This solution is correct but highly inefficient. Recursive calls aren't memoized

// so the poor code has to solve the same subproblem every time there's a single

// overlapping solution.

public int byRecursionApproach(int[] values, int length) {

if (length <= 0)

return 0;

int tmpMax = -1;

for (int i = 0; i < length; i++) {

tmpMax = Math.max(tmpMax, values[i] + byRecursionApproach(values, length - i - 1));

}

return tmpMax;

}

// With this approach we eliminate the need for recursive calls by solving the subproblems

// from the ground-up, utilizing the fact that all previous subproblems to a given problem

// are already solved. It follows the same basic principle from above, but adds memoization

// and excludes recursive calls.

public int byDynamicApproach(int[] values, int length) {

int[] subSolutions = new int[length + 1];

for (int i = 1; i <= length; i++) {

int tmpMax = -1;

for (int j = 0; j < i; j++)

tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);

subSolutions[i] = tmpMax;

}

return subSolutions[length];

}

public static void main(String args[])

{

int arr[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20};

int size = arr.length;

RodCutting rodCutting = new RodCutting();

System.out.println("Maximum obtainable value by recursion: " + rodCutting.byRecursionApproach(arr, size));

System.out.println("Maximum obtainable value by dynamic programming: " + rodCutting.byDynamicApproach(arr, size));

}

}