Climbing Stairs

// O(n) time, O(1) space
class Solution {
public:
    int climbStairs(int n) {
        // there are two ways to rean n, either from f(n-1) + 1, or from f(n-2)+2
        // f(n) = f(n-1) + f(n-2)
        // base case: f(1)=1, f(2)=2 
        if (n == 1) return 1;
        if (n == 2) return 2;

        int pp = 1;
        int prev = 2;
        int fn = 0;
        for (int i = 3; i <= n; ++i) {
            fn = pp + prev;
            pp = prev;
            prev = fn;
        }

        return fn;

    }
};