[LeetCode] 70. Climbing Stairs

문제 링크: https://leetcode.com/problems/climbing-stairs/submissions/

Climbing Stairs - LeetCode

코드

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

 

풀이

• 계단은 1칸, 2칸씩 오를 수 있으므로 2번 계단을 올라갈 때 까지의 경우의 수를 dp로 초기화해준다.
• 계단을 오르는 방법의 경우의 수의 합은, 한칸 두칸씩 오르는 경우의 수의 합이므로 현재 i 번째 계단에서 -1,-2번 계단의 경우의 수를 더한 값과 같다.