Dynamic Programming (동적 프로그래밍)

• 분할 정복 풀이!
• 어떤 문제를 풀기 쉬운 작은 문제로 분할해서 풀어나가는 법 (순열)

수열

• 수열은 "숫자의 나열"
  

초항(a1)

• 수열의 첫 번째 항

점화식(an)

• 초항 이후의 나머지 값을 구하기 위한 규칙
• 수열의 n번째 값 an을 구하기 위해 따라야 하는 규칙
• an을 구하기 위해서는 a1부터 순서대로 계산해야함

점화식을 사용한 문제 풀이

분할 정복 풀이 : Top-down 접근

• a5를 구하기 위해 a4를 구하고, a4를 구하기 위해 a3를 구하고, a3를 구하기 위해 a2를 구하고, a2를 구하기 위해 a1를 구하는데, 우리는 a1을 이미 알고있으니까 다시 위로 올라가면서 a2, a3, a4, a5를 구할 수 있다.

분할 정복 풀이 : Bottom-up 접근 (추천!)

• 가장 작은값부터 계산해서 위로 올라감
• a1을 이용해서 a2를 구하고, a2를 이용해서 a3을 구하고, a3를 이용해서 a4을 구하고, a4를 이용해서 a5를 구한다!

동적 프로그래밍의 자료구조 -> 배열(Array)

• 배열과 수열 사이에는 규칙이 있다
• 배열의 가장 왼쪽에 있는 index가 1인 원소(arr[1])는 곧 수열의 첫번째 원소 a1, 배열의 가장 오른쪽에 담겨있는 arr[5]는 a5이다.
• ai == arr[i]

-> 결국 for 반복문으로 구현 가능

pseudo code

int arr[5] = {3,0,0,0,0};

for (int i = 2; i <= 5;i++) 
{
	arr[i] = 2*arr[i-1] - 4; // a_n = 2a_n-1 -4
}

print(arr[5])