700. 杆子分割

杆子分割"/>

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];     } }