[김태원 알고리즘] 계단 오르기 (DP)

사용 언어: Python3

문제

풀이

Bottom-Up

N = int(input())
dp = [0] * (N+1)
dp[1] = 1
dp[2] = 2
for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]
    
print(dp[N])

Top-Down: 재귀, 메모이제이션

메모이제이션: 구해진 값들을 기록 해두고 cut edge를 통해 불필요한 재귀 호출을 방지한다.

def DFS(x):
    if dp[x] != 0:
        return dp[x]
    if x == 1 or x == 2:
        return x
    dp[x] = DFS(x-2) + DFS(x-1)
    return dp[x]

N = int(input())
dp = [0] * (N+1) # 메모이제이션을 위한 배열

print(DFS(N))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기