青蛙跳台阶

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路：

我们先考虑青蛙第一跳：

• 第一次跳1个台阶，那么还剩n-1个台阶，跳法为f(n-1)
• 第一次跳2个台阶，那么还剩n-2个台阶，跳法为f(n-2)

所以总的跳法:f(n)=f(n-1)+f(n-2)

• 当跳到只剩1个台阶时，有1种跳法：f(1)=1
• 当跳到只剩2个台阶时，有2种跳法：f(2)=2

观察发现，这就是一个斐波那契数列

image

我的代码：

public int JumpFloor(int target) {//target为台阶总数
        if(target==2){
            return 2;
        }
        if(target==1){
           return 1;
        }
        if(target<=0){
            return 0;
        }
        return JumpFloor(target-1)+JumpFloor(target-2);
    }

运行时间：544ms

占用内存：9056 k

改进：

为避免递归产生的栈溢出，改用自底向上的动态规划（迭代）来解题：

 public int JumpFloor(int target) {
       if(target==2){
            return 2;
        }
        if(target==1){
           return 1;
        }
        if(target<=0){
            return 0;
        }
        int first = 1, second = 2, third = 0;
        for (int i = 3; i <= target; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

运行时间：15ms

占用内存：9328 k