700

700

2017.10.24

状态转移方程为： value[i] = Math.max(value[i], value[j] + value[i-j]);

public class Solution {/** @param : the prices* @param : the length of rod* @return: the max value*/public int cutting(int[] prices, int n) {// Write your code hereif(n <= 0){return 0;}int value[] = new int[n+1];value[1] = prices[0];if(n == 1){return value[1];}for(int i = 2; i <= n; i++){value[i] = prices[i-1];for(int j = 1; j <= i/2; j++){value[i] = Math.max(value[i], value[j] + value[i-j]);}}return value[n];	}
}