一道经典的数学问题:
通过观察可以发现,当$n<5$时,无论怎么剪切,乘积永远小于等于$n$;当$n>=5$时,可以将$n$拆分成
$3 * (n - 3) = 3n - 9 > n$。所以我们应该尽可能地多剪长度为3的绳子段。
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length <= 3) return 1 * (length - 1); //长度小于等于3的情况
int res = 1;
//下面两行判断长度不为3的整数倍的情况
if (length % 3 == 1) res = 4, length -= 4; //余数为1且总长度大于3,则可以剪切成2*2即4,不能剪切成1*3
else if (length % 3 == 2) res = 2, length -= 2; //余数为2时表示多余一个2
while (length) length -= 3, res *= 3; //剩下的就是3的整数倍,全部剪切成3
return res;
}
};