算法系列-动态规划(2)：切割钢材问题

切割钢材问题

接上回说到，斐波那契数列是动态规划最简单应用，但动态规划却不是为了用来算那数列。

当时留了个尾巴，就是切割钢材的问题。

不同长度的钢材价格不一样，我现在有一根长度为n的钢材，要怎么切割才能利益最大化？
其中钢材的价格如下

长度	0	1	2	3	4	5	6	7	8	9	10
价格	0	1	5	8	9	10	17	17	20	24	30

罗拉老早就让告诉她动态规划怎么做这玩意，没办法，只能唠嗑唠嗑了。

如何下手？

看到这个问题，没头没脑的怎么下手？臣妾做不大啊。

遇事不决，举个栗子。

假设我现在有一段长度n=4的钢材，我有哪些切割方案呢？

我们把所有切割方案和对应的利润列出来如下：

切割方案.png

1，1，2 和2，1，1之类的是一样的就不列了
总共的方案其实是有2^{n-1}种,因为截断钢材包含1，所以，从右边往左边看，对于每一个长度1，都可以选择切割或者不切割。
当然，我们这边不是排列，是组合问题，数量肯定会少于2^{n-1}
具体的组合数量这里就不详细说明了，有兴趣的可一自己试试。

从图中可以看出，最佳的方案是将钢材截成2 + 2两段。

此时的利润为5 + 5 = 10

从上图中，我们可以得出一个结论，即：

如果我们有一个最优解可以将钢材为k段，(0 <= k <= n)

对于每一段钢材的长度i和长度n之间有：n=i_1+i_2+...+i_k

而对于最大的利润r和每一段钢材的利润p之间有：r_n=p_{i1}+p_{i2}+...+p_{in}

按照我们之前说的，对于每一个长度1的钢材，我们都可以选择切割或不切割

我们只要选择两者中利润大的方案即可。

这样我们就可以通过比较不切割钢材的收益和钢材切割后的收益来确定方案。

对于不切割钢材，我们可以通过价格表直接得到利润。

对于切割钢材，我们可以把它看作是两个子问题。

比如我切成1 和 n-1,1 和 n-1再分成两个子问题，即对长度为1 和 n-1进行分析。

那此时，对于切割的方案利润为：
r=r_1+r_{n-1}

而我切割可选的方案有n-1种(先不考虑剔除重复的情况)：
r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}+r_1

这样我们就可以推导出对于切割长度n的钢材的最大利润的公式为：
r_n = max(p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}+r_1)

p_n对应不切割情况，其他n-1个参数对应其他n-1种情况

这时我们可以发现，我们原本求解n的问题，切割后就变成了:r_1 和 r_{n-1}之类的的子问题.

而这些子问题的求解形式和n的求解形式完全一样。

我们可以将切割后的钢条完全当作两个独立的切割钢条实例。

通过求解所有可能的两段切割方案，从中选取最优的组合使得利润最大化。
从而得到组成切割长度n的钢材最优解。

你们仔细品，细细品，通过利润公式，这玩意怎么看都是递归的亲生儿砸。

这感觉用递归也能做了吧？

如何用递归解决切割钢材问题呢？

在上一篇
算法系列-动态规划(1)：初识动态规划中，八哥说了，切割钢材问题用递归没那么好做，但是也说了也不是不能做。

按照上面分析，用递归好像也没那难吧？

罗拉动手试着写了一下

public class CutRod {
    //钢材价格，0～10英寸的价格
    static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        int n = 4;
        System.out.println("长度为" + n + "的最大收益为：" + rec_cutRod(n));
        n = 10;
        System.out.println("长度为" + n + "的最大收益为：" + rec_cutRod(n));
    }

    public static int rec_cutRod(int n) {
        //当长度为0，自然没有收益，返回0
        if (n == 0) return p[0];
        int rvnd = 0;
        for (int i = 1; i <= n; i++) {
            //对比当前利润，和 切成 i 与 对 n-i 继续切割之和，取较大的组合
            rvnd = p[i];
            for (int j = 1; j < i; j++)
                rvnd = Math.max(rvnd, rec_cutRod(j) + rec_cutRod(i - j));
        }
        return rvnd;
    }
}

//结果
长度为4的最大收益为：10
长度为10的最大收益为：30

不错，不讲码德，先把代码写出来在再考虑优化。

接下来就是优化了，根据算法系列-动态规划(1)：初识动态规划中的案例，就是用备忘录的递归了。

罗拉昨天可是花了功夫去理解的，啪...啪...优化后,带备忘录的代码敲出来了

public class CutRod {
    //钢材价格，0～10英寸的价格
    static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        int n = 4;
        System.out.println("长度为" + n + "的最大收益为：" + men1(n));
        n = 10;
        System.out.println("长度为" + n + "的最大收益为：" + men1(n));
    }

    public static int men1(int n) {
        if (n == 0) return p[0];
        int[] men = new int[n + 1];
        men[0] = 0;
        for (int i = 1; i < n + 1; i++) men[i] = Integer.MIN_VALUE;
        return menHelper1(men, n);
    }

    public static int menHelper1(int[] men, int n) {
        //当长度为0，自然没有收益，返回0
        if (n == 0) return p[0];
        if (men[n] >= 0) return men[n];
        else {
            int rvnd = 0;
            for (int i = 1; i <= n; i++) {
                //对比当前利润，和 切成 i 与 对 n-i 继续切割之和，取较大的组合
                rvnd = p[i];
                for (int j = 1; j < i; j++) {
                    rvnd = Math.max(rvnd, menHelper1(men, j) + menHelper1(men, i - j));
                }
            }
            men[n] = rvnd;
            return rvnd;
        }
    }
}
//结果
长度为4的最大收益为：10
长度为10的最大收益为：30

不错，轻松就写出来了，但是有没有发现还有优化的空间哦。

罗拉闻言检查了几遍代码，然而也没发现继续优化的点，不免有些怀疑。

其实代码部分差不多了，但是我们分析问题的方式可以变一下，

比如代码中rvnd = Math.max(rvnd, menHelper1(men, j) + menHelper1(men, i - j))这部分，我们可以优化一下。

按照我们之前分析公式，这里是相当于把切割后的钢材当做两个子问题继续切割吧？

这就导致会出现二重循环和menHelper1(men, j) + menHelper1(men, i - j)这一部分。

时间复杂度显然大于O(n)小于O(n^2)

我们还可以对切割的方案进行优化。

优化切割方案

之前切割后的钢材当做两个子问题，现在换个思路：

假设我们有一段钢材长度为n，我们从左侧切割长度为i，对这一部分整体出售，对于右侧部分n-i则继续按照子问题的方式继续切割。

那么对于不切割的部分i，收益为:p_i

对于需要继续切割的部分n-i,收益则为:r_{n-1}

切割可选的范围为0<=i<=n,那么对于此时的可以获得的最大利润为：
r_n = max_{0leq i leq=n}(p_i,r_{n-i})

经过这一波操作,我们将之前切割方案会出现两个子问题变为只剩下一个子问题。

那么此时，我们很容易就写出一个递归的代码。

罗拉果然冰雪聪明，一定就通。

啪..啪..,很快哈，一分钟多一点，就写出了代码。

public class CutRod {
    //钢材价格，0～10英寸的价格
    static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        int n = 4;
        System.out.println("长度为" + n + "的最大收益为：" + rec_cutRod(p, n));
        n = 10;
        System.out.println("长度为" + n + "的最大收益为：" + rec_cutRod(p, n));
    }

    public static int rec_cutRod(int[] p, int n) {
        //当长度为0，自然没有收益，返回0
        if (n == 0) return 0;
        int rvnd = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            //对比当前利润，和 切成 i 与 对 n-i 继续切割之和，取较大的组合
            rvnd = Math.max(rvnd, p[i] + rec_cutRod(p, n - i));
        }
        return rvnd;
    }
}

//输出结果
长度为4的最大收益为：10
长度为10的最大收益为：30

老规矩，备忘录优化一下

于是，罗拉又一阵...啪...啪...，又整了一份带备忘录的递归出来。

public class CutRod {
    //钢材价格，0～10英寸的价格
    static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        int n = 4;
        System.out.println("长度为" + n + "的最大收益为：" + men_cutRod(n));
        n = 10;
        System.out.println("长度为" + n + "的最大收益为：" + men_cutRod(n));
    }

    public static int men_cutRod(int n) {
        //记录计算过的利润
        int[] men = new int[n + 1];//因为后续需要比较，先将备忘录所有值置为-1
        for (int i = 0; i < men.length; i++) men[i] = -1;
        return menHelper(men, n);
    }

    public static int menHelper(int[] men, int n) {
        // 备忘录中已经记录了n的最大利润，直接取
        if (men[n] >= 0) return men[n];
        //备忘录没有记录，则执行常规递归
        if (n == 0) return 0;
        else {
            int r = -1;
            for (int i = 1; i <= n; i++) {
                r = Math.max(r, p[i] + menHelper(men, n - i));
            }
            men[n] = r;
        }
        return men[n];
    }
}

//输出结果：
长度为4的最大收益为：10
长度为10的最大收益为：30

