剪绳子

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，$2≤n≤58$ 并且 $m≥2$ ）。

每段的绳子的长度记为$ k[1]、k[2]、……、k[m] $。

$k[1]*k[2]…k[m]*k[1]*k[2]…k[m] $可能的最大乘积是多少？

例如当绳子的长度是 88 时，我们把它剪成长度分别为 2、3、32、3、3 的三段，此时得到最大的乘积 1818。

样例

1
2
3

输入：8

输出：18

数学结论

假设 $N = n_1 + n_2 + … + n_k$ ，并且 $n_1n_2n_3*…*n_k$

是最大乘积

思路:

  1. $n=2，max=1*1 = 1$
  2. $n=3, max=1*2=2;$
  3. $n =4, max = 112*2 = 4,分成2个2$
  4. $n=5,分成一个2，一个3， max = 2*3=6$
  5. $n=6,分为2个3，max = 3*3 = 8$
  6. 以此类推，尽量分成多个3，其余为2，这样构成的数最大

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxProductAfterCutting(int length) {
        if(length<=1) return 1;
        else if(length == 2) return 1;
        else if(length <=3) return 2;
        int res = 1;
        if(length % 3 ==2) {
            //余数是2
            res *= 2,length -=2;
        }else if(length % 3 ==1) {
            res *= 4,length -= 4;
        
        }
        while(length) {
            res *= 3,length -= 3;
        }
        return res;
    } 
};