题目
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:
输入一个数n，意义见题面。（2 <= n <= 60）
输出描述:
输出答案。
答案
public class Solution {
public int cutRope(int target) {
int[] arrs = new int[target + 1];
for (int i = 0; i < arrs.length; i++) {
arrs[i] = -1;
}
if (target == 2) {
return 1;
} else if (target == 3){
return 2;
} else if (target ==4){
return 4;
}
arrs[1] = 1;
arrs[2] = 2;
arrs[3] = 3;
arrs[4] = 4;
if (target >= 5) {
for (int i = 5; i <= target; i++) {
for (int j = 1; j < i; j++) {
arrs[i] = Math.max(arrs[i], j * arrs[i - j]);
}
}
}
return arrs[target];
}
}
题解
这道题我们用动态规划来处理，首先我们需要知道什么是动态规划
动态规划
什么是动态规划
在了解什么是动态规划之前，我们需要了解什么是递归回溯
递归回溯
递归是一种思想，它将一个问题拆解成若干个子问题，比如在割绳子的例子中，我们要割6米的绳子，可以先割一段一米的，至于剩下5米要割掉几段割几米，我们完全不关心。从寻找两个子问题最优解变成了一个。
但这会导致一个问题，首先就是这种递归的代价太大了，因为进行了过多的重复运算
接下来我们着手解决这个问题
最优子
什么是最优子结构？
想象一下这个问题，我们需要完美的切割这条8米绳子，我们可以有以下三种组合，分别是：【先切1米，剩余7米】，【先切2米，剩余6米】，【先切3米，剩余5米】，【先切4米，剩余4米】。
如果我们要完美切割8米长的绳子，我们就需要在以上四种方案种找到最完美的一种，我们假设是第二种。
我们先切2米，那么剩下的问题就是，如何完美的切割6米长的绳子，我们重复这个循环，直到切割完毕。
回看一下，我们会发现，我们将一个问题的最优解划分到了其他小问题的最优解上，大问题的最优解符合小问题的最优解，这就是最优子结构。
了解了什么是最优子结构，我们开始解决递归带来的问题。
剪枝（备忘）
这两个其实是一个东西。
先来说递归中遗留的问题，我们进行了大量的重复运算，但是我们不想进行这种重复行为，我们可以用一个数组或者链表之类的东西给他存起来，下次要用直接取出来不就好了，这个就是备忘。
回头看我的代码，每一次备忘的时候，我们都是把最好的数据备忘到了数组中，这样在我们进行下一次调用这个数据的时候———比如我们要切割5米的时候，就可以直接拿到切割5米的最好数据，而不用再去处理切割5米的其他情况，这就达成了剪枝的效果，完全摒弃了其他坏数据。
那么到最后，我们来回答一下第一个问题，什么是动态规划？
所谓动态规划，就是在递归回溯的基础上，对一些符合最优子的问题，加入了备忘的功能，从而能达成剪枝的效果。
什么时候使用动态规划？
动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。通常用来求解最优化问题
当子问题有重叠，且整个问题处于最优子结构的情况下，我们使用动态规划。
怎样使用动态规划呢？
- 确定什么样的解是最优解
- 开始定义最优解的值，在这个例子中就是从5米开始确定最优解
- 从底向上，逐个米数确定最优解
- 最终得出，最后的最优解
Comments | NOTHING