# 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,

- Find all prime numbers less than or equal to N in Java
- String Transformation in Java using Dynamic Programming

## Leave a Reply