A child is running up a staircase withnsteps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Have you met this question in a real interview?

Yes

Example

n=3
1+1+1=2+1=1+2=3=3

return4

class Solution {
public:
    /**
     * @param n an integer
     * @return an integer
     */
    int climbStairs2(int n) {
        // Write your code here
        int f[3];
        f[0] = 1; f[1] = 1; f[2] = 2;
        for (int i = 3; i <= n; ++i) {
            f[i % 3] = f[(i - 3) % 3] + f[(i - 2) % 3] + f[(i - 1) % 3];
        }
        return f[n % 3];
    }
};