leetcode筆記：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階樓梯共有幾種爬法-_-||。題目可以看成是，設

f(n)

表示爬到第

n

階樓梯的方法數，為了爬到第n階樓梯，有以下兩種選擇：

• 從第

f(n-1)

階前進

1

步；

• 從第

f(n-2)

階前進

2

步；

則

f(n)

可寫成：

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

題目轉化為斐波那契數列的問題，關于這一内容，網上相關研究有很多，概念傳送門：

http://baike.baidu.com/link?url=c2Bmk2jBGbI46qTIA-qKmdTkYBrVYYrejAHzf8BJRwCekIL4Sbx48fFCRkeGdul0

二.題目分析

關于斐波那契序列，可以使用遞歸或者疊代來解決問題，該書列可寫成以下遞推關系：

顯然，使用遞推關系式反複疊代并不是最優的解法，在計算f(n)值時，需要計算f(1),f(2),…,f(n-1)的所有值，其中存在很多重複的運算，如計算f(4)=f(3)+f(2)，其中需要求解f(3)=f(2)+f(1)。若使用一個數組用于儲存所有計算過的項，可以把時間複雜度降至O(n)，而空間複雜度也為O(n)。

這裡為了追求時間複雜度，是以直接使用斐波那契的通項公式，該公式的推導過程如下：

三.示例代碼

#include <iostream>
using namespace std;

class Solution
{
public:
    // 時間複雜度O(1)
    int climbStairs1(const int n)
    {
        const double sqrtNum = sqrt();
        return int(floor((pow(( + sqrtNum) / , n + ) - pow(( - sqrtNum) / , n + )) / sqrtNum));
    }

    // 時間複雜度O(n)
    int climbStairs2(const int n)
    {
        int current = ;
        int last = ;
        for (int i = ; i <= n; i++)
        {
            int temp = current;
            current += last;
            last = temp;
        }
        return current;
    }
};
           

簡單的測試代碼：

#include "ClimbingStairs.h"
#include <iostream>

int main()
{
    int n;
    cout << "How many stairs? " << "Input: ";
    cin >> n;
    Solution s;
    int result1 = s.climbStairs1(n);
    int result2 = s.climbStairs2(n);

    cout << "How many ways to reach the finish line? " "Result1：" << result1 << endl;
    cout << "How many ways to reach the finish line? " "Result2：" << result2 << endl;
    system("pause");
    return ;
}
           

四.小結

其實使用通項公式也存在漏洞，因為通項公式使用浮點運算，還出現了實體書，是以不能保證結果的精度。而在《程式設計之美》一書中，還給出一種分治政策的解決方法。該算法可做到時間複雜度O(Log2n)，而網上更有博文寫出了七種解斐波那契序列的方法，還要繼續深入研究啊。