leetcode 刷題之路 92 Climbing Stairs

leetcode 刷題之路 92 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

一個台階總共有n級，如果一次可以跳1級，也可以跳2級，求總共有多少總跳法。

分析：

一次最多只能跳兩級，那麼對於第n級（n>=2）台階，顯然只能從第n-1級跳一級到達或者從第n-2級跳兩級到達，因此只要知道了n-1級和n-2級的跳法個數，求和就是第n級的跳法個數。

設跳法個數為f(n)，n為台階級數，則有：

f(n)=f(n-1)+f(n-2)，

當n=0,1時，f(n)=1

題目轉換成一個典型的Fibonacci序列問題。

Accepted Solution:

class Solution {
public:
    int climbStairs(int n) 
    {
        int first=1,second=1;
        for(int i=2;i<=n;i++)
        {
            int temp=second;
            second=first+second;
            first=temp;
        }
        return second;
    }
};