Binomial Co-Efficient using Dynamic Programming in Java
In this Java tutorial, we are going to find the Binomial Co-efficient in Java with an easy Java program.
What is Binomial Co-efficient ?
A binomial co-efficient C(n,k) can be defined as the co-efficient of x^k in expansion of ( 1+x)^n .
It reflects choosing of k elements among n elements.
General Approach for the problem
Value of C( n,k ) can be calculated as
C( n,k ) = C( n-1 , k-1 ) + C( n-1 , k)
Step by Step Approach for the problem
- Input value of n and k .
- Build a 2-D matrix and fill it up in bottom-up manner.
- If k is zero or k is equal to n then return 1 as C ( n,0) and C(n,n) is equal to one.
- In other cases value of each cell in the table is equal to the sum of the value in the previous diagonal element and value of cell above it.
- Return the value of the last element of the table which is our answer.
Java Code to find the Binomial Co-efficient of C(n,k)
import java.util.Scanner; class Codespeedy { static int result ( int n , int k) { int dp[][] = new int[n+1][k+1]; int i,j, check; for (i=0 ; i<=n ;i++) { check = i>k ? k : i ; for(j=0 ; j<=check ;j++) { if(i==0 || j==0) dp[i][j]=1; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } } return dp[n][k]; } public static void main ( String args[]) { Scanner scan = new Scanner ( System.in) ; int n = scan.nextInt(); int k = scan.nextInt(); System.out.println(result(n,k)); } }
Here is an output provided for a particular input.
INPUT
6
4
OUTPUT
15
You may also learn,
Leave a Reply