题目
给你一根长度为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