[Algorithms] 동적 계획법(Dynamic Programming)-네트워크 선 자르기(Bottom up) / (Top Down) 2가지 방식

 

1. Bottom Up 방식으로 풀이

가장 작은 부분 부터 직관적으로 풀어보자. 이 후 점화식을 이용하여 점차 큰 문제를 풀어나간다.

import sys
 
sys.stdin=open('input', 'r')
n = int(input())
arr = [0] * (n+1)
arr[1]=1
arr[2]=2
 
for i in range(3, n+1):
    arr[i] = arr[i-1] + arr[i-2]
print(arr[n])
 

def DFS(len):
    if memo[len] > 0:
        return memo[len]
    if len == 1 or len == 2:
        return len
    else:
        memo[len] = DFS(len-1) + DFS(len-2)
        return memo[len]
 
if __name__=='__main__':
    n = int(input())
    memo = [0] * (n+1)
    print(DFS(n))