[名企面试知识点][Java]变态跳台阶
发布于 2017-03-09 09:02 1427 次浏览 0 赞 来自 笔试面试  

题目描述

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

输入描述

台阶数

输出描述

跳法数

题目分析

  • 设n阶的跳数为f(n)

  • 当n=1时,f(1) = 1

  • 当n=2时,分为最后一步 跳2阶和跳1阶 两种情况,有f(2)=f(0)+f(1)=1+1=2

  • 当n=3时,分为最后一步 跳3阶、跳2阶和跳1阶 三种情况,有f(3)=f(0)+f(1)+f(2)=1+1+2=4

  • 有    f(n) = f(n-1)+f(n-2)+...+f(1) + f(0)成立 同时有 f(n-1)=f(n-2)+...+f(1) + f(0) 成立,可得出f(n)=2f(n-1) (n>=2)

 

很明显可以得出递推公式:

     | 1     (n=0 ) f(n) =   | 1      (n=1 )      | 2*f(n-1)  (n>=2)

解法一  运行时间:35ms   占用内存:654k

public class Solution {
   public int JumpFloorII(int target) {
       if(target<=1)  return 1;
       return 2*JumpFloorII(target-1);
   }
}

解法二  运行时间:34ms  占用内存:654k

public class Solution {
   public int JumpFloorII(int target) {
     if(target<=1)  return 1;
       return 1<<(target-1);
   }
}

  换一种思路想一下:一共有n个台阶,最后一个台阶是一定要跳上去的,其他的 n-1个可跳可不跳,一共有多少总情况?

  

2(n-1)

这里用移位实现乘法,时间上要快一些!


添加回复
回到顶部