Dynamic programming
- 복잡한 문제를 여러개의 간단한 문제로 나누어 푼 다음, 그 결과를 결합하여 최종적인 해답에 도달하는 방법.
- 각 하위 문제의 결과를 계산한 뒤 저장하여 같은 하위 문제가 나왔을 때 간단하게 해결할 수 있다.
- 이를 통해 계산 횟수를 줄일 수 있다.
적용 조건
- Overlapping Subproblems
- 동일한 작은 문제들이 반보갛여 나타나는 경우
- Optimal Substructure
- 부분 문제의 최적 결과값을 통해 전체 문제의 최적 결과를 낼 수 있는 경우
구현 방법
- Bottom-up
- memorization(Tabulation - table-filling)을 위해 dp라는 배열을 만들고 dp[0]에서 시작하여 목표인 dp[n]까지 점화식을 통해 결과를 저장해가면서 만들어가는 방식
- Top-down
- dp[n]에서 시작하여 dp[0]이 나올때까지 재귀적으로 호출한다음 dp[0]에 도달하게 되면 결과값을 return해줌으로써 정답을 찾아가는 방식.
Github - https://github.com/dddwsd