题目描述
给你一根长度为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。
求解
很多朋友都通过观察发现了最大解其实就是尽可能的多分长度为3的段,下面系统证明:
假设得到最大乘积时,其中一段长度为k,下面通过反证法证明:
k!=1且k不能再继续拆分成2和3的和
证明1:
先证明k!=1,假设k=1,则取其临近的一段,假设长度为l,则存在这样一种剪法:k+l为一段,其余不变,比当前k和l被剪开的乘积要大(因为l<(1+l)),因此k!=1
再证明k不能再继续拆分,假设k能够继续拆分为 k=k1+k2,其中k1>=2,k2>=2,假设其余各段乘积为M,则
图片说明
既将k拆分能得到一种乘积更大的剪法
又因为当k>=4时,一定可以拆分成2和3的组合,因此最终:k[i]一定为2或者3,其中0<=i<=m
下面再证明为什么当k[i]中3尽可能多时,能够得到最大解
证明2:
假设k[0]-k[m]中有x个2,y个3,则有
图片说明
其乘积为:
图片说明
这是一个随y递增的函数,因此要保证最后的乘积最大,则y需要尽可能大,既3的个数要尽可能多
证毕,附代码如下:

class Solution {
public:
    int cutRope(int number) {
        if (number <= 3) {
            return number - 1;
        }
        int m = number / 3;
        int n = number % 3;
        if (n == 1) {
            m--;
            n = 4;
        }
        else if (n == 0) {
            n = 1;
        }
        return n * pow(3, m);
    }
};