【剑指Offer】67、剪绳子
??题目描述：
??给你一根长度为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分成很多个整数，要求这些数字的乘积最大，问你最大的乘积是多少？
??解题思路：
??本题是动态规划和贪心算法的应用实例，有以下两种解法：
??解法一：动态规划
??令F(n)表示长度为n的绳子剪成若干段之后，每一段长度的最大乘积。我们以剪第 i 次作为第 i 次决策，则可以得到：当剪第1次时，可以选择n-1个位置，即有n-1个不同的选择；同样，在剪第 i 次时，同样有n-i个位置可以选择，因此，我们可以得到一个递推公式：F(n)=max(F(i)*F(n-i))，其中0
??通过公式可以看出，这是一个自上而下的递归问题，是一个典型的动态规划问题，可以通过存储局部值的方式避免重复计算，先计算F(1)，接着计算F(2)…，直到得到F(n)。
??同时，需要注意特殊情况，当n=2时，只可以划分为两个长度为1的小段，因此F(2)=1，当n=3时，不难得到F(3)=2.
??解法二：贪心法
??我们可以通过先例举小的数字，然后观察划分规律。
| 长度 | 最大乘积 | 长度 | 最大乘积 |
|---|---|---|---|
| 2 | 1*1 | 7 | 2*2*3 |
| 3 | 1*2 | 8 | 2*3*3 |
| 4 | 2*2 | 9 | 3*3*3 |
| 5 | 2*3 | 10 | 2*2*3*3 |
| 6 | 3*3 | 11 | 2*3*3*3 |
- 当n%3==0时，也就是全都是3，乘积肯定最大
- 当n%3==1时，注意
1*3没有2*2大，所以我们应该把一个3拿出来和剩下的那个1组成2*2的形式 - 当n%3==2时，
2*3*……*3的形式乘积最大
??编程实现（Java）：
//方法一：动态规划
public class Solution {
public int cutRope(int target) {
if(target==2)
return 1;
if(target==3)
return 2;
int[] dp=new int[target+1];
dp[0]=0; // 不代表最大值，是为了方便i>=4的计算
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(int i=4;i<=target;i++){ //依次求出比n小的每个值，避免重复计算
int maxN=0;
for(int j=1;j<=i/2;j++){
maxN=Math.max(maxN,dp[j]*dp[i-j]);
dp[i]=maxN;
}
}
return dp[target];
}
}
//方法二：贪心法
public class Solution {
public int cutRope(int target) {
if(target==2)
return 1;
if(target==3)
return 2;
int p=target/3, q=target%3;
double res=0;
if(q==0)
res=Math.pow(3,p);
else if(q==1)
res=2*2*Math.pow(3,p-1);
else if(q==2)
res=2*Math.pow(3,p);
return (int)res;
}
}