2225번 합분해(DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/2225

<전략>

1. K개의 합 (ㅁ+ㅁ+ㅁ+...+i) = N 이라고 할때, K-1개의 합 (ㅁ+ㅁ+ㅁ...+ㅁ) = N - i이고, i가 0<= i <= n 의 범위이므로d[n][k]를 n을 k개의 정수의 합으로 나타낸 경우의 수라 하면, d[n][k] = d[n-0][k-1] + d[n-1][k-1] + ... + d[n-n][k-1] 으로 나타낼 수 있다.

※주의사항

1. d[0][0]는 이론상 존재하지 않는 경우지만, 해당 메모이제이션을 위해서는 d[0][0]가 최하단에서 호출되므로, 1로 초기화 해준다.

Code