다이나믹 프로그래밍

이항 계수

4gats 2023. 6. 21. 15:58

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

 

11051번: 이항 계수 2

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\))

www.acmicpc.net

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}
 cs