Binomial Co-Efficient using Dynamic Programming in Java

By divyesh srivastava

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

  1. Input value of n and k .
  2. Build a 2-D matrix and fill it up in bottom-up manner.
  3.  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.
  4. 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.
  5. 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