GeeksforGeeks에 의하면 DP는 Sub-Problem들로 나누어 결과 값을 저장함으로써 계산 수를 줄이는 것을 말한다.
그러나 위는 그저 정의이고 실제로 풀 때는 다음과 같은 접근 방법이 편할 것이다. DP는 문제들을 작은 Sub-Problem으로 쪼개어 Sub-Problem 간의 상관 관계에 집중하여 결과적으로 전체 Problem을 푸는 방법이다.
조금 더 친근하게 말하기 위해 계단에 비유해 보겠다. 우리가 $n$번째 계단을 밟기 위해서는 $n-1, n-2, n-3, ..., 1$번째 계단들을 밟아야 한다. 순서대로 계단을 밟는다면 끝에 도달할 수 있다. 문제가 주어졌을 때 계단으로 바꾸어 생각해 보도록 한다. 어떠한 상태에서 다음 상태로 나아가기 위해 무슨 일을 해야하는지 고민하고 처음 상태와 끝 상태를 고려하면 문제는 풀린다.
피보나치 수열을 예로 들어보자.
$f_n = f_{n-1} + f_{n-1}$
$f_{10}$을 계산하기 위해서 재귀 함수를 이용한다면 $f_{10}$을 계산할 때 $f_5$가 필요할 때마다, $f_4, f_3, f_2, f_1, f_0$을 계산해야 한다. 이렇게 푼다면 굉장히 비효율적이지 않은가? 이 방법 대신에, 이전 두 값을 알 때 다음 값을 알 수 있다는 점을 고려하여 $f_2, f_3, f_4 ...$ 순서로 계산해 나간다면 쉽게 풀 수 있다는 것을 유추할 수 있다.
이처럼 임의의 $n$번째 Sub-Problem에 대하여, $n+1$ 번째 Sub-Problem을 구할 수 있다면 DP로 풀 수 있다. 또한 이 때 반드시 처음 Sub-Problem과 마지막 Sub-Problem을 고려해야 한다. 경계 값에서 프로그램이 버그를 일으킬 가능성이 높기 때문이다. 나중에 문제의 난이도가 조금 더 상승한다면, 임의의 $(n,m)$ Sub-Problem에 대하여 $(n+1, m)$과 $(n, m+1)$ 번째 Sub-Problem을 구할 수 있을 때 2차원 DP도 풀 수 있다. DP의 원리를 잘 파악한다면 보다 어려운 3, 4원 DP 문제들도 풀 수 있을 것이다. (ㅋㅋㅋㅋㅋㅋ..)
대부분 눈치를 챘겠지만, 점화식으로 나타낼 수 있는 모든 수열은 DP로 풀 수 있다. 하지만 이 말이 곧 점화식으로 나타낼 수 있다면 무조건 DP로 풀어야 한다는 것은 아니다. 반례로 피보나치 수열을 구하는 O(logn)의 시간 복잡도를 가지는 DP가 아닌 알고리즘이 있다.
코딩 테스트에 자주 나오는 DP 문제들은 경우의 수를 파악하는 문제, 조합을 구하는 문제, LIS (Longest Increasing Subsequence) 정도로 요약할 수 있다.