青蛙跳台阶--尾递归优化

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
才开始感觉有点懵，就看一下规律，当台阶只有一级台阶，f(1)=1，当台阶有2级，f(2)=2，当台阶有3级，f(3) = 3,f(4) = 5,依次类推，发现是个斐波拉切数列。那么，为什么会是这样呢？
假设要跳到6，有两种，一种是从5跳到5，这个时候，跳到6的方式就是f(5)，另一种是从4跳到6,方法数就是f(4).所以f(6) = f(5) + f(4)，正好是斐波拉切数列。

而传统的斐波拉切数列是0，1，1，2，3，5，8…….按照题意，本题中的数列是0，1，2，3，5，8…，就是0级的时候是0，1级的时候有一种，2级的时候有2中，依次类推。所以，在前面我先判断一下，0级和1级的时候，都返回1，就能通过，而我用的方式是尾递归。具体请见我领一篇博客这里写链接内容

public class Solution {
public int JumpFloor(int target) {
if(target == 0 || target == 1){
return 1;
}else{
return
Fob(target,0, 1);
}
}
private int Fob(int n,int a, int b){
if( n == 0){
return
b;
}else{
return Fob(n - 1,b,a+b);
}
}
}

最后

以上就是怕孤独冬瓜为你收集整理的青蛙跳台阶--尾递归优化的全部内容，希望文章能够帮你解决青蛙跳台阶--尾递归优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。