70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution {
    int dp[46] = {0,};
public:
    int climbStairs(int n) {
        return n <= 2 ? n : dp[n] ? dp[n] : dp[n] = climbStairs(n-2) + climbStairs(n-1);
    }
};