동적 프로그래밍에 대해서는 아직 제대로 이해하지 못했다.
이해의 수준이 높아질 때마다 개선해 나갈 생각이다.

동적 프로그래밍(Dynamic Programming)이란?

'동적 계획법'이라고도 한다.

어려운 문제를 여러개의 하위 문제로 쪼갠후, 하위 문제들을 먼저 해결하는 방법이다.
풀린 작은 문제들을 이용해서 더 큰 문제들을 풀어나간다.

복잡한문제를 하위문제로 쪼갠다는 점에서 분할 정복과 유사해보이지만,
분할정복이 분할되는 작은 문제들이 각각 독립적이며 그 각각의 문제를 풀고 결과를 합치는 방식이라면,
동적 프로그래밍은 분할되는 작은 문제들이 독립적이지 않고 중복되는 부분이 있다는 점이다.
(하위문제의 결과를 이용해서 상위 문제를 푼다)
이런 문제를 동적프로그래밍이 아닌 분할정복으로 풀면 같은 문제를 반복해서 풀게되는 문제가 생긴다.

구조

동적 프로그래밍 알고리즘의 해답은 격자(Grid)의 형태이다.

1. 문제에 적합한 행과 열을 만든다.

격자의 각 칸은 원래 문제에 대한 하위문제이고, 다른 문제를 하위 문제로 가질 수 있다.
어떻게 원래의 문제를 하위문제로 나눌 수 있을지 고민해야한다.

2. 첫 번째 행부터 격자 칸의 값을 계산해 나간다

각 칸에 최적화 하고자하는 값을 적는다.
다음 행은 없다는 전제하에 계산해야한다.

3. 격자를 모두 채우게 되면 답이 나온다.

활용 사례

• git diff 명령어 처리
• 문자열의 유사성을 측정하는 레벤슈타인의 거리(Levenshtein distance)
• 워드프로세스의 자동 줄맞추기 기능