이항 계수

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

11051번: 이항 계수 2

이항계수의 점화식을 기억해두자...

 

#include <iostream>
 
using namespace std;
int mod = 10007;
int dp[1004][1004] = { 0, };
 
int binomial(int n, int k) {
    
 
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= min(k, i); j++)
            if (i == j || j == 0)
                dp[i][j] = 1;
            else
            {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                dp[i][j] %= mod;
            }
 
 
    return dp[n][k];
}
 
int main()
{
    int n, k;
    cin >> n >> k;
 
    cout << binomial(n, k)  << '\n';
 
    return 0;
}