先来看一个问题：
有一座高度是10阶的楼梯，从下往上走，每跨一步可以是一级或两级台阶。要求用程序求出一共一共有多少种走法。
比如，一步一阶，一共10步，这是一种走法。我们可以简写为1,1,1,1,1,1,1,1,1,1。
难画的.png
再比如，每次走两阶，共5步，这是另一种走法。可简写为2,2,2,2,2。
好难画的.png
当然，除此之外，还有很多走法。
容易想到的是利用排列组合的思想，写一个多层嵌套循环遍历出所有可能性，每遍历出一个组合，让计数器加一。
但是这个方法属于暴力枚举，时间复杂度是指数级别的，因此我们想要寻求更高效的解法。
这就是我们的主角动态规划了。先来看看定义：动态规划英文名为Dynamic Programming. 是一种分阶段求解决策问题的数学思想。但它不止用于编程领域，也应用于管理学，经济学，生物学。
是不是听起来高大上但是你还是什么都听不懂啊？
直白点就是一句话：大事化小，小事化了。
拿上面的题目来说，假设只剩最后一步就到达第10阶，这时候会出现几种情况呢？
两种，因为一步走一阶或者两阶，第一种是从第九阶到第十阶，第二种是从第八阶到第十阶。
暂且不管从0到8阶的过程，也不管从0到9阶的过程，想要走到第10阶，一定是从第九阶或者是第八阶开始。
接下来的新问题是：如果已知从0—9阶有X种走法，从0—8阶有Y种走法，那么从0—10阶有多少种走法呢？
没错，就是两部分的总和X+Y。
也就是说：0—10阶走法之和 = 0—8阶走法之和 + 0—9阶走法之和。
方便表达，写为：F(10) = F(9) + F(8)。那么我们怎么求F(9) 和 F(8) 呢？
利用刚才的思路可以推出：F(9) = F(8) + F(7)； F(8) = F(7) + F(6)。
惊不惊喜？意不意外？我们正在把一个复杂的问题分阶段进行简化，逐步简化成简单的问题。
而这就是动态规划的思想。
继续上面的问题，当只剩下一阶或者两阶的时候有多少种走法呢？分别是一种和两种。由此，我们归纳出一下公式：
F(1) = 1；
F(2) = 2；
F(n) = F(n-1) + F(n-2)；(n>=3)
动态规划中包含三个重要的概念：【最优子结构】、【状态转移公式】、【边界】。
还是上面的例子，我们分析得出F(10) = F(9) + F(8)。 F(9) 和 F(8) 就是F(10) 的最优子结构。
当只有一阶或者两阶台阶时，我们可以直接得出结果，无需继续简化。我们称F(1)和F(2)是问题的【边界】。如果一个问题没有边界，将永远无法得到有限的结果。
F(n) = F(n-1) + F(n-2)是阶段与阶段之间的【状态转移方程】。这是动态规划的核心，决定了问题的每一个阶段和下一个阶段的关系。
（可把我厉害坏了，叉会腰）
叉完腰就会发现：完成的仅仅是动态规划的前半部分：问题建模。下面才是真正麻烦的部分：求解问题。
解法1：前面提到的，递归。既然已经归纳出F(n) = F(n-1) + F(n-2)，又知道了递归的结束条件。可以直接用递归实现，代码如下：
int getClimbingWays(int n) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
return getClimbingWays(n - 1) + getClimbingWays(n - 2);
}
代码比较简单，不做解释。
这样来算确实可以计算出最终答案，氮素让我们来看看它的时间复杂度，首先，递归路径是这样的：要计算F(n)，就要先计算F(n - 1) 和 F(n - 2)，以此类推
好难画的.png
看起来hin复杂吧，像一颗二叉树吧。
没错，它就是一颗二叉树，树的节点个数就是我们递归方法所需要计算的次数。不难看出，这颗树的高度是N-1，节点个数接近2(n-1)，所以方法的时间复杂度可以近似的看作O(2n)。
这效率是极低的，想想有什么可以优化的。
想好没有？没想好就再看看上面的图片，或者直接看下图的相同颜色节点你没看错，有些相同的参数被重复计算了，而且越往下走，重复的越多（自己往下画画看）
非常难画的.png
对于重复计算的情况，应该怎么避免呢？
其中一个方法就是用缓存，先创建一个哈希表，每次把不同参数的计算结果存入哈希，当遇到相同参数时，再直接从哈希 表中取出，就不用重复计算了。我们把这成为备忘录算法。代码如下：
int getClimbingWays(int n, HashMap<Integer,Integer> map) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
if(map.contains(n)) {
return map.get(n);
} else {
int value = getClimbingWays(n - 1) + getClimbingWays(n - 2);
map.put(n,value);
return value;
}
上面代码中，当每次需要计算F(n)时，会首先从map集合中寻找匹配元素。若map中存在，则直接返回结果，若map中不存在，就计算出结果，存入备忘录中。
从F(1)到F(n)一共有n个不同的输入，在哈希表中存了N-2个结果，所以时间可空间复杂度都是O(N)。
下面再来看空间上的优化。能不能把空间复杂度进一步减小呢？
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
| --------- |-----: | :----: |
|走法数 |1 | 2|||||||||
就让我们用这一张表格阐述奥义：表格上所表示的是已经确定的对应台阶数的走法数。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3||||||||
第一次迭代，台阶数等于3走法数量是3，介个结果是怎么来的呢？是F(1)和F(2)相加得来的，F(3)只依赖于F(1)和F(2)。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3|5|||||||
第二次迭代，台阶数为4时，走法数是5，这是F(2)和F(3)相加得来的，所以F(4)只依赖于F(2)和F(3)。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3|5|8||||||
同理，在后续迭代中，F(5)只依赖于F(3)和F(4)，F(6)只依赖于F(4)和F(5)……
由此可见，每一次迭代过程中，只要保留之前的两个状态，就可以推导出新的状态。而不用像备忘录算法那般把全部子状态都记录下来。这才是真正的动态规划的实现
解法3：动态规划实现
int getClimbingWays(int n) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
int a = 1;
int b = 2;
int temp = 0;
for(int i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
程序从i = 3 开始迭代，知道 i = n 结束。每一次迭代，都会计算出多一级台阶的走法数。迭代过程只需要保留两个临时变量 a 和 b，为了便于理解，引入了temp变量，代表了当前迭代的结果值。
现在看起来hin简洁有木有？
再来看看时间空间复杂度。时间复杂度明显的是O(0)，由于引入了三个临时变量，所以空间复杂度为O(1)。
这就是动态规划，利用简洁的自底向上的递推方式，实现了时间和空间上的最优化。
氮素，这只是动态规划领域最简单的一道题，因为它只有一个变化维度。
下面给出相对复杂的一道题。
题目：有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
网友评论