Dynamic programming을 처음 배울 때 가르쳐주는 특징이

overlapping subproblems랑 optimal substructure잖아.

나는 어제까지만 해도 이 특징들을 생각을 안 하고

그냥 재귀함수부터 생각해보고 어쩌다 생각나면 풀어보는 방식으로 풀었었음.

근데 문제에서 overlapping subproblem이랑 optimal substructure가 

뭔지부터 생각해보면 답이 더 쉽게 생각나는 것 같다.

예를 들어 longest common subsequence 문제를 보면 A와 B라는 string 두 개가 있을 때,

overlapping subproblem은 A[i]와 B[j]가 같은 경우라는 거지.

왜냐하면 A[i] == B[j]일 경우 그 후에 나오는 수많은 경우들은 A[i] == B[j]인 경우가 overlapping, 즉 겹치는 경우이기 때문임.

Optimal substructure은 A[i] == B[j]인 경우일 때의 optimal solution, 즉 A[i]와 B[j]을 제외하고 본 string들의 최적의 해답을 바탕으로 만들 수 있음.

A[i] != B[j]일 때는 A[i]를 제외하고 본 string들, 혹은 B[j]를 제외하고 본 string들 중 더 나은 최적의 해답을 바탕으로 만들 수 있음.


물론 이런식으로 생각한다고 정답이 바로 떠오르는 건 아니지만

dp 문제들 풀 때 좋은 접근법이 되는 것 같다.

확실히 전처럼 마냥 재귀함수 짜보려고 머리 쥐어짜는 것보단

문제와 답에 대한 이해도도 훨씬 높아지는듯.


내가 책을 많이 안 읽어서 설명을 잘 못하는데 읽어줘서 아리가또.

꿀팁 더 있으면 오네가이.