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

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]



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

    print(DFS(n))

• Top-Down 방식은 재귀와 메모이제이션 방식을 사용해서 진행한다.
• 재귀는 말그대로 본인을 호출하는 것을 의미하고 메모이제이션은 해당 재귀가 한 번이라도 호출되었다면 어딘가에 메모해두고 이를 다시 사용하지 않는 방식을 의미한다.
• 위의 코드에서 if dp[n] > 0: 이 한 번 호출되었던 경우를 의미한다.