Given a rope with positive integer-lengthn, how to cut the rope intom_integer-length parts with length_p[0],p[1], ...,p[m-1], in order to get the maximal product ofp[0]*p[1]* ... *p[m-1]?mis determined by youand must be greater than 0(at least one cut must be made). Return the max product you can have.

Assumptions

• n > = 2

Examples

• n = 12, the max product is 3 * 3 * 3 * 3 = 81(cut the rope into 4 pieces with length of each is 3).

Solution: size从1到N计算，dp[i] = Math.max(Math.max(dp[j], j) * Math.max(dp[i - j], i - j))，分为j段和i - j段，有切与不切2种情况

  public int maxProduct(int length) {
    int[] dp = new int[length + 1];
    dp[1] = 1;
    for (int i = 2; i <= length; i++) {
    //因为对称，所以枚举到i / 2即可
      for (int j = 1; j <= i / 2; j++) {
                                 //切  不切
        dp[i] = Math.max(Math.max(dp[j], j) * Math.max(dp[i - j], i - j), dp[i]);
      }
    }
    return dp[length];
  }