Dynamic Programming

• 동적 계획법
  - Top-down
  1. 문제를 작은 문제로 나눈다.
  2. 작은 문제를 푼다.
  3. 작은 문제를 풀고, 문제를 푼다.(큰 문제를 풀어 간다.)
  
  * CODE - 피보나치
   : 트리로 생각하자
  
  
  ?

  1 2 3 4 5 6 7 8 9 10

  int memo[100]; int fibonacci(int n) {     if (n <= 1) {         return n;     }     else {         memo[n] = fibonacci(n - 1) + fibonacci(n - 2);         return memo[n];     } }

   : memorization을 이용하면 반복을 줄일 수 있다! 
  
  

  

  
  

  ?

  1 2 3 4 5 6 7 8 9 10 11 12 13

  int memo[100]; int fibonacci(int n) {     if (n <= 1) {         return n;     }     else {         if (memo[n]) {             return memo[n];         }         memo[n] = fibonacci(n - 1) + fibonacci(n - 2);         return memo[n];     } }

   
  - Bottom-up
  1. 문제를 크기가 작은 문제부터 차례대로 푼다.
  2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
  3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
  4. 반복하면 언젠간 풀어야 하는 문제를 풀 수 있다.
  
  * CODE - 피보나치

  ?

  1 2 3 4 5 6 7 8 9

  int dp[100]; int fibonacci(int n) {     dp[0] = 1;     dp[1] = 1;     for (int i = 2; i <= n; i++) {         dp[i] = dp[i - 1] + dp[i - 2];     }     return dp[n]; }