这个时候我们再看看时间复杂度，只有一个for循环,虽然有 r = Math.max(r, p[i] + menHelper(men, n - i));,但是由于备忘录的存在，时间复杂度还是O(n)。

这个不仅仅简化了了理解，也提高效率。

我们可以看到，备忘录的递归本质还是从大问题分成小问题，即计算的过程是：n,n-1....2,1。

ps: 虽然代码有for (int i = 1; i <= n; i++),但仔细分析即可发现，我们实际上处理的n的规模，即我们划分的子问题的n是下降的。

这也符合我们之前说的自顶向下的方法。

至于带备忘录的递归是不是动态规划，这个后面会说明

如何用dp数组切割钢材问题呢

备忘录都写出来，那后面dp数组形式的应该也不难了。

首先我们需要记录计算过的值，所以我们用一个数组dp来记录计算过的最佳利润。（为了方便最好长度设为n+1）

然后是确定初始值，既然是自底向上，那肯定是从1,2...,n-1,n（对于这个问题是这样）的顺序计算。

指定初始值：对于(n=0、n=1)我们可以直接得出结果，所以dp[0]=0,dp[1]=1

对于n>=2：我们分析过可以通过左侧不切割整体出售，右侧继续切割化为一个子问题的形式。通过组合所有的方案选出最优方案。

所以我们不难写出推导公式(ps:用md太难写了，写了半天废了，直接画图吧）：
手绘公式图.png

有了上面的分析，罗拉耐不住手痒，于是啪...啪...代码出炉

public class CutRod {
    //钢材价格，0～10英寸的价格
    static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public static void main(String[] args) {
        int n = 4;
        System.out.println("长度为" + n + "的最大收益为：" + cutRod(n));
        n = 10;
        System.out.println("长度为" + n + "的最大收益为：" + cutRod(n));
    }

    public static int cutRod(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n + 1]; //因为dp[0]=0,所以不需要额外赋值
        for (int i = 1; i <= n; i++) {
            int r = p[i];//不切割是保底的，所以直接等于p[i]即可。
            for (int j = 1; j < i; j++) {//遍历所有的切割方案，选择大得
                r = Math.max(r, p[j] + dp[i - j]);
            }
            dp[i] = r;
        }
        return dp[n];
    }
}

//结果
长度为4的最大收益为：10
长度为10的最大收益为：30

怎样，很简单吧？

但是问题来了，dp数组又回到了双重for循环，时间复杂度显然介于O(n) 与 O(n^2)。

能不能再优化，目前八哥也没想到。有更好的优化手段可以评论区留一下。

到此，切割钢材的问题就算是解决，如果罗拉去面试，能到这步，不说offer一定拿，蹭多一杯咖啡还是可以的吧。

疑问+总结

通过上篇文章和本文，对动态应该有点感觉了吧。
接下来就对动态规划做点总结吧，包括填一下前面的坑。

动态规划的思想是什么？

仔细安排求解的顺序
每个子问题只求解一次。（将结果保存下来）
遇到求解过的子问题直接从保存的结果获取。
时空权衡，典型的是空间换时间。（付出额外内存空间保存计算过的结果）

一般的递归之所以效率低，就是因为它会反复求解相同的子问题，所以对于计算顺序，计算结果的保存都是优化递归的重要手段。

怎么判断一个问题能不能用动态规划？

这就得扯一扯了。

首先，什么样的问题我们能联想到动态规划呢？

最起码，这个问题得能分为很多子问题；
其次，通过这些子问题我们可以得到最终问题的答案。
简单的说就是f(n) 与f(p)存在关系，其中p是比n小的问题。

接下来，就判断这问题能不能用动态规划？

无后效性
即过去的内容不会影响将来的内容。（如fn(n)=2f(n-1),对于f(n)而言，我只需要知道f(n-1)即可，之前的我不需要知道）
具备最优子结构
结合我们的案例，切割钢材，我们的对于钢材可以选择切割与不切割。
我们$r_n$本就是最优解，但是r_n=max(p_n,r_i+r_{n-i}),r_n的最优解与r_i 、 r_{n-i}有关。
即最终问题的最优解可以由小问题的最优解得到，这个性质叫做最优子结构。
子问题重叠性
指在递归算法自顶向下对问题求解的时候，每次产生的子问题都不是新的问题，很多子问题会被多次重复计算。
动态规划利用这种特性对子问题只计算一次，将之存入一个数组。当再次遇到该问题的时候直接从数组获得结果，提高效率。

只要问题具备无后效性、最优子结构和子问题重叠，就可以用动态规划。

