어제 풀었던 피보나치 수열 문제랑 똑같은 풀이로 풀 수 있다!
상향식 풀이 -> 재귀 X
class Solution:
from collections import defaultdict
dp = defaultdict(int)
def climbStairs(self, n: int) -> int:
self.dp[1] = 1
self.dp[2] = 2
for i in range(3, n+1):
self.dp[i] = self.dp[i-1] + self.dp[i-2]
return self.dp[n]
재귀
class Solution:
# 타뷸레이션? 상향식 풀이
from collections import defaultdict
dp = defaultdict(int)
def climbStairs(self, n: int) -> int:
if n < 3:
return n
if self.dp[n]:
return self.dp[n]
self.dp[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return self.dp[n]
defaltdict 호출할 때 default 값 type을 빼먹지 말라.
defaultdict(int)
class Solution:
# 타뷸레이션? 상향식 풀이
def climbStairs(self, n: int) -> int:
x, y = 1, 2
for _ in range(n-1):
x, y = y, x + y
return x