剪绳子

---

题目描述

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

输入描述：

输入一个数n，意义见题面。(2 <= n <= 60)

输出描述：

输出答案

示例1

输入：

8

输出：

18

解题思路

参考以下示例：

n		n%3	n/3
4	2*2	1	1
5	2*3	2	1
6	3*3	0	2
7	2*2*3	1	2
8	2*3*3	2	2
9	3*3*3	0	3
10	2*2*3*3	1	3
11	2*3*3*3	2	3
12	3*3*3*3	0	4
13	2*2*3*3*3	1	4
14	2*3*3*3*3	2	4

可以发现以下规律：

• 所有的拆分都拆分为2或3;
• 拆分的结果中，2的个数与 n%3相关， 且n%3的结果总是 0, 1, 2循环，可作为判断条件；

由于规定至少拆为两端，所以当 n = 2时，只能拆分为 1*1;当 n = 3时，只能拆分为 1*2;

具体操作看以下代码

代码

class Solution
{
public:
    int cutRope (int number)
    {
        if (number == 2)
            return 1;
        if (number == 3)
            return 2;
        
        int x = number % 3;
        int y = number / 3;
        if (x == 0)
            return pow(3, y);
        else if (x == 1)
            return 2 * 2 * pow(3, y - 1);
        else
            return 2 * pow(3, y);
    }
};

参考博文链接：https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?f=discussion