减绳子

题目描述
给你一根长度为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);
    }
};