漫画：五分钟了解动态规划

————————————

题目：

有一座高度是10级台阶的楼梯，

从下往上走，

每跨一步只能向上1级或者2级台阶。

要求用程序来求出一共有多少种走法。

比如，

每次走1级台阶,一共走10步，

这是其中一种走法。

我们可以简写成 

1,1,1,1,1,1,1,1,1,1。

再比如，

每次走2级台阶，

一共走5步，

这是另一种走法。

我们可以简写成

 2,2,2,2,2。

当然，

除此之外，

还有很多很多种走法。

第一种情况：

第二种情况：

把思路画出来，就是这样子：

F(1) = 1;

F(2) = 2; 

F(n) = F(n-1)+F(n-2)（n>=3）

方法一：递归求解

由于代码比较简单，

这里就不做过多解释了。

如图所示，

相同的颜色代表了方法被传入相同的参数。

方法二：备忘录算法

在以上代码中，

集合map是一个备忘录。

当每次需要计算F(N)的时候，

会首先从map中寻找匹配元素。

如果map中存在，就直接返回结果，

如果map中不存在，

就计算出结果，

存入备忘录中。

方法三：动态规划求解

程序从 i=3 开始迭代，

一直到 i=n 结束。

每一次迭代，

都会计算出多一级台阶的走法数量。

迭代过程中只需保留两个临时变量a和b，

分别代表了上一次和上上次迭代的结果。 

为了便于理解，

我引入了temp变量。

temp代表了当前迭代的结果值。

文章转载自IT名校尚学堂

学习过马士兵java的小朋友举个爪

动态规划，生信人必备

好好学习，天天向上

欢迎关注生信人