算法入个门——动态规划（java版）

算法入个门——动态规划（java版） 导语

Hello大家好，这里是算法入个门系列

作者就是想通过算法入个门系列与大家一同探讨如何理解并掌握常用算法，对，这个就是开设这个专栏要达到的目标，共勉之

引言

相信大家LeetCode也刷了有一段时间了，但可能存在一些问题

比如：对于一些常见算法标签不熟悉？对于题解一脸懵？咋整？？？

怎么解决这些问题呢？

我想可以这么解决——去了解一下算法标签中未知的算法的原理~

LeetCode常见算法标签

动态规划、滑动窗口、深度优先搜索、广度优先搜索、数学、哈希表、贪心......

嗯。。。是很常见，且一般偏难的那种，但不要被这些标签吓到，只要肯下功夫，理解了它们，你就可以运用之。

算法介绍

dynamic programming（动态表格法），俗称DP，通常用来求解最优化问题（optimization problem）

引用自《算法导论》

动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。分治将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

实现步骤介绍，一共4个步骤

引用自《算法导论》

刻画一个最优解的结构特征递归地定义最优解的值计算最优解的值，通过采用自底向上的方法利用计算出的信息构造一个最优解

说实话，看到这些话的时候，还是挺懵的，只知道会将子子问题记录到表格中，但不知道具体怎么实施，对吧，所以继续往下看，后面会通过实例来加深理解。

实例讲解 钢条切割问题

一根长n的钢条，可以切成k段，1<=k<=n，但不同的长度对应的收益也不同，收益如下图所示

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

 问：如果甲有一根钢条，长度N在[1,10]之间，求怎么切能达到利益最大化，N是可输入的

解题思路

① 当遇到这样的问题的时候，我们可能首先会想到这得有好多种解法啊？

于是乎求共有多少种解法：长度为N，最多可切成N段，切N-1下，每一下都有2种选择（切/不切），共有2^(N-1)种解法。

② 到底应该怎么解呢？

开始分析：

当N=1，（不切）1种解法

当N=2，（不切；切1，剩下N=1，N=1就1种切法）2种解法

当N=3，（不切；切1，剩下N=2，N=2有2种解法；切2，剩下N=1，N=1有1种解法）4种解法

当N=4，（不切，切1，剩下N=3，N=3有4种解法；切2，剩下N=2有2种解法；切3，剩下N=1，N=1有1种解法）8种解法

......

通过分析，我们发现，N与N-1，N-2，N-3，...，1之间是有关系的，如果我们先计算并存储了当N=1的最优解，N=2的最优解，N=3的最优解，然后求N=N的最优解时，则只需要计算N次（不切；切1；切2，切3，...，切N-1，并分别与切口处左侧pi的值进行求和，通过比较求和的结果，每次比较后都仅保留最大值，就可以算出来N的最大收益），于是乎算法可以这么写。

③ 代码实现

public int cutRod(int[] p, int n) {
    // 记录子问题最优解
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // 记录最优解
        int q = 0;
        for (int j = 1; j <= i; j++) {
            // p[j-1]的含义即在第j个位置切(j=1,2,3,...,i)，左侧的收益为p[j-1]，右侧的收益最优解为dp[i-j]
            q = Math.max(q, p[j - 1] + dp[i - j]);
        }
        // 将n长的钢筋切法收益的最优解赋值给dp[n]
        dp[i] = q;
    }
    return dp[n];
}

此题没有加判断，数组p中的数值均大于0，于是q设为了0，实际运用中，q应该是小于p中最小数的值

结语

这就是理解求最优解的动态规划算法的一种思路，共勉之，希望大家都能刷穿LeetCode，早日成为巨佬，喜欢的话，请一键三连支持一下，后续的将更加精彩 ~