[名企面试知识点][Java]跳台阶
发布于 2017-03-06 15:13 1150 次浏览 0 赞 来自 笔试面试  

题目描述

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

输入描述

台阶级数 target

输出描述

多少种跳法

题目分析

  

  • 假设跳上n阶台阶时有f(n)种跳法 

  • 要跳上n阶只能从n-1阶或是n-2阶跳上去 

  • 那么有f(n)=f(n-1)+f(n-2)成立,这符合斐波那契数列

  • 显然n=1时 f(1)=1,n=2时f(2)=2,n=3时f(3)=f(1)+f(2)=3, 我们得出递推公式:      | 1, (n=1) f(n) =   | 2, (n=2)      | f(n-1)+f(n-2) ,(n>2,n为整数)

解法一(递归)  运行时间:444ms 占用内存:629k

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

注意输入限制,在上一题中说到了递归调用效率不高, 不推荐

解法二 (动态规划) 运行时间:33ms 占用内存:654k

public class Solution {
   public int JumpFloor(int target) {
       if(target<=0)  return 0;
       if(target<=2)  return target;

       int i =1;
       int j =2;
       for(;target>2;target--){
           j+=i;
           i=j-i;
       }
       return j;
   }
}

  首先,可以明显看出运行时间只有递归的十分之一不到。n=1时 f(1)=1,n=2时f(2)=2直接返回.   根据n的大小,从f(1)=i 和 f(2)=j 从头开始遍历整个序列,由f(n)=f(n-1)+f(n-2) (n>2),依次求得后面的结果,最后求得f(target)并返回。


添加回复
回到顶部