漫画：什么是动态规划？

（点击 上方公众号 ，可快速关注）

来源：伯乐专栏作者/ 玻璃猫， 微信公众号 - 梦见（dreamsee321）

如有好文章投稿，请点击 → 这里了解详情

主页君小提示：图文有点长，慢慢看

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

题目：

有一座高度是 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中不存在，就计算出结果，存入备忘录中。

方法三：动态规划求解