[LeetCode][Python3] 70. Climbing Stairs

Problem :

https://leetcode.com/problems/climbing-stairs/solution/

My Solution :

class Solution:

def climbStairs(self, n):

"""

:type n: int

:rtype: int

"""

a, b = 1, 2

for _ in range(1, n):

a, b = b, a + b

return a

Comment :

가장 전형적인 동적 프로그래밍 문제이다. 이 문제의 경우 피보나치 수열과 동일한 형태이다. 접근 방법은 아래와 같다.

n번째 계단에 도착하는 경우는 다음 2가지 밖에 없다. n-1번째 계단에서 1칸 올라온 경우와 n-2번째 계단에서 한번에 2칸 올라온 경우. 따라서 2가지 경우를 더하면 된다. 이는 f(n) = f(n-1) + f(n-2) 형태의 피보나치 수열과 같다.

문제를 변형해서 한번에 오를 수 있는 계단이 1,2,3이라면 마찬가지로 f(n) = f(n-1) + f(n-2) + f(n-3) 으로 구하면 된다.

예전에 HackerRank에서 풀었던 문제

2018/07/21 - [프로그래밍] - [HackerRank][Python3] Recursion: Davis' Staircase