HW#06 : Dynamic Programming을 이용한 Binomial Coefficient 문제 해결HW#06 : Dynamic Programming을 이용한 Binomial Coefficient 문제 해결

Posted at 2011. 3. 31. 00:06 | Posted in Computer Science/알고리즘
#include <stdio.h>
#include <stdlib.h>

int minimum(int i, int k)
{
	if(i < k) return i;
	else return k;
}

int bin2(int n, int k)
{
	// Valable Decaltion
	int i = 0;
	int j = 0;
	int **B = NULL;

	int returnValue = 0;
	
	// Matrix Initialization
	B = (int**)malloc(sizeof(int*) * (n+1));

	for(i = 0; i < n+1; i++)
		B[i] = (int*)malloc(sizeof(int) * (k+1));

	for(i = 0; i < n+1; i++)
		for(j = 0; j < k+1; j++)
			B[i][j] = 0;

	// Binomial Coefficient
	for(i = 0; i <= n; i++)
		for(j = 0; j <= minimum(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];

	returnValue = B[n][k];
	
	// Matrix Uninitialization
	for(i = 0; i < n+1; i++)
		free(B[i]);
	
	free(B);

	return returnValue;
}

int main(int argc, char argv[])
{
	printf("B[4][2] = %d\n", bin2(4,2));

	return 0;
}

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기