【剑指offer080 09 跳台阶、变态跳台阶】

题目描述

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

 

跳上n级台阶的跳法等于跳上n-1台阶的跳法+n-2台阶的跳法，斐波拉契数列 f(1)=1 f(2)=2

class Solution {
public:
/*
斐波拉契数列
跳到n的方法数 = 跳到n-1的方法数 + 跳到n-2的方法数
即f(n)=f(n-1)+f(n-2)
*/
    int jumpFloor(int number) {
        if(number<=0)return 0;
        if(number==1)return 1 ;
        if(number==2)return 2 ;
        int f1=1 , f2=2;
        int ans = 0 ;
        for(int i=3 ; i<=number ; ++i){
            ans = f1 + f2;
            f1 = f2 ; f2 = ans ;
        }
        return ans ;
    }
};

题目描述

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

 

可与跳上任意一阶，那么就是n前面所有台阶可能的和

即f(n)=1+f(n-1)+.....+f(1)

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0){return 0;}
        if(number==1){return 1;}
        if(number==2){return 2;}
        int f1 = 1 , f2 = 2;
        int sum_f = 3 ;
        int f = 0;
        for(int i = 3 ; i<=number ; ++i){
            f = sum_f + 1 ;
            sum_f = sum_f + f ;
        }
        return f ;
    }
};