24 lines
875 B
Python
24 lines
875 B
Python
# Climbing Stairs
|
|
|
|
class Solution:
|
|
def climbStairs(self, n: int) -> int:
|
|
dp = [0] * (n+1)
|
|
dp[0] = 1
|
|
dp[1] = 1
|
|
for i in range(2, n+1):
|
|
dp[i] = dp[i-1] + dp[i-2]
|
|
|
|
return dp[n]
|
|
|
|
|
|
|
|
"""
|
|
걸린 시간: 3분
|
|
|
|
복잡도: n+1 칸의 dp 리스트를 다 채우기 때문에 시간복잡도는 O(n)이다.
|
|
n+1짜리 dp 리스트를 만들기 때문에 공간복잡도는 O(n)이다.
|
|
|
|
해설: 계단을 오를 수 있는 방법이 여러가지 제시되어 있고, 목적지까지 가는 경우의 수를 묻는 것이기 때문에 dp로 풀 수 있다.
|
|
i번째 칸으로 도착할 수 있는 경우의 수가 i-1, i-2번째 칸에서 1칸, 2칸씩 오르는 경우밖에 없고, 이 두 경우의 수를 더하면 i번째 칸 경우의 수가 된다.
|
|
이렇게 하면 중복되는 경우 없이 셀 수 있다.
|
|
""" |