DP를 조금이라도 잘 푸는 방법

그 동안 유독 DP 문제를 어려워 했었다.
다른 건 다 감을 많이 잡았는데, DP 만은 왜 이렇게 매번 새로운건지..

그래도 몇십 문제 풀면서,
개인적으로 내가 느꼈던 팁을 좀 정리해보고자 한다.

DP 문제라는걸 잊어라.

상당히 엥 할만한 말이긴 한데,

그러나 보통 DP 연습 목적으로 문제를 풀다보면,
애초에 문제 유형이 DP라는걸 알고 접근하는 경우가 많다.

답을 알고 있으니까, 억지로 점화식부터 세우려고 하니
이해를 할 지언정 DP로 접근해야만 하는 근본적인 이유는 알 수 없었다.

오히려 땅바닥에서부터 생각하니 윤곽이 잡혔다.
이 문제가 무슨 문제고, 복잡도가 뭐며,
먼저 그리디로 생각해보고, 안 잡히면 완전탐색으로 생각해보고,
그 과정에서 중복 계산이 계속 나온다면 DP로 도출하는게 훨씬 자연스럽다.

문제를 최대한 간단히 정의해라.

그 문제에 포함된 변수를 배열화하고, 값은 해당 경우에서 문제가 요구하는 값으로 둔다.

첫 트라이에서는 최적화를 고려하지 말아라.

거꾸로 생각해라.

dp 배열의 형태를 정의했다면, 가장 마지막 경우에서 직전의 시나리오를 생각해보아라.

그때 어떤 케이스로 나뉘어지는지 설계해라.

베이스라인을 잡아라.

자주 간과하지만 가장 중요한 것 중 하나가 초기화 상태다.