리트코드-70. Climbing Stairs

문제

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

풀이

주어진 조건에서 n 계단을 올리가기 위한 모든 방법을 계산하는 문제이다. 전형적인 DP 알고리즘 적용 문제로 인덱스 0, 1, 2을 제외하고서는 dp[n] =dp[n-1] + dp[n-2] 식을 적용하면 쉽게 풀린다.

• 인덱스 0, 1, 2를 제외하는 이유는 1계단, 2계단씩 오를 수 있기 때문에 위의 식에서 +1씩 방법이 늘어나기 때문이다.
• DP는 상향식과 하향식이 있는데 해당 문제는 하향식으로 푸는 것이 더 빠른 결과를 가져온다.
• 하지만 상향식이 더 간단하기 때문에, 상향식을 사용해 풀었다.

코드

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0, 1, 2]
        for i in range(3,n+1):
            dp.append(dp[i-1] + dp[i-2])
        return dp[n]