[LeetCode] DP, DFS - 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?

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

 

Constraints:

• 1 <= n <= 45

코드

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const memo = new Map();
    const method = (num) => {
        if(!num) return 0;
        if(num === 1) return 1;
        if(num === 2) return 2;
        if(memo.has(num)) return memo.get(num)
        let result = method(num - 1) + method(num - 2);
        memo.set(num, result);
        return result;
    }

    return method(n);
};