题解 | #剪绳子#

先说结论：尽量分出多个3，其余为2，这样构成的数最大

下面证明：
有,可以划分为
先假设存在 , 有 ， 即, 就可以得到 , 这是必然成立的，因为我们已经假设过 了，也就是说 如果最终解 中包含 大于等于5的数字，则一定可以拆分出 3，那么5就一定不是最优解了，下面最优解就落在 2 3 4 中了

下面假设 , 那么 ，所以可以使用 来替代，所以最优解就一定在 2 和 3 之间了

而且有 , 即如果有三个以上的2，替换成3的乘积就一定更大，所以 2 的数量一定不会超过两个

选用尽量多的3，直到剩下2或者4时，用2。如果N模3余1就是两个2，如果模3余2就是一个2，如果模3余0就没有2

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        //尽量分出多个3，其余为2，这样构成的数最大
        if(n<=3)
        {
            return 1*(n-1);
        }

        int res=1;
        if(n%3==1)
        {
            res*=4;
            n-=4;
        }
        if(n%3==2)
        {
            res*=2;
            n-=2;
        }

        while(n)
        {
            res*=3;
            n-=3;
        }

        return res;
    }
};