RodCutting.java

/*
    Problem: Given a rod's length and prices of each length,
             find a maximum profit.

 */
public class RodCutting {
    // complexity: time O(2^(n-1)), space O(n)
    static int cutRodRecur(int[] price, int l) {
        // base case
        if (l <= 0) {
            return 0;
        }
        int max = -1;
        for (int i=0; i<l; i++) {
            max = Math.max(max, price[i] + cutRodRecur(price, l - (i + 1)));
        }
        return max;
    }
  
    // complexity: time O(n^2), space O(n)
    static int cutRod(int[] price, int L) {
        int[] memo = new int[L + 1];
        for (int i=1; i<=L; i++) {
            int max_value = -1;
            for (int j=0; j<i; j++) {
                max_value = Math.max(max_value, price[j] + memo[i - (j + 1)]);
            }
            memo[i] = max_value;
        }
        return memo[L];
    }

    public static void main(String[] args) {
        System.out.println(cutRodRecur(new int[]{1, 5, 8, 9, 10, 17, 17, 20}, 8));
        System.out.println(cutRod(new int[]{1, 5, 8, 9, 10, 17, 17, 20}, 8));
        System.out.println(cutRodRecur(new int[]{2, 3, 7, 8, 9}, 5));
        System.out.println(cutRod(new int[]{2, 3, 7, 8, 9}, 5));
    }
}

/*
References:
http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/
http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/
 */