Leetcode에서 Climbing Stairs 문제 풀어보기

문제 링크

bookmark

다이나믹 프로그래밍(DP)이란?

• 하나의 problem은 단 한번만 푸는 알고리즘
• 즉, 한번 결과값이 나왔던것은 다시 한번 재연산을 하는것이 아니라 기억을 해놨다가 사용하는 것 (memoization)
• 대표적으로 피보나치 수열 점화식이 있음 ( D[i] = D[i-1] + D[i-2] )

소스 코드

function climbStairs(n: number): number {
    if(n === 1) return 1;
    if(n === 2) return 2;
    
    const stairs = new Array(n+1).fill(0);
    stairs[1] = 1;
    stairs[2] = 2;
    
    for(let i=3; i<stairs.length;i+=1) {
        stairs[i] = stairs[i-1] + stairs[i-2];
    }
    
    return stairs[n];
};

각 계단의 경우의 수를 살펴보면 다음과 같다

1개 → 1

2개 → 2

3개 → 3

4개 → 5

5개 → 8

즉 피보나치 수열과 맞물린다

0 1 1 2 3 5 8 13 ......

때문에 피보나치 수열의 점화식인 D[i] = D[i-1] + D[i-2] 을 이용하여 푼다

• 맨앞에 n이 0인경우를 포함하기 위해 n+1 개의 배열을 0으로 가득채워 초기화한다
• n이 1인경우와 2인경우에는 각각의 경우의 수에 맞게 return 해준다
• stairs의 3번인덱스부터 순회하여 각 n별로 경우의 수를 구한다
• 그 값을 리턴한다