Dynamic Programming

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

  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을 이용하면 반복을 줄일 수 있다! 
  
  

  

  
  

  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 - 피보나치

  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];
  }