leetcode 70. climbing stairs(dp 푸는법)

문제: https://leetcode.com/problems/climbing-stairs/description/
동적할당을 이용한 문제이다.
이문제가 동적할당인것만 알았어도 접근하기는 어렵지 않았을것이다.

동적할당문제를 푸는법은 간단하다
1~8번까지 노가다로 값을 구해본다.
n=1 > 1 ==> 1개
n=2 > 1+1 2 ==> 2개
n=3 > 1+1+1 1+2 2+1 ==> 3개
n=4 > 1+1+1+1 2+1+1 1+2+1 1+1+2 2+2 ==> 5개
n=5 > 1+1+1+1+1 2+1+1+1 1+2+1+1 1+1+2+1 1+1+1+2 2+2+1 2+1+2 1+2+2 ==> 8개
|
|
|
즉 갯수는 1,2,3,5,8 이렇게 늘어난다.
여기서 규칙을 찾으면
n의 갯수는 n-1과 n-2의 합과 같다.

우선 n번까지 수행하게 될때 그 이전의 값들을 저장할 공간이 필요하기 때문에
배열을 통해 저장할 공간을 만들어준다.

    let stairs = new Array(n).fill(0)
    ```
    그 뒤에 위에 공식을 적용하면 답은 아래와 같다. 
답
```js
var climbStairs = function(n) {
    let stairs = new Array(n).fill(0);
    stairs[1] = 1;
    stairs[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        stairs[i] = stairs[i - 2] + stairs[i - 1];
    }
    
    return stairs[n];
};

참고자료

동적계획법 과 점화식

알고리즘 - Dynamic Programming(동적프로그래밍)이란?