跳台阶递归与迭代方法

63 阅读 0 评论 42 点赞

我是靠谱客的博主暴躁未来，这篇文章主要介绍跳台阶递归与迭代方法，现在分享给大家，希望可以做个参考。

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

public class Solution {
    public int JumpFloor(int target) {
        if(target==0||target==1||target==2)
            return target;
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

迭代，效率更高，没有重复计算

public class Solution {
    public int JumpFloor(int target) {
        if(target==0||target==1||target==2)
            return target;
        int pre =1; //前两个台阶跳法总数
        int later=2; //前一个台阶跳法总数 
        for(int i=3;i<=target;i++){
            int temp=pre+later;//当前台阶跳法总数
            pre=later
            later=temp;        
        }
        return temp;
    }
}