LeetCode "Climbing Stairs"

The best way to learn DP from DFS! Nice problem.

My intuition is that it can be solved by DFS:

class Solution {
public:    
    int climbStairs(int n) {
        if (n == 0) return 1;
        int cnt0 = climbStairs(n - 1);
        int cnt1 = 0;
        if(n >= 2) cnt1 = climbStairs(n - 2);
        return cnt0 + cnt1;
    }
};

You can get correct answer by this, but it is taking too long - TLE.

Actually, the equation is quite obvious in above code: s[n] = s[n-1] + s[n-2] with s[1] = 1; s[2] = 2. Sooooo beautiful:

class Solution {
public:    
    int climbStairs(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;

        //    S[n] = S[n-1] + S[n-2]; S[1] = 1; S[2] = 2
        int ret = 0;
        int *s = new int[n + 1];
        s[1] = 1; s[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            s[i] = s[i - 1] + s[i - 2];
        }
        ret = s[n];
        delete[] s;
        return ret;
    }
};