[C++]LeetCode: 52 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?
構想解析:
すぐにFibonacci numberだと判断できず、問題の分析を開始した.
the number of solutions for N steps stair(S[N])は、2つの部分から構成され、S[N-1]&&S[N-2]は、残りの1ステップまたは2ステップで1回で完了することができる(テーマ要件).S[N]=S[N−1]+S[N−2]がある.フィボナッチ数列を連想します
数学的には、フィボナッチ数列は再帰的な方法で定義されています.


(n≧2)
文字で言えば、フィボナッチ数列は0と1から始まり、その後のフィボナッチ係数は前の2つの数で加算されます.最初のいくつかのフェボナッチ係数は(†A 000045):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
複雑度:O(N)
Attention:
1.ループの回数に注意し、N-2回;stepOneとstepTwoの初期値もあります.
2.アルゴリズムのすばらしさは、数列のすべての値をコンテナvectorで保存するのではなく、2つの変数のみを使用して前の2つの値を保存するため、空間複雑度が定数である.
            ret = stepOne + stepTwo;    //S[N] = S[N-1] + S[N-2]             stepTwo = stepOne;          //S[N-1]_new = S[N-2]_old             stepOne = ret;              //S[N-2]_new = S[N]_old
AC Code:

class Solution {
public:
    int climbStairs(int n) {
        if(n == 0 || n == 1) return 1;
        //Fibonacci number    
        int stepOne = 1, stepTwo = 1;
        int ret = 0;
        
        //Fibonacci number S[N] = S[N-1] + S[N-2]. stepOne  S[N-1], stepTwo  S[N-2],  0   。  N-2 。
        for(int i = 2; i <= n; i++)
        {
            ret = stepOne + stepTwo;    //S[N] = S[N-1] + S[N-2]
            stepTwo = stepOne;          //S[N-1]_new = S[N-2]_old
            stepOne = ret;              //S[N-2]_new = S[N]_old
        }
        
        return ret;
    }
};