动态规划的步骤？

寻找最优子结构。(干什么？设计状态的表示形式)
归纳出状态转移方程。（怎么做？）
初始化。（即初始化动态起点）

这只是常用的步骤，动态遇多了就会发现什么乱七八糟的玩意都有。重点是理解思想，掌握核心科技，一点都不慌。

什么是自顶向下、带备忘录的自顶向下，自底向上？

首先说说自顶向下：

自顶向下就是，从最终状态开始，找到可以到达当前状态的状态，如果该状态还没处理，就先处理该状态。

大白话就是：
老板交代给你一个任务，你丫的不讲武德，直接去问下面的人。下面的人也不知道啊，也跑去问下面的人，直到问到知道的人，再层层上报。

那什么是带备忘录的自顶向下呢？

备忘录就是将计算过的值记录下来，下次用到的时候直接从备忘录中查找。减少递归的时间。

大白话就是：
每次老板发任务，就是上一层领导都过来询问，之前傻傻的来一个领导我重新做一遍。
现在我学乖了，第一个领导过来，我做一遍，把结果写在纸上，后面再有领导过来直接告诉他。

那什么是自底向上呢？

我们知道了所有递归的边界，列出了所有的状态。并且当前的状态可以影响、更新后面的状态，直到所有的状态被更新为止。

大白话就是：
知道老板要发布任务，不需要领导来问我，我自己主动把自己这一部分的工作做了，报给我直系领导，
我直系领导得到我的反馈，把自己那部分也做了，再上报给他的直系领导，直到老板得到结果。

如果还不清楚，那再举两个例子。

故事一
某日小明上数学课，他的老师给了很多个不同的直角三角板让小明用尺子去量三角板的三个边，并将长度记录下来。
两个小时过去，小明完成任务，把数据拿给老师。
老师给他说，还有一个任务就是观察三条边之间的数量关系。
又是两个小时，小明说：“老师，我找到了，三条边之中有两条，它们的平方和约等于另外一条的平方。”
老师拍拍小明的头，“你今天学会了一个定理，勾股定理。就是直角三角形有两边平方和等于第三边的平方和”。
故事二
某日老师告诉小明“今天要教你一个定理，勾股定理。”
小明说，“什么是勾股定理呢？”
“勾股定理是说，直角三角形中有两条边的平方和等于第三边的平方。”
然后老师给了一大堆直角三角板给小明，让他去验证。
两个小时后，小明告诉老师定理是正确的.

其中故事一就是自底向上，故事二就是自顶向下。

备忘录的递归算不算动态规划？

如果单纯看前文，可能给大家一个感觉，就是动态规划只有dp数组的形式，备忘录递归不属于动态。其实不然，下面详细总结一下吧。

动态规划有两种等价的实现方法：

带备忘录的自顶向下法(top-down whit memoization)

此方法一般按照自然递归的形式编写过程。
在计算的过程中会保存每一个子问题的解，即备忘录(一般是数组或散列表)
当需要求解问题是，先去备忘录寻找，若备忘录有，直接提取，若无，按照常规方式求解。

之所以叫做备忘录，是因为它“记住”了之前计算过的结果。

自底向上法(bottom-up method)

一般要恰当定义子问题“规模”，使得任何子问题的求解只依赖更小子问题的求解。
将子问题按照规模排序，从小到大的顺序进行求解，记录每一个每一个子问题的结果。(一般是dp数组)
当我们计算一个子问题的时候，它依赖的更小子问题都已经求解完毕，我们直接可以从保存的结果中取值。直到求解到我们问题的规模。

两种实现方法的优劣

这玩意得看具体问题。

一般来说这两种方法效率相差不大。
但是仔细分析一下也可以知道，带备忘录的递归本质还是递归，
频繁的函数调用是少不掉，即使你用了备忘录，
所以自底向上的方法在时间复杂度上可能会有一点优势。

但是这个不绝对。
就比如切割钢材，带备忘录的递归(自顶向下)我可以把时间复杂度下降到O(n)$,但是dp数组(自底向上)的时间复杂度却在O(n)与 O(n^2) 之间

总之就是看问题，别人都叫动态了，有固定才怪了。

大概先写这么多吧，动态规划理解思想，多找几个题目练练手，也就差不多了。
本文很多内容都是八哥看【算法导论三】和其他博文总结。
后续找几个案例让罗拉练练手，免得下次面试又挂了。

如果公式看的难受，可以去公众号看，博客园md支持太操蛋了

如想了解更多，欢迎关注【兔八哥杂谈】，会持续更新一些有意思的内容。

本文为原创文章，转载请注明出处！！！