동적계획법 공부하다가 헷갈려서 질문드려요. 피보나치를 예로 들면 메모이제이션(재귀에 캐시 붙이는 top-down 방식)이랑 타뷸레이션(반복문으로 표 채우는 bottom-up 방식) 두 개가 다 나오는데요.
top-down은 이렇게 짜잖아요.
memo = {}
def fib(n):
if n < 2: return n
if n in memo: return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
bottom-up은 이렇게요.
def fib(n):
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
둘 다 시간복잡도는 O(n)으로 똑같은 걸로 아는데, 실무나 코테에서 뭘 기준으로 고르는지 궁금해요. 그냥 취향 차이인가요 아니면 상황마다 유불리가 있나요?