[동적 계획법][Bottom-Up] - 네트워크 선 자르기

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

dp[1] = 1
dp[2] = 2

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

• 가장 작은 해를 구해 그 해를 이용해서 점차 다른 큰 해를 구하는 점화식을 Bottom-up 방식이라 한다.
• DP의 경우 기준점이되는 부분을 잘 찾아서 이를 이용하면 문제를 쉽게 해결할 수 있다.
• Bottom-Up 방식이 동적계획법이고 Top-Down 방식은 넓은 의미의 동적 계획법이다.