(알고리즘) 이항계수

3. 이항 계수 구하는 문제

nCr = n-1Cr-1 + n-1Cr 공식 이용하여 이항 계수 계산

분할 정복

?

1 2 3 4 5

int bincoeff(int n, int k) {     if(k==0 || k==n) return 1;     else return bincoeff(n-1, k-1) + bincoeff(n-1, k); }

동적 프로그래밍

?

1 2 3 4 5 6 7 8 9

int bincoeff(int n, int k) {     int i,j;     int B[0...n][0...n];     for(i=0; i<n; i++)         for(j=0; j<min(i,k); j++)             if(j==0 || j==i) B[i][j] = 1;             else B[i][j] = B[i-1][j-1] + B[i-1][j];