杆子分割"/>
700. 杆子分割
700. 杆子分割
给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值.样例
样例1 输入: [1, 5, 8, 9, 10, 17, 17, 20] 8 输出:22 解释: 长度 | 1 2 3 4 5 6 7 8 -------------------------------------------- 价格 | 1 5 8 9 10 17 17 20 切成长度为 2 和 6 的两段。 样例2 输入: [3, 5, 8, 9, 10, 17, 17, 20] 8 输出:24 解释: 长度 | 1 2 3 4 5 6 7 8 -------------------------------------------- 价格 | 3 5 8 9 10 17 17 20 切成长度为 1 的 8 段。 public class Solution { /** * @param prices: the prices * @param n: the length of rod * @return: the max value */ public int cutting(int[] prices, int n) { // Write your code here int[] ret=new int[n+1]; for (int i = 1; i <= n; i++) { ret[i]=prices[i-1]; for (int j = 1; j < i; j++) { ret[i]=Math.max(ret[i],ret[i-j]+ret[j]); } // System.out.println(ret[i]); } return ret[n]; } }更多推荐
700. 杆子分割
发布评论