解决|关于动态规划，你想知道的都在这里了！( 三 ) 实例|于同|最短路径|子结构

（3）最长递增子序列
给定一个未排序的整数数组，求最长递增子序列的长度。
例如，对于数组[10,9,2,5,3,7,101,18]而言，其输出为4，即序列[2,3,7,101]
解决方案
我们需要找到大小为n的数组的最长递增子序列的长度。这听起来像是一个可以通过动态规划来解决的优化问题，那么让我们来试一下。假设我们已经有了大小为N的问题的解，称其为s（n）,然后我们在数组中增加了一个额外元素，称为Y。那么，你能重复使用X的解决方案来解决这个新问题么？这个问题通常会为我们带来一些启发。
在这里，我们需要知道新元素是否可以扩展任一现有序列：
迭代数组中的每一个元素，我们称其为X。
如果新元素Y大于X，那么序列可以扩展一个元素。
如果我们已经存储了所有子问题的解，那么获取新长度是非常简单的——只需在数组中进行查找即可。我们可以根据子问题的最优解得出新问题的解。
返回新的最长递增子序列的长度。
我们似乎得到了某种算法。继续我们的分析：
最优子结构：我们已经证明了大小为n的问题的最优解可以由子问题的最优解计算出来。
重叠子问题：要想计算s（n），则需要s（0）， s（1），... ...，s（n-1）。同样，要计算s（n-1），则需要s（0）， s（1），... ...，s（n-2）。同样的问题需要进行多次计算。
以下是该自下而上解决方案的代码。
大家可以在下方链接中试着编写并测试一下自己的解决方案。
（链接地址：https://leetcode.com/problems/longest-increasing-subsequence/?ref=hackernoon.com）
（4）有多少BST
对于给定的n，有多少结构唯一的存储值为1... ...n的BST（二叉搜索树）？
例子：
输入：5
输出：42
说明：给定n = 5, 总共有42个唯一的BST
解决方案
我们一起来看看这个例子。假设我们有数字1、2、3、4、5，如何定义BST？
我只需要选择其中一个数作为根，先假设其为数字3，则：
3是根
3的左边是数字1和2
3的右边是数字4和5
我们可以解决（1，2）和（4，5）的相同子问题（暂且称其为解决方案L和R），数一数以3为根可以形成多少个BST，即L*R。如果我们对每一个可能的根都这样做，并且把所有的结果相加的话，就可以得到我们所需的解决方案C（n）。如你所见，有条不紊地从几个例子出发，可以帮助我们更好地设计算法。
其实，我们只需要：
选一个元素作为BST的根；
解决（1到根-1）和（根+1到n）两个数字的相同问题；
将每个子问题的两个结果相乘；
将其加到我们的运行总计上；
继续下一个根；
实际上，我们并不关心数组两边的数字是什么。我们只需要子树的大小，即根的左右两边的元素个数。这个问题中的每个实例都会产生相同的结果。在之前的例子中，L和R都是C（2）的解。我们只需要计算一次C（2），缓存，然后重复使用即可。
大家可以在下方链接中试着编写并测试一下自己的解决方案。
（链接地址：https://leetcode.com/problems/unique-binary-search-trees/?ref=hackernoon.com）
二维问题
这些问题通常比较难建模，因为它涉及两个维度。常见的例子是，在两个字符串中迭代，或移动映射。
自上而下的解决方案和之前没有太大的区别：找到递归并使用缓存。
对于自下而上的解决方案，一个2D数组就足以存储结果了。像我之前提到的，可能会减少一个或几个一维数组，但是没有必要太在意。之所以提到这一点只是以防你在解决问题时看到会有点摸不着头脑。
我曾在另一篇文章中说过，学习是迭代的。首先，要把注意力集中在理解基础知识上，然后再一点一点地增加更多的细节。
（1）最小路径和
给定m×n的非负数网格，找出一条从左上到右下的路径，使路径上所有数字之和最小。
注意：你只能选择向下移动或向右移动。
例子：
输入：[ [1,3,1], [1,5,1], [4,2,1] ]
输出：7
说明：因为路径13111总和最小
解决方案
最小化问题应该会让你想到动态规划。进一步分析，路径可以经过任意单元格C（i，j）（即不在上边框或左边框），单元格A = （i-1, j）和B=（i，j-1）。由此，我们发现，有些问题需要进行多次计算。此外，我们如果知道A和B的最优解，就可以计算出当前单元格的最优解为min(sol (A)，sol(B)) + 1，因为我们只能通过当前单元格来表示A或B，要想移动到当前单元格就需要多走一步。换句话说，这是一个最优子结构和重叠问题。我们可以使用动态规划。