[BOJ-11051]이항계수2

파스칼의 삼각형을 이용하여 동적계획법으로 풀이하면 된다. 

memo[n][k] 는 nCk 를 의미하고,

nCk = n-1Ck-1 + n-1Ck 를 더하여 값을 구할 수 있다.

#include<cstdio>
#include<vector>
#include<memory.h>
using namespace std;
 
typedef vector<int> vi;
const int MAX = 1111;
const int DIV = 10007;
int memo[MAX][MAX];
 
int combi(int n, int k) {
    if (k < 0 || n < 0) return 0;
    if (memo[n][k] == -1) memo[n][k] = (combi(n - 1, k - 1) + combi(n - 1, k)) % DIV;
    return memo[n][k];
}
 
int main() {
    memset(memo, -1, sizeof(memo));
    memo[0][0] = 1;
    int n, k; 
    scanf("%d%d", &n, &k);
    printf("%d\n", combi(n, k));
 
    return 0;
}