题目

给你一根长度为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米开始确定最优解
  • 从底向上,逐个米数确定最优解
  • 最终得出,最后的最优解

醉后不知天在水,满船清梦压星河