递归与动态规划---基础篇1

ps:最近几天正在刷一些有关动态规划的题，我会把自己学习时的想法以及做题的想法记录下来。（小白第一次写作，希望大家多多支持）

题目1：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

对于这道题，我第一眼看到的想法是用递归的做法的，用递归的方法做题，我觉得最重要的就是找出 这个函数与下一个函数之间的关系 以及 一个函数体结束的临界条件（即递归的结束）。

例如就本题而言,

1.第一步先找这个函数与下一个函数之间的关系：

假如有n个台阶，跳上一个n级的台阶的跳法总数为f(n).

我们在跳的过程中，每一次有两种跳法，即跳一个或两个台阶。

第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。

或者用

第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。

由此不难得出递归公式：f(n) = (n-1) + f(n-2);

2.第二步，找出递归的结束条件

当n <= 0时，跳法为0，即此时f(n) = 0

当只剩下一个台阶n = 1时，那么只有一种跳法，即f(1) = 1;

当n = 2时，此时跳法为2种，即f(2) = 2;

函数与函数之间的关系以及递归的临界条件都找出来了，那么接下来就可以开始写代码了。如下所示：

不过观察一下你就会发现，其实在递归的过程中，有很多相同的)f(n)重复算。

如下图：

算一下你就知道，时间复杂度是指数级别的。如果是比赛这样做的话，绝对超时不通过

因此对于那些重复算过的，其实我们可以不用在重复递归来算它的，也就是所我们可以把f(n)算的结果一边给保存起来，这种就是动态规划的思想。

也就是说，我们可以把每次计算的结果保存中一个map容器里，把n作为key,f(n)作为value.然后每次要递归的时候，先查看一下这个f(n)我们是否已经算过了，如果已经算过了，我们直接从map容器里取出来返回去就可以了。如下：

这种方法会快很多很多。

实际上，对于f(n) = f(n-1) + f(n - 2)这种有递推关系的题，其实和斐波那契数列很相似，还可以这样做：

问题2： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析，其实这道题和上面那道题一样的，只是本来每次跳有两种选择，现在有n中选择，即f(n) = f(n-1) + f(n - 2) + f(n-3)+.....+f(1);

因此做法如下：

如果你有其他想法，或者更完美的做法，欢迎指点江山。