存储中间计算结果的动态规划算法
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;}}}?
吐血归来，小帖一篇代码，恢复中。。。