中間計算結果を格納する動的計画アルゴリズム

public class RodCutting {

	public static void main(String[] args) {
		int n = 5;
		int[] prices = new int[]{1, 4, 5, 6, 8};
		long start = System.currentTimeMillis();
		System.out.println(cut(n, prices));
		long end = System.currentTimeMillis() - start;
		System.out.println(end);
	}
	
	private static Map<Integer, Integer> intermidum = new HashMap<Integer, Integer>();
	private static int cut(int n, int[] prices) {
		if(n == 1) {
			//System.out.println("One one inch, no cut");
			return prices[0];
		} else if (intermidum.containsKey(n)) {
			return intermidum.get(n);
		} else {
			int price = prices[n - 1];
			int index = 0;
			for(int i = 1; i < n; i++) {
				int tmp = prices[i - 1] + cut(n - i, prices);
				if(tmp > price) {
					price = tmp;
					index = i;
				}
			}
			
			if(price == prices[n - 1]) {
				//System.out.println("No cut for the "+ n +" inches.");
			} else {
				System.out.println("Cut to " + index  + " and " + (n - index) + " inches.");
			}
			
			intermidum.put(n, price);
			
			
			return price;
			
		}
	}
}