Climbing Stair

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

 

계단오르기문제(DP)

계단을 오르는 방법으로는 1칸 또는 2칸을 오를수 있는데 N의 파라미터는 총 계단수이면 반환으로 N의 계단을 오르기 위한 방법들의 수를 반환하는 식을 작성하라.

 

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = new Array(n + 1);
    dp[0] = 1, dp[1] = 1;
    for (let i = 2; i <= n; ++i){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

 

문제 설명

- 계단수가 1인 경우에 방법은  1 로 1가지

- 계단수가 2인 경우에 방법은  1+1 , 2 로 2가지

- 계단수가 3인 경우에 방법은  1+1+1, 2+1, 1+2로 3가지

- 계단수가 4인 경우에 방법은  1+1+1+1. 2+2. 1+2+1, 2+1+1, 1+1+2 로 5가지가 된다.

계속 계단수가 늘어날수록 식이 보이게 되는데 계단수 N = 계단수 N-1 + 계단수 N-2 가 되는걸 확인할 수 있었다.

그래서 DP(N) = DP(N-1) + DP(N-2)가 되는데 이 식을 함수안에 작성하여 문제를 풀어주면 된다.