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

... ...的最短小/最大/最短路径；
都是潜在“候选人”。
解决动态规划问题的步骤
很不幸，解决动态规划问题并没有什么通用秘诀。我们需要在经历过很多问题之后，才能逐渐掌握其诀窍。这确实不容易，毕竟这可能会是你在面试中遇到的最难的问题了。但也先不要气馁，简单来讲，就是用相对简单的工具针对问题进行建模，并不需要花哨的数据结构或算法。
我已经解决过很多此类问题了，但有时还是会觉得毫无头绪，找不到解决方法。练习得越多，就越容易。以下这几点或许能带你走近解决动态规划问题的秘诀：
证明重叠子问题和次优结构特性。
定义子问题。
定义递归。
编写自上而下或自下而上的动态规划解决方案。
复杂度分析因问题而异，但一般来说，时间复杂度可以表示为：
时间~子问题个数*每个子问题的时间
计算自下而上解决方案的空间复杂度很简单，因为其等于存储子问题解决方案所需的空间（多维数组）。
示例
我已经根据所涉及的独立维度的数量对问题进行了分类。这一步并不是必须的，但我发现在设计解决方案时，遵循一定的心理模型是非常有用的。随着编写的代码越来越多，你会找到一些模式，而这就是其中之一。不妨试一下，如果觉得有用的话就用起来吧。
一维问题
（1）斐波那契
因为现在大家都已经对这个问题非常熟悉了，所以我就直接给出递归解决方案：
从递归到自上而下的过程通常都有固定的模式：
检查我们需要的值是否已经在缓存中了。如果是，就返回它。
如果不是，就在返回之前先缓存的解决方案。
这里，用到自下而上的解决方案，我们通过构建一个表（从基本用例为起点），来形成要找的问题的解决方案。这个表是一个一维数组：我们只需要存储较小的问题的解，就可以推导出原始问题的解。
额外空间优化
这种方法可以进一步优化内存，但并不会优化时间（也可以通过其他技术更快地计算斐波纳契数列，但这就是另一篇文章的内容了），只需要使用3个变量，而不必使用数组，因为我们只需要跟踪两个值，即f （n - 1）和f （n - 2），就可以得到我们想要的输出——f （n）。
这种方法更高级，也更常见。如果只需要跟踪：
几个变量，或许我们就可以摆脱一维数组，将其变成几个变量。
二维矩阵中的几行，或许我们可以将其减少成几个一维数组。
等等... ...
通过降维，我们提高了空间的复杂度。现在，你不必记住所有的细节，但在进行过一些实践之后，要试着自己提出这些优化方案，从而增强自己分析问题并将想法转化为代码的能力。在面试中，我会选择更简单的版本，只讨论潜在的优化方案。只有在编写了自己的“标准化”动态规划解决方案，并且时间充足的时候，才动手实施这些优化。
（2）爬楼梯
假设你正在爬一段有n个台阶的楼梯，每次可以爬1或2个台阶。那么要想爬到顶端的话，一共有多少种不同的方法呢？
例1:
输入：2
输出：2
说明：有两种方法可以爬到顶端：1阶+1阶和2阶
例2:
输入：3
输出：3
说明：有三种方法可以爬到顶端：1阶+ 1阶+ 1阶，1阶+ 2阶，2阶+ 1阶
解决方案
先试着自己解决一下这个问题。你可能会想到一个递归解决方案。回顾一下我的说明和前面的示例，看看是否可以自行编写出自上而下的的解决方案。
提示一下：既然这个问题以“有多少种方式”开头，那就应该能想到采用动态规划的潜在可能性。
在这种情况下，如果想要到达第N阶，就要经过第N-1阶或第N-2阶，因为一次可以爬1阶或2阶。如果我们能解决这两个子问题的话，就可以找到一般问题的解。我们将f（N）称为到第N阶的方法数。
要得到f（N），就要先求出f（N-1）和 f（N-2）。
要得到f（N-1），就要先求出f（N-2）和 f（N-3）。
要得到f（N-2），就要先求出f（N-3）和 f（N-4）。
不需要继续罗列下去了吧，你应该已经发现了：
这个问题有重叠的子问题：你需要多次计算f（N-2）， f（N-3）， f（N-4），... ...
这个问题向我们展现了最优子结构：通过f（N-1）和f（N-2）的最优解，可以得到f（N）的最优解。
这表示我们可以通过动态规划来求解该问题。
因为我已经在上一个例子中写过代码了，所以这里就不再写代码了。
大家可以在下方链接中试着编写并测试一下自己的解决方案。
（链接地址：https://leetcode.com/problems/climbing-stairs/?ref=hackernoon.com）