剑指offer_【8】跳台阶

1.题目描述

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

2.解题思路

1. 把n级台阶的跳的次数看成是n的函数,即为f(n),当n>2时,第一次跳有两种跳法,

   第一次跳1级,则该次跳法数目为后面剩下的n-1级台阶的跳法数目f(n-1)。

   第一次跳2级,则该次跳法数目为后面剩下的n-2级台阶的跳法数目f(n-2)。

   所以f(n)=f(n-1)+f(n-2),即相当于斐波那契数列。`

即该题跟斐波那契数列是相似的，青蛙跳台阶的公式为

F(n) = F(n-1)+F(n-2),n>=3

3.代码

public class Solution {
    public int JumpFloor(int target) {
        if(target<=2)
        {
            return target;
        }
        int one_=1; //第一次跳台阶的方法数

        int two_=2; //第二次跳台阶的方法数

        int finN=0;
        for(int i=3;i<=target;i++)
        {
            finN=one_+two_;
            one_=two_;
            two_=finN;
        }
        return finN;
    }
}