[leetcode] Climbing Stairs

Climbing Stairs

나의 풀이

백준에서 1,2,3 더하기라는 비슷한 문제를 풀어본 적이 있다. 일단 규칙을 모를 때는 그려본다.

노란색 부분은 +1, 분홍색 부분은 +2가 된 것이다. 3을 예로 들면, 3은 2+1인데 2가 되는 방법의 개수는 DP[2]에 저장되어있고, 끝이 2가 되는 1+2에서는 1이 되는 방법의 개수는 DP[1]에 저장되어 있다.

코드

class Solution:
    def climbStairs(self, n: int) -> int:
        DP = [0] * (46)
        DP[1] = 1
        DP[2] = 2
        
        for index in range(3, n+1):
            DP[index] = DP[index-1] + DP[index-2]
        
        return DP[n]

처음에 제출했을 때 틀렸던 이유는 n = 1인 경우에 대한 처리가 잘못되었기 때문이다. DP = [0] * (size+1)로 하면 DP[2]는 없기 때문에 에러가 뜬다. 사이즈를 크게 만들어두자.