•
•
문제 설명 : 언덕의 높이가 주어지며, 각 걸음마다 1 혹은 2만큼만 올라갈 수 있을 때 조합이 가능한 스텝의 종류는 몇가지인지 반환한다.
•
풀이 방법
◦
우선 문제 조건이 1 <= n <= 45 이고, n을 4나 5까지 확장해보니 피보나치 수열과 완전히 일치하는 문제였다.
◦
그래서 별도의 리스트에 이전 언덕 높이의 결과를 저장하고, 이를 재사용하는 기본적인 DP의 방식을 사용하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
climb = [0] * 46
climb[0], climb[1] = 1, 1
def climbStairs(self, n: int) -> int:
if n <= 1:
return self.climb[n]
for i in range(2, n + 1):
self.climb[i] = self.climb[i - 1] + self.climb[i - 2]
return self.climb[n]
Python
복사