题目描述

给你一根长度为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。

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

输出描述:

输出答案。

示例1

//输入
8
//输出
18

解题思路

由于，所以长度为2和3的需要单独考虑。长度大于4的，我们可以列举一些简单的例子，如下：
4的分解 最大
5的分解 最大
6的分解 最大
8的分解 最大
10的分解 最大
11的分解 最大
。。。。。。
根据上述可以不难发现如下规律：分解的数字主要由3和2组成，所以我们可以进行用递归进行判别

class Solution {
public:
    int cutRope(int number) {
        //单独考虑长度为2和3的情况
        if(number==2)
            return 1;
        else if(number==3)
            return 2;
        //长度大于4的情况
        return dp(number);
    }

    int dp(int number)
    {
        //由于number拆解的单位不超过3，所以当number小于等于3时直接返回
        if(number<=3)
            return number;
        //进行递归求解两种情况，分别是拆分出3或者拆分出2，选取其中最大的即可
        return max(dp(number-3)*3,dp(number-2)*2);
    }
};