Non-recursive approach to the Rod-Cutting I've given the Rod-Cutting Problem a go with a non-recursive approach that use a cache instead, with a bottom up approach. For anyone who hasn't heard about the Rod-Cutting problem, it's defined as follows:


  Serling Enterprises buys long steel rods and cuts them into shorter
  rods, which it then sells. Each cut is free. The management of Serling
  Enterprises wants to know the best way to cut up the rods. We assume
  that we know, for i = 1, 2, ..., the price pi in dollars that Serling
  Enterprises charges for a rod of length i inches. Rod lengths are
  always an integral number of inches. Given a rod of length n inches
  and a table of prices pi for i = 1, 2, ..., n determine the maximum
  revenue obtainable by cutting up the rod and selling the pieces. Note
  that if the price pn for a rod of length n is large enough, an optimal
  solution may require no cutting at all.


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

public static void main(String[] args) {

    // Best Price Check #1
    for (int i = 1; i &lt; 9; i++) {
        System.out.println(i + " =&gt; " + bestPrice(i));
    }

}

public static int bestPrice(int n) {

    // This works like a cache
    int[] maxPrices = new int[n+1];

    // The trick here is to work from the bottom up
    for (int i = 1; i &lt;= n; i++) {

        int max_price = prices[i-1]; // Without cuts

        // Try all cuts length with combo from existing cache
        for (int j = 1; j &lt;  i; j++) {
            max_price = Math.max(max_price, maxPrices[i-j] + prices[j-1]);
        }
        maxPrices[i] = max_price;
    }

    return maxPrices[n];

}
The algorithm itself seems to have no problems. It's Dynamic programming and I wouldn't call the int[] maxPrices cache. Cache is something used for speed only, you can clear it anytime and everything must still work.

For example, a straightforward recursive solution to this problem would be damn slow because of recomputing values again and again. It could be made much faster using a cache.

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


This way you lose any chance to make it more flexible. You class has two functions: It's both the computing core and the main class. That's fine for a small class, but even then you should separate the tasks. 

For the main class, something like

private static final int[] PRICES = new int[] {1, 5, 8, 9, 10, 17, 17, 20};


Here, static final is the way how constants get declared in Java. PRICES is uppercase as a constant should be. And there's a space after each comma.

For the core, pass it explicitly to the bestPrice method. In more complicated cases, you could use an instance field for this.



max_price should be maxPrice in Java. No underscores except in constants.