백준 2225 합분해

문제

풀이방법

떠오르지 않아 직접 표를 만들어 보았다.

예상외로 점화식은 dp[n][k]=dp[n][k-1]+dp[n-1][k]로 간단하였다.

코드

#include <iostream>
#define mod 1000000000
using namespace std;

int main()
{
    unsigned int dp[203][203] = { 0, };
    int i = 0, j = 0, n = 0, k = 0;
    cin >> n;
    cin >> k;
    for (i = 1; i <= n; i++) {
        dp[i][1] = 1;
    }
    for (i = 1; i <= k; i++)
        dp[1][i] = i;
    for (i = 2; i <= n; i++) {
        for (j = 2; j <= k; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
    }
    cout << dp[n][k];
    return 0;
}