剪绳子 I
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
解题思路
1，可以用动态规划解，用dp[i]表示长度为i的绳子的最大值
2，如果从长度为i的绳子上拆出一段j，这时候 积为j*dp[i-j]
3,dp[i]的值就为j取值从1到i－1 时候积的值，以及（i-j)*j 中最大值
4，状态转移方程为dp[i]=max(dp[i-j]*j,dp[i],(i-j)*j
代码实现
剪绳子 II
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 1000
解题思路：
1，由于取模了，所以不能用动态规划来解了
2，我们可以找规律来解
3，我们可以参照整数拆分来求解，在整数拆分基础上取模
代码实现
整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
解题思路：
1，当绳子长度为1，2，3 的时候只能拆成两段1，n－1
2，当拆分因子中没有1的时候总有 积>=和
3，因此我们可以把绳子拆出更多3，没法拆出3的时候拆成2
A，当n%3==2时候，pow（3，n／3）＊2
B，当n％3=＝1时候，pow（3，n/3－1）＊4
C，当n%3==0时候，pow（3，n／3）
首先，任何一个数字 n，都可以被分为有限个小数字之和。
根据常理：一般这 M 个数字的乘积要大于原数字 n。
其次，所有数字n 都可以通过对一个因子 xx 求整数部分 a（a = n // x） 和余数部分 b（ b = n % x）；
即得出数字 n 由 a 个 x 和 1 个 b 相加而成。
问题转化：是否有优先级最高的因子 x存在？若有，我们就可以把问题转化为求 x^a * b 这个表达式的最大值。
例如：2 = 1 + 1，1 * 1 < 2，因此 2 比 1+1 更优；
例如：3 = 1 + 2，1 * 2 < 3，因此 3 比 1 和 2 更优；
例如：4 = 2 + 2，2 * 2 = 4，因此可以认为 4 与 2 等价，因此见到 4 就拆分；
例如：5 = 2 + 3；因为每个 5都可以拆分为 2+3，而 2 * 3 = 6 > 5，因此见到 5 就拆分。
例如：6 = 3 + 3 = 2 + 2 + 2；因为 3 * 3 > 2 * 2 * 2 > 6。因此见到 66 就拆分，并且 3是比 2更优的因子。
易推出：大数字都可以被拆分为多个小因子，以获取更大的乘积，只有 2和 3 不需要拆分。
n 拆分 乘积
2 1+1 1 不拆分，2 比 1+1 更优
3 1+2 2 不拆分，3 比 1+2 更优
4 2+2 4 拆分，2 与 4 等价
5 2+3 6 拆分
6 3+3 9 拆分，3+3 比 2+2+2 更优
7 2+2+3 12 拆分，但不能拆成 1+3+3
观察以上枚举，我们可以列出以下贪心法则：
第一优先级：3；把数字 n 拆成尽可能多的 3 之和；
特殊情况：拆完后，如果余数是 1；则应把最后的 3 + 1 替换为 2 + 2，因为后者乘积更大；
第二优先级：2；留下的余数如果是 2，则保留，不再拆为 1+1。
算法流程：
当 n <= 3 时，按照贪心规则应直接保留原数字，但由于题目要求必须拆分，因此必须拆出一个 1，即直接返回 n - 1；
求 n除以 3 的整数部分 a和余数部分 b；
当 b == 0时，直接返回 3^a；
当 b == 1 时，要将一个 1 + 3 转换为 2+2，此时返回 3^{a-1} * 2*2
当b==2 时，返回3^{a}*2
代码实现