关于java:动态规划解题方法

魔幻的 2020 让咱们狐疑人生是否存在最优解？咱们某个工夫的决策到底是否正确？历史不能扭转，但却会重演，咱们到底要从过来中学到什么呢？

让咱们一起从动静布局中，来找寻这些问题的答案吧～

（咳咳，明天开始回归算法系列，来聊一聊之前的算法文章中没有讲到的内容。

动静布局（Dynamic Programic，简称 DP）是一种求解最优解的办法，它是一种非凡的分治思维，利用它能够实现工夫复杂度的优化，有时也能够进行空间复杂度的优化，有时是须要更多的空间的（相比其余办法）。

dynamic 是动静的意思，也就是变动的，programing 能够了解为方程（我瞎说的），联合起来就是动静布局是用状态转移方程来求得最优解的算法。

在解释动静布局的时候，咱们顺便理一理和它相干的两种思维——分治和贪婪算法。

分治是把大问题分解成若干个子问题，这样的能合成性质就是最优子结构的。

最简略的例子就是小明在解决问题 A 的时候，发现问题 A 是由问题 B 和 C 一起组成的，所以他想要解决问题 A，就须要把 B、C 一起去解决。

动静布局是分治法的特例。

动静布局比分治法多了一种，就是重叠的子问题。

什么是重叠的子问题呢？举个例子来讲，可恶的小明遇到了一个可恶的问题，那就是问题 A，然而在后面须要解决一连串的问题，咱们用 A1，A2，A3，A4 ... A 来示意，在解决 A1 之后会用它的解去解决相似的问题 A2，
而后再去解决A3，最终再去解决 A，这就是重叠的子问题的典型代表。（上面的例题还会解释这个概念）

贪婪比动静布局更加的非凡，它还须要问题满足另外一个性质——贪婪抉择性质，每次都能够把原问题合成成为一个子问题。

实际上再用动规的例子来阐明贪婪，在解决 A1，A2，A3，A4 ... A 的时候，他发现解决不光有一种重叠子问题的性质在外面，更乏味的是，解决 A1 须要一种非凡的规定。

例如小明当初在玩电脑游戏，而电脑游戏的最终目标是达到 A，而他又发现，只有始终往右边走就能达到最终的目的地了。这就是一种贪婪的算法，在每次往右边走，就是一种非凡的规定，而走到目的地A 须要很多反复的子问题，也即每次流动一个单位。

其实在很久之前我写的一篇文章中，以斐波那契数列这道根本题为例，具体论述了从递归到 DP 的优化办法和思路，以及简略题的不简略的答法，大家无妨先去温习一下：

这才是面试官想听的：从递归到 DP 的优化

而后咱们再来看看个别的动静布局解题思路。

回到动静布局，这里有四个根本的概念：

state（状态示意）
function（转移方程）
initial（初始化）
final state（最终的状态）

在刚开始的时候，咱们首先须要构建一个存储数据的表格，个别是数组或者矩阵，而后设定好每一个格子到下一个格子须要的转移方程。

而后去执行反复的步骤，从初始化的状态始终计算到最终须要的状态。

回到小明的例子，刚开始的时候小明须要确定一个 state（A0代表的是什么），而后找到 A0 与A1之间的关系，从初始化开始始终计算到最终的状态。

接下来，咱们以 Leetcode 120 来具体的解说这个算法。

当初咱们来剖析一下这个题目，首先咱们剖析一下为什么它是一个动静布局的问题。

题目是要找到一种门路的和，这种门路和是要最小的，也就是求一个 最优解。

因为这是门路，咱们就是在每一层外面抉择一个适合的数字，而后连成一个门路，在这道题目外面，最小的门路是 2-3-5-1，在第一层挑了2，在第二层挑了3。也就是说总的问题拆分成了每一层的问题，而每一层之间都有一种依赖性在外面，例如第二层抉择了3 之后只能在 6,5 之中抉择一个，不能跳到 7，这就是 重叠子问题。

咱们用 f[i][j] 示意从三角形顶部走到地位 [i][j] 的最小门路和。这里的地位 i, j 指的是三角形中第 i 行第 j 列的地位。

因为只能是从一个节点到相邻的两个节点（树），因而要想走到地位 [i][j]，上一步就只能在地位 [i-1][j-1] 或者地位 [i-1][j]。

咱们在这两个地位中抉择一个门路和较小的来进行转移，状态转移方程为：

f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]，

其中 c[i][j] 指的是 triangle[i][j] 的数值。

当设定完通项方程之后，咱们还须要设定一些非凡的转化方程：

当凑近左边界时，也就是 j = 0 时，于是没有 f[i-1][j−1] 这一项，状态转移方程变为：

f[i][0]=f[i−1][0]+c[i][0]

当凑近右边界时，咱们间接用上一层斜上角地位的数值进行计算：

f[i][i]=f[i−1][i−1]+c[i][i]

最终，咱们只须要在 dp 三角形的最初一行找到最小值就能够了。

那么初始的状态是什么呢？

实际上就是刚开始的时候设定 dp 的第一个单位的数值为cp[0][0]，也即是dp[0][0] = c[0][0]。

状态转换图如下所示：

代码如下：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {
       // 创建表格
        int[][] dp = new int[triangle.size()][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);
       // 动静布局的方程式
        for (int i = 1; i < dp.length; i++) {for (int j = 0; j <= i; j++) {int curr = triangle.get(i).get(j);
                if (j == 0) {dp[i][j] = dp[i-1][j] + curr;
                } else if (j == i) {dp[i][j] = dp[i-1][j-1] + curr;
                } else {dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + curr;
                }
            }
        }
        int res = dp[triangle.size()-1][0];
        for (int j = 1; j < triangle.size(); j++) {res = Math.min(res, dp[triangle.size()-1][j]);
        }
        return res;
    }
}

