【递归】青蛙跳台阶的变式题你还会吗？

问题1：

如果青蛙一次只能跳一级或两级台阶，问跳到第N级台阶总共有多少方法？

解题：

跳上一级台阶，青蛙共有一种方法；0-->1，总共一种方法。

跳上两级台阶，青蛙可以一级一级跳，跳两次0-->1-->2，也可以直接跳到二级台阶,跳一次，0--->2；总共2种方法。

跳上三级台阶，青蛙可以青蛙可以一级一级跳，跳两次，0-->1-->2-->3,也可以先跳一级，然后再跳三级台阶，跳两次，0-->1--->3;也可以先跳两级，再跳一级台阶，跳两次，0-->2-->3;总共三种方法。

对于跳上三级台阶我们还可以从他跳上第三级台阶的最后一步来考虑（因为最后一步不一样，所以方法肯定不会重复），就是跳上三级台阶的方法数=跳上倒数第一级台阶的方法数+跳上倒数第二级台阶的方法数,这

那么我们便找到了普遍规律：

跳上N级台阶，得到递推公式f(n)=f(n-1）+f(n-2)

递推出口就是f(1)=1&&f(2)==2

这和斐波那契数列的结论很像，但是思考的过程却大相径庭！

代码：

#include<stdio.h>
int fabo(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n > 2) return fabo(n - 1) +fabo(n-2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret=fabo(n);
	printf("%d", ret);
}

结果：

看到这里我相信会了青蛙一次跳一级，两级台阶，但是稍微变一下，如果是青蛙可以一次跳一级，两级，三级台阶的问题，你是不是还会呐？

问题2：

如果青蛙一次可以跳1级，或2级，......或N级台阶，问青蛙要想跳到第N级台阶总共有多少种方法？

解题：

同样从他跳上第三级台阶的最后一步来考虑（因为最后一步不一样，所以方法肯定不会重复）

最后一步青蛙可以从倒数第一级，倒数第二......第二级，第一级台阶跳上去

因此得到公式f(n)=f(n-1)+f(n-2)+f(n-3)+....+f(2)+f(1);

同时f(n-1)=f(n-2）+f(n-3）+.....+f(2)+f（1）；

得到递推公式f(n)=2*f(n-1);

代码：

#include<stdio.h>
int fabo(int n)
{
	if (n == 1) return 1;
	if (n >= 2) return fabo(n - 1) * 2;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret=fabo(n);
	printf("%d", ret);
}

结果：

 问题3:

如果青蛙一次可以跳1级，或2级......或M级台阶，问青蛙要想跳到第N级台阶总共有多少种方法？（青蛙不能回跳）

解题：（分情况讨论）

1.当M>=N,因为青蛙不能回跳，所以此时问题等同于问题2；

2.当M<N,f(n)=f(n-1)+f(n-2)+f(n-3)+....+f(n-m)

同时f(n-1)=f(n-2)+f(n-3）+....+f(n-m)+f(n-m-1);

变换一下就是f(n-1)-f(n-m-1)=f(n-2)+f(n-3）+....+f(n-m)

因此得到递推公式：f(n)=2*f(n-1)-f(n-m-1)

代码同理可以写出来，自己动手试试吧！