합 N을 만드는 정수 K개 중에서, 하나의 값은 미리 정해두고 나머지 (k-1)개의 조합을 구하는 방식으로 모든 경우의 수를 구할 수 있다. 이처럼, 문제를 쪼개서 풀 수가 있고, sub-problems이 반복되기 때문에 Dynamic Programming으로 풀 수 있다.
위의 생각을 바탕으로, 다음과 같은 Top-Down recursive 방식을 생각할 수 있다.
solve( N, K ):
(n,k)
/ / \ \
(0, k-1), (1, k-1) ... (n-1, k-1), (n, k-1)
/ / ... | \
... (0, k-2), ... (n, k-2)
...
...
...
위의 (n,k)에서 시작하는 방식을 기반으로, (0, 1)부터 (n,k)까지 작성해나가는 Bottom-Up 방식으로 개선할 수 있다.
dp[n][k]에 대하여
dp[i][j] = dp[i][j-1]+ dp[i-1][j]
따라서, 시간 복잡도는 O(nk)이다.
Table을 작성하기 위한, (n+1) x (k+1)의 2D Array가 필요하다.
이처럼, DP를 쓰기 위해선, 문제를 쪼갤 수 있어야하고, 같은 문제가 반복적으로 나타야한다.
이 조건을 갖추면, 직관적으로 떠올릴 수 있는 Top-Down 방식을 생각하고, 순서를 뒤집어서 Bottom-Up 방식으로 개선하면 된다.