다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.

- 큰 문제를 작은 문제로 쪼개는 알고리즘은 다이나믹 프로그래밍과 분할정복이 있다.

 두 알고리즘의 차이는 문제를 작은 문제로 만들었을 때, 분할정복과 다르게 dp는 중복이 가능하다는 점이다.

(따라서 중복을 잘 다뤄야한다.)

 

 

- 문제가 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

   1. overlapping Subproblem (겹치는 작은 문제)  

   2. optimal substructure (최적부분구조)

 

- 1번 속성에 의해 문제를 큰 문제와 작은 문제로 쪼갤 수 있어야하고, 큰 문제와 작은 문제는 같은 방식으로 풀 수 있어야한다.

- 2번 속성에 의해 문제의 정답을 작은 문제의 정답에서 구할 수 있다. -> 최적부분구조를 만족한다면, 문제의 크기와 관계없이 어떤 한 문제의 정답은 일정하다.

 

->다이나믹 프로그래밍에서 각 문제는 한번만 풀어야한다.

-> 최적부분구조를 만족하므로, 같은 문제는 구할때마다 정답이 같다. --> 더 큰 값을 구하기 위해 쓸 수 있다. 이러한 값을 

따로 저장해두는것을 memoization이라고 한다. (값을 저장하는 것과 꺼내 쓰는 것 구현해두면 좋다)

 

다이나믹 구현 방식에는 두 가지 방법이 있다.

1. top-down ->보통 재귀 

2. bottom-up ->보통 for문 

 

문제 풀이 전략 

>문제에서 구하려는 답을 문장으로 나타내기

>문장에 나와있는 변수의 개수만큼 메모하는 배열 만들기

>점화식을 잘...만들기 

 

 

문제 

 

- 1로만들기 

- 2*x타일링

- 2*x타일링 2

- 123더하기

- 카드구매하기

- 카드구매하기 2

- 123더하기 5

- 쉬운 계단 수 

- 이친수