다이내믹 프로그래밍은 표를 크게 그리고 시작하면 풀린다는 식으로 배우기 쉽다. 칸을 채우는 순서만 찾으면 될 것 같고, 코드도 반복문으로 깔끔해 보인다. 그런데 이 접근은 문제를 먼저 이해한 것이 아니라 답안의 모양을 먼저 흉내 낸 것이다.

그 방식이 그럴듯한 이유는 있다. 편집 거리나 배낭 문제처럼 결과가 표로 정리되는 문제는, 완성된 해설을 보면 상태와 전이가 너무 당연해 보인다. 하지만 처음 만난 문제에서 중요한 것은 표의 크기가 아니다. 현재 문제가 어떤 더 작은 문제로 줄어드는지, 그때 무엇이 반복되는지다.

재귀는 여기서 꽤 불편하지만 유용하다. 종료 조건을 정하고 한 단계 줄여 보면, 필요한 상태가 드러난다. 같은 호출이 다시 나타날 때 메모가 필요한 이유도 보인다. 그 뒤에야 상향식으로 바꾸는 판단이 가능하다. 표는 생각의 출발점이 아니라, 이미 확인한 의존 관계를 저장하는 방식에 가깝다.

다음에 DP 문제를 만나면 배열부터 선언하지 말아야겠다. 우선 이 문제가 어디까지 작아질 수 있는지부터 보려고 한다.