2. 다이나믹 프로그래밍(동적 프로그래밍, 동적 계획법)

알고리즘 문제 풀이에 있어서 다이나믹 프로그래밍으로 풀수있는 문제는 두가지의 속성을 만족해야한다

1. Overlapping Subproblem 은 중복되는 부분 문제이다.

예를 들면 N번째 피보나치수를 구하는 문제를 구하는 문제는 N-1번째 N-2번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 경우가 생긴다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야한다. 그리고 문제를 작은 문제로 나누어서 풀 수 있어야한다.

2. Optimal Substructure 문제의 정답을 작은 문제의 정답을 구할 수 있다.

다이나믹 프로그래밍에서는 작은 문제들을 한 번만 풀어야한다.(시간을 줄이려면 당연히) 그리고 정답을 구했으면 이 답을 어딘가 메모해놓고 (Memoization) 이 답들을 이용해서 큰 문제를 푼다. 그리고 저장되는 공간을 cache라고 한다. 따라서 DP를 구현하기 위해서는 메모를 작성하는 부분과 메모를 읽는 부분이 필요하다. 피보나치 수를 구하는 예제를 살펴보면서 DP를 더 자세히 알아보자.