给你一根长度为 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
方法一：归纳总结 举例子来找规律： 4 ： 2*2 5 ： 2*3 6 ： 3*3 7 ： 2*2*3 或者4*3 8 ： 2*3*3 9 ： 3*3*3 10：2*2*3*3 或者4*3*3 11：2*3*3*3 12：3*3*3*3 13：2*2*3*3*3 或者4*3*3*3
首先判断 k[0] 到 k[m] 可能有哪些数字，实际上只可能是 2 或者 3。5<2*3, 6<3*3, 比 6 更大的数字我们就更不用考虑了，肯定要继续分。其次看 2 和 3 的数量，2 的数量肯定小于 3 个，因为2*2*2<3*3。x = n%3; y = n/3;y表示 3 的数量，x 表示 2 的数量，x==0(没有2)；x==1(两个2,y-1个3)；x==2(一个2)。特殊情况，n=2 只能是 1*1，n=3 只能是 2*1，直接返回。 class Solution { public: int cutRope(int number) { if (number == 2) return 1; if (number == 3) return 2; int x = number%3; int y = number/3; if (x == 0) return pow(3, y); if (x == 1) return 4 * pow(3, y-1); if (x == 2) return 2 * pow(3, y); } };方法二：动态规划
子问题：求和为 i 的整数分割后的最大乘积，用 dp[i] 表示 递推公式：dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j)));
dp[i]: 表示不分割出 j，j*dp[i-j] 表示 i 分割出 j，剩下的再分割，得到的最大乘积j*(i-j) 表示 i 分割出 j，剩下的不分割 class Solution { public: int integerBreak(int n) { vector<int>dp(n+1, 0); for (int i = 2; i <= n; i++){ for (int j = 1; j <= i-1; j++){ dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j))); } } return dp[n]; } };方法二：递归 很容易懂，最后的结果就是 x 个 3 和 y 个 2 相乘。
class Solution { public: int cutRope(int number) { if(number == 2) return 1; if(number == 3) return 2; return cutRope1(number); } int cutRope1(int n){ if (n <= 4) return n; int x = 2 * cutRope1(n - 2); int y = 3 * cutRope1(n - 3); return max(x, y); } };