剑指 Offer 14- I. 剪绳子

题目链接： 剑指 Offer 14- I. 剪绳子

方法：数论

解题思路

将 \(n\) 分为 \(m\) 个数的和，使得这 \(m\) 个数的乘积最大，那么应该将 \(m\) 个数分为 \(2\) 和 \(3\) 的组合, 尽可能为 \(3\)。

代码

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;
        }

        return res * n;
    }
};