剑指offer——剪绳子

题目描述：

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

本题知识点：

贪心  动态规划

解题思路：

1. 当n大于3时，可以确定一定要将绳子剪成由2和3组成的部分，因为如果包含4，可以将4看成2×2，5可以看成2×3，并且最多包含两个2，因为如果有3个2，则2×2×2=8 < 3×3=9。
2. 使用动态规划方法，保存每个绳子长度的最大结果。注意当绳子长度小于4的时候可以直接返回。

代码：

class Solution {
public:
    int cutRope(int number) {
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        int* dp = (int*)malloc((number + 1)*sizeof(int));
        // 因为绳子长度为2/3的时候需要进行至少两次的分割，所以直接返回结果，此时dp保存的数为可以不进行分割的最大值。
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        int maxnum = 0;
        for(int i = 4; i <= number; i++)
        {
            for(int j = 1; j <= i / 2; j++)
                maxnum = max(maxnum, dp[j] * dp[i - j]);
            dp[i] = maxnum;
        }
        return dp[number];
    }
};