上面来剖析这个问题的工夫复杂度以及空间复杂度，一般来说空间复杂度是就是 DP 表格的大小。

在这道问题中是 O(n^2)，而对于工夫复杂度来说，就是整个 dp 的遍历次数，而在这个问题中咱们只进行了一次遍历，也即一个矩阵的遍历，所以是O(n^2)。

而如果想要优化到 O(n)，咱们须要怎么做呢？

实际上这个就波及到了一种 状态压缩 的办法，也即压缩这个状态表。

那么怎么去压缩呢？

这个问题比较简单，因为 dp[i][j] 仅仅与上一层的状态无关，所以说与前两层的是没有任何关系的，因而咱们不用存储这些无关的状态。

实际上最简略的状态压缩就是保留好前两个状态即可，例如在计算第四行的时候，保留第三行以及第二行的状态表，而后交替的进行更新就能够啦。

class Solution {public int minimumTotal(List<List<Integer>> triangle) {
      // 只保留最近 2 行
        int[][] dp = new int[2][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            int row = i % 2;
            int prevRow = (i-1) % 2;
            for (int j = 0; j <= i; j++) {if (j == 0) {dp[row][j] = dp[prevRow][j] + triangle.get(i).get(j);
                } else if (j == i) {dp[row][j] = dp[prevRow][j-1] + triangle.get(i).get(j);
                } else {dp[row][j] = Math.min(dp[prevRow][j-1], dp[prevRow][j]) + triangle.get(i).get(j);
                }
            }
        }

        int res = dp[(triangle.size() - 1) % 2][0];
        for (int j = 1; j < triangle.size(); j++) {res = Math.min(res, dp[(triangle.size() - 1) % 2][j]);
        }
        return res;
    }
}

这个的空间复杂度是 O(2n)，能不能压缩成严格意义上的 O(n) 呢？

那么再往后是否还可能进行状态的压缩呢？

答案是能够的，咱们能够再想一种方程而后达到最优的空间复杂度的指标。

当咱们在计算地位 [i][j] 时，f[j+1] 到 f[i] 曾经是第 i 行的值，而 f[0] 到 f[j] 依然是第 i-1 行的值。

此时咱们间接通过 f[j] = min(f[j−1], f[j]) + c[i][j]来计算，然而这个时候咱们须要j 是倒着遍历的，因为这样才不会影响之前记录下的状态。

如果从 1 开始，那么计算 2 的时候就会用到新的 1 的数值而不是上一层 1 的数值。

代码如下：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int[] dp = new int[triangle.size()];
        dp[0] = triangle.get(0).get(0);

        for (int i = 1; i < triangle.size(); i++) {dp[i] = dp[i-1] + triangle.get(i).get(i);
            for (int j = i-1; j > 0; j--) {dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
            }
            dp[0] += triangle.get(i).get(0);
        }

        int res = dp[0];
        for (int j = 1; j < triangle.size(); j++) {res = Math.min(res, dp[j]);
        }
        return res;
    }
}

办法 1 有点绕，但如果自下向上来了解，就会变得很简略，这个办法也叫 bottom-up，办法 1 则是 top-down。

从后果登程，这个问题是一个 发散三角树 的问题，从最初一行登程，而后每一行每一行的进行递推，那么第一行就是最终的后果了。

举个最简略的例子：

 1
1 2

如果从最底下往上登程，实际上找最小值办法的法则很容易找到，那就是在第二行 [1，2] 外面抉择一个就能够了，因为他们两个都要走到根节点。

也就是在下一行的两个数外面取个小的就行了，那么后果就是第一行的数值。

咱们先用二维的转移矩阵来解释这个问题，用这种办法也不须要思考办法 1 外面的边界条件了：
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j]

状态转换图如下所示：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int[][] dp = new int[triangle.size()][triangle.size()];
        // 创立 DP 空间
        for (int i = 0; i < triangle.size(); i++) {dp[triangle.size() - 1][i] = triangle.get(triangle.size() - 1).get(i);
        }

        for (int i = triangle.size() - 2; i >= 0; i--) {for (int j = 0; j < triangle.get(i).size(); j++) {dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }

        return dp[0][0];
    }
}

那么在进行状态压缩的时候，咱们该怎么去做呢？

实际上就是只用一个状态表来示意所有的。

因为只是和上一个状态相干，所以说能够示意成如下的模式：

dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]，

咱们只用 j 来代表以后的状态，而后最终输入 dp[0] 即可。

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int[] dp = new int[triangle.size()];
        // 创立 DP 空间
        for (int i = 0; i < triangle.size(); i++) {dp[i] = triangle.get(triangle.size() - 1).get(i);
        }

        for (int i = triangle.size() - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }

        return dp[0];
    }
}

以上就是动静布局解题办法的浅显介绍，总的来说，咱们须要留神动静布局的这么几件事件。

确定是否须要用动静布局；
确定动静布局的四个局部；
写代码。

实际上难点就是 转移方程，这个的确须要大量的积攒才可能在面试的时候看穿，甚至有些题没见过的话就是想不进去的。

然而没见过就做不进去的题面试个别也不会考，所以大家也不必太放心，重点还是把握办法，触类旁通。

接下来我也会演绎总结一些动静布局的常见题型，和大家一起摸索 最优解。

更多算法文章，倡议珍藏这个链接：

齐姐聊算法

我是小齐，后端开发工程师，坐标纽约，曾在投行做 Quant，后退出科技公司 FLAG 中的一家。

业余时间打理公粽号【NYCSDE】，更新略少，干货很多，倡议加个星标避免错过。

关于java:动态规划解题方法

什么是动静布局

分治

动静布局

贪婪

入门

解题思路

题目形容

办法一

办法 2

总结