[LeetCode easy] Climbing Stairs (JavaScript)

https://leetcode.com/problems/climbing-stairs/

문제 설명

한번에 1칸 또는 2칸씩 계단을 오를 수 있다. 숫자 n이 주어졌을 때 n까지 가는 다른 방법들의 개수는 몇 개인가?

예를 들어
ex1) n = 2 일 경우 1칸 1칸 올라가는 방법 1개와 2칸 올라가는 방법 1개로 답이 2이다.
ex2) n = 3 일 경우 1칸 + 1칸 + 1칸, 1칸 + 2칸, 2칸 + 1칸 으로 답은 3이다.

문제 풀이

해당 문제는 dynamic programming으로 풀 수 있다.

dp문제는 점화식을 잘 세워야 한다. 해당 문제의 점화식은
dp[n] = dp[n-1] + dp[n-2] 이다.
즉, n칸은 n-1칸일 때의 값 + n-2칸일 때의 값이 된다.
n-1 칸의 값은 n-1칸까지 한번도 겹치지 않은 수 이고 n-2칸의 값도 n-2칸까지 한번도 겹치지 않은 수 이기 때문에 각각 1칸, 2칸을 갔다고 생각하면 n칸의 값을 구할 수 있다.

var climbStairs = function(n) {
    let dp = new Array(n+1).fill(0);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};