剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

 1 public class Solution {
 2     public int cutRope(int target) {
 3         if (target == 2) return 1;
 4         if (target == 3) return 2;
 5         if (target == 4) return 4;
 6         
 7         int []f = new int[target / 2 + 1];
 8         int ans = 1;
 9         for (int i = 2; i <= target / 2; ++i) {
10             int temp = target % i;
11             int c = target / i;
12             int sum = 1;
13             for (int j = 0; j < i; ++j) {
14                 if (j < temp) {
15                     sum = sum * (c + 1);
16                 } else {
17                     sum = sum * c;
18                 }
19             }
20             ans = Math.max(ans, sum);
21             
22         }
23         
24         return ans;
25     }
26 }