DP - Top-Down 방식과 Bottom-up

# bottom-top 방식

'''
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])
'''
# TopDown 방식 Dfs사용
def dfs(n):

    if dp[n]>0:
        return dp[n]
    
    if n==1 or n==2:
        return n
    else:
        dp[n]=dfs(n-1)+dfs(n-2)


    return dp[n]


n=int(input())

dp=[0]*(n+1)

print(dfs(n))

말 그대로 Top-Down방식은 위에서부터 아래로 이동해가면서 최적의 해를 찾아가는방식이고

Bottom-up은 반대이다

다만, Top-Down은 보통 DFS를 많이사용하는것같다.주의하자