【剑指offer】一，跳台阶（java实现）

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。   分析：此题为典型的递归问题，递归问题的典型解法就是找到递推公式和边界条件。青蛙跳上第N阶前可能在第N-1，N-2 阶得到递推公式f(n)=f(n-1)+f(n-2)。考虑边界条件当n为1时，有1种方法。当N为2时有两种方法。代码如下： 1 public class Solution { 2 public int JumpFloor(int target) { 3 if(target<3){ 4 return target ; 5 } 6 else return f(n-1)+f(n-2) ;

 

14 } 15 }考虑时间效率，采用动态规划进行优化 public class Solution { public int JumpFloor(int target) { if(target<3){ return target ; } int temp1 = 1 ,temp2 = 2 ; int res=0 ; for(int i = 3 ;i <= target ;i++){ res = temp1+temp2 ; temp1 = temp2 ; temp2 = res ; } return res ; } }

写这个系列主要时因为最近找工作在刷算法。把自己的结果分享出来给大家，也方便自己以后温习。

 

转载于:https://www.cnblogs.com/huntertoung/p/4753423.html