LeetCode ClimbingStairs

class Solution {

public:

    int climbStairs(int n) {

        if (n < 1) return 0;

        int a = 0;

        int b = 1;

        for (int i=0; i<n; i++) {

            int t = a + b;

            a = b;

            b = t;

        }

        return b;

    }    

};

発見leetcodeの上の問題の多くも剣指offerの中であって、この問題も、実際には1つのfab数列を計算して、1つのnに対して、1歩先に行ってもいいし、2歩先に行ってもいいので、前者はn-1の階段を残して、後者はn-2を残して、私たちがすでに求めた(n-1)と(n-2)の階段の時の種数を仮定して、この時f(n)=f(n-1)+f(n-2)