Part7.3動的プログラミングの課題

import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
dy = [0]*(n+1)
dy[1] = 1
dy[2] = 1

for i in range(3, n+1):
    dy[i] = dy[i-1] + dy[i-2]
print(dy[n])

import sys
sys.stdin = open("input.txt", "rt")

def DFS(len):
    if dy[len] > 0:
        return dy[len]
# 가지를 cut 하는 방법
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        #dy[7] = D(6) + D(5)
        return dy[len]


if __name__=="__main__":
    n = int(input())
    dy=[0]*(n+1)
    print(DFS(n))