[leetcode]41 Climbing Stairs

タイトルリンク:https://leetcode.com/problems/climbing-stairs/ Runtimes:2ms
1、問題
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?
2、分析
もしn階の階段があるならば、1歩歩くことを選択することができて、n-1階の階段を残して、2歩歩くことを選択することができて、n-2階の階段を残して、次にn-1を引き続き求める必要があって、n-2はどれだけの歩き方があって、明らかに再帰の事件で、再帰の公式はf(n)=f(n-1)+f(n-2)で、明らかに1つのフィボラッチのシーケンスで、非再帰の求め方で完成することができます.n=1,f(1)=1のとき;n=2,f(2)=2のとき;n=3,f(3)=3のとき;n=4,f(4)=5のとき;このように推す.
3、まとめ
再帰的に解決することはできず、スペースがかかりすぎて、計算した数値を繰り返し計算しやすい.
4、実現

class Solution {
public:
    int climbStairs(int n) {
        int i = 1, presum = 0, sum = 1;
        while(i <= n)
        {
            int temp = sum;
            sum += presum;
            presum = temp;
            ++i;
        }
        return sum;
    }
};

5、反省
簡単なテーマで、効果はいいです.