0%

剪绳子

发表于 更新于

给你一根长度为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。

找规律，2、3组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int cutRope(int number) {
        if (number < 1)
        {
            return 0;
        }
        else if (number == 2)
        {
            return 1;
        }
        else if (number == 3)
        {
            return 2;
        }
        else
        {
            int quotient = number / 3;
            int remainder = number % 3;
            switch (remainder)
            {
            case 0:
                return pow(3, quotient);
            case 1:
                return pow(3, quotient - 1) * 4;
            case 2:
                return pow(3, quotient) * 2;
            }
        }
    }
};