设为首页 加入收藏

TOP

青蛙跳台阶
2016-05-01 02:25:02 来源: 作者: 【 】 浏览:180
Tags:蛙跳 台阶

题目描述

一只青蛙一次可以跳上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)并返回。

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇指针和数组的掌握以及内存的管理 下一篇hdu 5671 Matrix(BC――思维题)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目