剪绳子 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
代码实现
代码语言：javascript复制func cuttingRope(n int) int {
dp:=make([]int,n 1)
dp[1]=1
for i:=2;i<=n;i {
m:=0
for j:=i-1;j>0;j--{
m=max(dp[i-j]*j,m,(i-j)*j)
}
dp[i]=m
}
return dp[n]
}
func max(a,b,c int)int{
if a>=b && a>=c{
return a
}
if b>=c && b>=a{
return b
}
return c
}
/*
我们考虑最后一步的情况，即最后剪的一下，会把绳子分为两部分，且两部分的结果互不影响
定义 dp[i] 表示长度i的绳子能得到的最大乘积
则 dp[i] 等于 在绳子区间[0, i)之间剪开的两部分乘积最大值
如果剪开位置为k，则区间分为[0, k)和[k, i)两部分
第一部分长度为k, 第二部分长度为i-k
第二部分存在剪和不剪两种情况，剪的时候值为dp[i-k]，不剪的时候取（i-k)
于是得到状态转换方程：
dp[i] = max{ k * dp[i-k], k * (i-k)} (2<=k<=i)
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n 1, 0);
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i<=n; i ){
for (int k = 2; k <= i-1; k ){
dp[i] = max(dp[i], max(k*(i-k), k*dp[i-k]));
}
}
return dp[n];
}
};
*/剪绳子 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，我们可以参照整数拆分来求解，在整数拆分基础上取模
代码实现
代码语言：javascript复制func cuttingRope(n int) int {
if n<=3{
return 1*(n-1)
}
res:=1
if n%3==2{
res*=2
n-=2
}
if n%3==1{
res*=4
n-=4
}
for i:=0;i<n/3;i {
res=res*300000007
}
return res
}整数拆分
给定一个正整数 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
代码实现
代码语言：javascript复制func integerBreak(n int) int {
if n<=3{
return 1*(n-1)
}
res:=1
if n%3==1{
res*=4
n-=4
}
if n%3==2{
res*=2
n-=2
}
for i:=0;i<n/3;i {
res*=3
}
return res
}
