[Leetcode] Easy-Climbing Stairs

n번째까지 도달하는 경우의 수 구하기.
먼저, 몇가지 예시를 적어 input n에 따른 output이 나오는 규칙을 도출해보자.

• n = 2일 때,
  1) 1 + 1
  2) 2

• n = 3일 때,
  1) 1 + 1 + 1
  2) 1 + 2
  3) 2 + 1

• n = 4일 때,
  1) 1 + 1 + 1 + 1
  2) 1 + 1 + 2
  3) 1 + 2 + 1
  4) 2 + 1 + 1
  5) 2 + 2

• n = 5일 때,
  1) 1 + 1 + 1+ 1 + 1
  2) 1 + 1 + 1 + 2
  3) 1 + 1+ 2 + 1
  4) 1 + 2 + 1 + 1
  5) 2 + 1 + 1 + 1
  6) 1 + 2 + 2
  7) 2 + 1 + 2
  8) 2 + 2 + 1

경우의 수만 나열해보면
2 3 5 8 13 ···, n번째 순서의 점화식의 규칙은 n=(n-1)+(n-2)가 됨을 확인할 수 있다.

13 = 8 + 5
8 = 5 + 3
5 = 3 + 2

즉, 구하려는 값은 왼쪽의 두 값을 더하면 된다.

Dynamic Programming 이용

var climbStairs = function(n) {
    let dp = []
    dp[1] = 1;
    dp[2] = 2;

    for(let i = 3; i <= n; i++){
        // i = 3일 때 dp[3] = dp[2] + dp[1] => 3
        // i = 4일 때, dp[4] = dp[3] + dp[2] => 5
        // i = 5일 때, dp[5] = dp[4] + dp[3] => 8
        // i = 6일 때, dp[6] = 8 + 5 => 13
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[n]
};

• n이 1일 때와 2일 때, 경우의 수를 할당해주고 index = 3부터 시작한다.
• n번째 점화식울 구하려면 이전 값들을 저장해놓고, n번째의 (n-1)번째가 되는 값과 (n-2)번째가 되는 값을 더해야한다.
• index = 3부터 시작하기 위한 조건은, index=2일 때와 index = 1일때의 값을 할당하는 것이다. 이는 dp[i-1] + dp[i-2] 의 값을 알아야만 결과가 산출되기 때문이다.

Dynamic Programming?