青蛙跳台阶的非递归和递归做法

一.问题：

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

二.递归做法:

核心关键：1>找底层逻辑值；2>找限制条件；3>简化

1.由图可以看出：剩n个台阶时我们有fib(n)种跳法

2.我们从起步开始分析：

--刚开始起步跳有两种跳法-->跳一个台阶and跳两个台阶

3.当选择初始跳一个台阶时我们会发现：剩n-1个台阶，也就是fib(n-1)种跳法

4.当选择初始跳两个台阶时：剩n-2个台阶，也就是fib(n-2)跳法

*5.底层逻辑：

-->n = 1时有一种跳法：一次跳一个-->fib(1) = 1;

-->n = 2时有两种跳法：一次跳一个跳两次一个and一次跳两个-->fib(2) = 2;

6.简化问题：找出两种跳法后相加即是总跳法数：fib(n) = fib(n-1) + fib(n-2);

代码以及效果图：

二.非递归做法：

核心关键：-->找规律

1.

2.可以看出：1+2 = 3；2+3 = 5；3+5 = 8；

*3.即从第三级台阶开始，前两数相加等于后面数，前两节依旧特殊情况

代码以及效果图：

三.总结

递归方法：一定要找到底层值，找到底层逻辑相当于知道了限制条件，再分化简化

非递归方法：一定要找规律，找不到规律很难想到

四.完结撒花

希望对你解决这道题有帮助，加油！