2225번: 합분해

https://www.acmicpc.net/problem/2225


$O(nk)$

답은 kHn이다.

#include<cstdio>
int n, k, dp[201] = { 1 };
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++) dp[j] = (dp[j - 1] + dp[j]) % (int)(1e9);
    printf("%d", dp[n]);
    return 0;
}