네트워크 선자르기 (Bottom-Up, Top-Down)

bottom up

"""
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.

예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m

네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법?
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
"""
# Bottom-Up
n=int(input())
d=[0]*(n+1)
d[1]=1
d[2]=2

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

 

top down

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

def dfs(len):
    if d[len]>0:
        return d[len]

    if len==1 or len==2:
        return len
    else:
        d[len]=dfs(len-1)+dfs(len-2)
        return d[len]

print(dfs(n))