[DP] 다이나믹 프로그래밍이란?

1. 개념

"하나의 문제는 한번만 풀도록 하는 알고리즘" - 핵심

다이나믹 프로그래밍은 문제의 답이 이용되는 구조를 이용한 알고리즘이다. 큰 문제를 작은 문제로 나눈다는 측면에서 분할정복(divide and conquer)알고리즘과 비슷하지만 다음과 같은 차이점이 존재한다.

DAC	DP
문제가 절반으로 줄어듬	문자게 -1로 줄어듬
Function problem	최적화 문제
결과가 한번 사용	결과가 여러번 사용됨
분할이 성능 향상	결과 재사용이 성능 향상

다이나믹 프로그래밍 알고리즘을 적용하기 위해서는 두가지 조건을 만족해야 한다.- 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰

• 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지?
     (Overlapping SubProblem)
  문제를 작은 문제로 나누어 풀 수 있어야 하며, 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 한다. 
  
  
• 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
     (Optimal Substructure)

2. 알고리즘 기법

• Top-Down (Recursive)
  1. 문제를 작은 문제로 나눈다. 
  2. 작은 문제들을 푼다.
  3. 작은 문제들의 답으로 전체 문제를 푼다.
  
  
• Bottom-Up (주로 반복문)
  1. 가장 작은 문제부터 푼다.
  2. 문제의 크기를 점점 크게 만들어서 전체문제를 푼다.
  

 

3. 점화식

1. 점화식 : 인접한 항들 사이의 관계식
   
   

4. Tip.

큰 문제가 주어지면 작은 문제부터 확인하자. cache[0],cache[1],cache[2].. 순서대로 해결하다보면 규칙이 보일 것이다.
하지만 그 규칙을 제대로 구현하는 것은 나의 실력 문제니... 열심히 하겠습니다.