[C++] DP - 네트워크 선 자르기(Top-Down)

Top Down방식은 재귀적으로 동작한다.

#include <iostream>

int dy[101];//다이나믹 배열 메모이제이션

#include <iostream>

using namespace std;

int DFS(int n){
    if(dy[n] != 0) return dy[n]; //메모이제이션
    if(n == 1 || n == 2) return n; //dfs(1)은 한가지 dfs(2)는 두가지
    else return dy[n] = DFS(n-1) + DFS(n-2);
}

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    cout << DFS(n);
    return 0;
}

• 이 문제는 이 전 문제와 동일한 네트워크 선 자르기이다.
• Bottom Up은 직관적으로  알 수 있을 정도로 문제를 작은 단위로 바꾸어 점점 큰 문제의 답을 구했지만
• Top Down은 원하는 큰 문제부터 시작하여 재귀적으로 동작함으로써 점점 작은 문제로 줄여나가는 방식이다.
• 하지만 Top Down도 결국 네트워크선이 1m이거나 2m일 때에는 답이 1, 2라는 것(작은 문제의 해)를 미리 정해놓고 점화식도 이에 따라서 결정하기 때문에 Bottom- Up과 성질이  크게 다르지 않다.
• 따라서, 코드를 재귀적으로 짜느냐, 아니냐의 차이이다. 개인적으로 점화식을 짠다는 측면에서 Top-Down이 훨씬 코드가 보기 좋은 것 같다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard