剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

思路：

对于一个数n。

1. 如果n超过了5，可以进行如下的操作。
   n = 3 + (n - 3) -> 乘积 = 3 * (n - 3) = 3n - 9 > n。
   所以如果超过了5则拆分成更多的3可以大于原始的数
2. n 不会别拆成若干个1,1练乘的结果是1.
3. 所以答案锁定在拆分成 2 3 4 ,如果是4，则拆分成 2 * 2 = 4 == 4，所以可以认为拆分成了2。
4. 答案锁定在 2 3 ，对于5 (> 4) 来说，拆分成更多的3是更好的选择，比如 5 = 2 + 3 -> 2 * 3 = 6 > 5 = 2 + 2 + 1 -> 2 * 2 * 1.

综上，如果数字n > 4，则拆分成更多的3，如果小于4，则特殊判断一下。

代码：

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;
        int res = 1;
        while(n > 4) res *= 3,n -= 3;
        if(n) res *= n;
        return res;
    }
};