Skip to main content

Binomial coefficient using dynamic programming

Here given code implementation process.

// C Program 
// Binomial coefficient using dynamic programming
#include <stdio.h>

void biCoefficient(int n, int k)
{
	//   Formula nCr
	//      n!
	//   ––––––––––
	//   k! (n -k)!
	// auxiliary space
	int c[k + 1];
	int j = 0;
	// Set initial value
	for (j = 0; j <= k; ++j)
	{
		c[j] = 0;
	}
	// Set first
	c[0] = 1;
	// iterate the loop through by n
	for (int i = 1; i <= n; i++)
	{
		// Get minimum
		if (k > i)
		{
			j = i;
		}
		else
		{
			j = k;
		}
		while (j > 0)
		{
			c[j] = c[j] + c[j - 1];
			j--;
		}
	}
	// Display given n , k
	printf("\n Given  : (%d,%d) ", n, k);
	printf("\n Result :  %d\n", c[k]);
}
int main()
{
	// Test case
	biCoefficient(7, 3);
	biCoefficient(6, 4);
	biCoefficient(8, 2);
	return 0;
}

Output

 Given  : (7,3)
 Result :  35

 Given  : (6,4)
 Result :  15

 Given  : (8,2)
 Result :  28
/*
  Java Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	public void biCoefficient(int n, int k)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		int[] c = new int[k + 1];
		int j = 0;
		// Set initial value
		for (j = 0; j <= k; ++j)
		{
			c[j] = 0;
		}
		// Set first
		c[0] = 1;
		// iterate the loop through by n
		for (int i = 1; i <= n; i++)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j--;
			}
		}
		// Display given n , k
		System.out.print("\n Given : (n = " + n + ",k = " + k + ") ");
		System.out.print("\n Result : " + c[k] + "\n");
	}
	public static void main(String[] args)
	{
		BinomialCoefficient task = new BinomialCoefficient();
		// Test case
		task.biCoefficient(7, 3);
		task.biCoefficient(6, 4);
		task.biCoefficient(8, 2);
	}
}

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	public: void biCoefficient(int n, int k)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		int c[k + 1];
		int j = 0;
		// Set initial value
		for (j = 0; j <= k; ++j)
		{
			c[j] = 0;
		}
		// Set first
		c[0] = 1;
		// iterate the loop through by n
		for (int i = 1; i <= n; i++)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j--;
			}
		}
		// Display given n , k
		cout << "\n Given : (n = " << n << ",k = " << k << ") ";
		cout << "\n Result : " << c[k] << "\n";
	}
};
int main()
{
	BinomialCoefficient task = BinomialCoefficient();
	// Test case
	task.biCoefficient(7, 3);
	task.biCoefficient(6, 4);
	task.biCoefficient(8, 2);
	return 0;
}

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
// Include namespace system
using System;
/*
  C# Program 
  Binomial coefficient using dynamic programming
*/
public class BinomialCoefficient
{
	public void biCoefficient(int n, int k)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		int[] c = new int[k + 1];
		int j = 0;
		// Set initial value
		for (j = 0; j <= k; ++j)
		{
			c[j] = 0;
		}
		// Set first
		c[0] = 1;
		// iterate the loop through by n
		for (int i = 1; i <= n; i++)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j--;
			}
		}
		// Display given n , k
		Console.Write("\n Given : (n = " + n + ",k = " + k + ") ");
		Console.Write("\n Result : " + c[k] + "\n");
	}
	public static void Main(String[] args)
	{
		BinomialCoefficient task = new BinomialCoefficient();
		// Test case
		task.biCoefficient(7, 3);
		task.biCoefficient(6, 4);
		task.biCoefficient(8, 2);
	}
}

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
<?php
/*
  Php Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	public	function biCoefficient($n, $k)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		$c = array_fill(0, $k + 1, 0);
		$j = 0;
		// Set initial value
		for ($j = 0; $j <= $k; ++$j)
		{
			$c[$j] = 0;
		}
		// Set first
		$c[0] = 1;
		// iterate the loop through by n
		for ($i = 1; $i <= $n; $i++)
		{
			// Get minimum
			if ($k > $i)
			{
				$j = $i;
			}
			else
			{
				$j = $k;
			}
			while ($j > 0)
			{
				$c[$j] = $c[$j] + $c[$j - 1];
				$j--;
			}
		}
		// Display given n , k
		echo "\n Given : (n = ". $n .",k = ". $k .") ";
		echo "\n Result : ". $c[$k] ."\n";
	}
}

function main()
{
	$task = new BinomialCoefficient();
	$task->biCoefficient(7, 3);
	$task->biCoefficient(6, 4);
	$task->biCoefficient(8, 2);
}
main();

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
/*
  Node Js Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	biCoefficient(n, k)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		var c = Array(k + 1).fill(0);
		var j = 0;
		// Set initial value
		for (j = 0; j <= k; ++j)
		{
			c[j] = 0;
		}
		// Set first
		c[0] = 1;
		// iterate the loop through by n
		for (var i = 1; i <= n; i++)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j--;
			}
		}
		// Display given n , k
		process.stdout.write("\n Given : (n = " + n + ",k = " + k + ") ");
		process.stdout.write("\n Result : " + c[k] + "\n");
	}
}

function main()
{
	var task = new BinomialCoefficient();
	// Test case
	task.biCoefficient(7, 3);
	task.biCoefficient(6, 4);
	task.biCoefficient(8, 2);
}
main();

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
# 
#   Python 3 Program 
#   Binomial coefficient using dynamic programming

class BinomialCoefficient :
	def biCoefficient(self, n, k) :
		#    Formula nCr
		#       n!
		#    ––––––––––
		#    k! (n -k)!
		#  auxiliary space
		c = [0] * (k + 1)
		j = 0
		#  Set initial value
		while (j <= k) :
			c[j] = 0
			j += 1
		
		#  Set first
		c[0] = 1
		i = 1
		#  iterate the loop through by n
		while (i <= n) :
			#  Get minimum
			if (k > i) :
				j = i
			else :
				j = k
			
			while (j > 0) :
				c[j] = c[j] + c[j - 1]
				j -= 1
			
			i += 1
		
		#  Display given n , k
		print("\n Given : (n = ", n ,",k = ", k ,") ", end = "")
		print("\n Result : ", c[k] )
	

def main() :
	task = BinomialCoefficient()
	#  Test case
	task.biCoefficient(7, 3)
	task.biCoefficient(6, 4)
	task.biCoefficient(8, 2)

if __name__ == "__main__": main()

Output

 Given : (n =  7 ,k =  3 )
 Result :  35

 Given : (n =  6 ,k =  4 )
 Result :  15

 Given : (n =  8 ,k =  2 )
 Result :  28
#   Ruby Program 
#   Binomial coefficient using dynamic programming

class BinomialCoefficient 
	def biCoefficient(n, k) 
		#    Formula nCr
		#       n!
		#    ––––––––––
		#    k! (n -k)!
		#  auxiliary space
		c = Array.new(k + 1) {0}
		j = 0
		#  Set initial value
		while (j <= k) 
			c[j] = 0
			j += 1
		end

		#  Set first
		c[0] = 1
		i = 1
		#  iterate the loop through by n
		while (i <= n) 
			#  Get minimum
			if (k > i) 
				j = i
			else 
				j = k
			end

			while (j > 0) 
				c[j] = c[j] + c[j - 1]
				j -= 1
			end

			i += 1
		end

		#  Display given n , k
		print("\n Given : (n = ", n ,",k = ", k ,") ")
		print("\n Result : ", c[k] ,"\n")
	end

end

def main() 
	task = BinomialCoefficient.new()
	#  Test case
	task.biCoefficient(7, 3)
	task.biCoefficient(6, 4)
	task.biCoefficient(8, 2)
end

main()

Output

 Given : (n = 7,k = 3) 
 Result : 35

 Given : (n = 6,k = 4) 
 Result : 15

 Given : (n = 8,k = 2) 
 Result : 28

/*
  Scala Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	def biCoefficient(n: Int, k: Int): Unit = {
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		var c: Array[Int] = Array.fill[Int](k + 1)(0);
		var j: Int = 0;
		// Set initial value
		while (j <= k)
		{
			c(j) = 0;
			j += 1;
		}
		// Set first
		c(0) = 1;
		var i: Int = 1;
		// iterate the loop through by n
		while (i <= n)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c(j) = c(j) + c(j - 1);
				j -= 1;
			}
			i += 1;
		}
		// Display given n , k
		print("\n Given : (n = " + n + ",k = " + k + ") ");
		print("\n Result : " + c(k) + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BinomialCoefficient = new BinomialCoefficient();
		// Test case
		task.biCoefficient(7, 3);
		task.biCoefficient(6, 4);
		task.biCoefficient(8, 2);
	}
}

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
/*
  Swift 4 Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	func biCoefficient(_ n: Int, _ k: Int)
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		var c: [Int] = Array(repeating: 0, count: k + 1);
		var j: Int = 0;
		// Set initial value
		while (j <= k)
		{
			c[j] = 0;
			j += 1;
		}
		// Set first
		c[0] = 1;
		var i: Int = 1;
		// iterate the loop through by n
		while (i <= n)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j -= 1;
			}
			i += 1;
		}
		// Display given n , k
		print("\n Given : (n = ", n ,",k = ", k ,") ", terminator: "");
		print("\n Result : ", c[k] );
	}
}
func main()
{
	let task: BinomialCoefficient = BinomialCoefficient();
	// Test case
	task.biCoefficient(7, 3);
	task.biCoefficient(6, 4);
	task.biCoefficient(8, 2);
}
main();

Output

 Given : (n =  7 ,k =  3 )
 Result :  35

 Given : (n =  6 ,k =  4 )
 Result :  15

 Given : (n =  8 ,k =  2 )
 Result :  28
/*
  Kotlin Program 
  Binomial coefficient using dynamic programming
*/
class BinomialCoefficient
{
	fun biCoefficient(n: Int, k: Int): Unit
	{
		//   Formula nCr
		//      n!
		//   ––––––––––
		//   k! (n -k)!
		// auxiliary space
		var c: Array < Int > = Array(k + 1)
		{
			0
		};
		var j: Int = 0;
		// Set initial value
		while (j <= k)
		{
			c[j] = 0;
			j += 1;
		}
		// Set first
		c[0] = 1;
		var i: Int = 1;
		// iterate the loop through by n
		while (i <= n)
		{
			// Get minimum
			if (k > i)
			{
				j = i;
			}
			else
			{
				j = k;
			}
			while (j > 0)
			{
				c[j] = c[j] + c[j - 1];
				j -= 1;
			}
			i += 1;
		}
		// Display given n , k
		print("\n Given : (n = " + n + ",k = " + k + ") ");
		print("\n Result : " + c[k] + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: BinomialCoefficient = BinomialCoefficient();
	// Test case
	task.biCoefficient(7, 3);
	task.biCoefficient(6, 4);
	task.biCoefficient(8, 2);
}

Output

 Given : (n = 7,k = 3)
 Result : 35

 Given : (n = 6,k = 4)
 Result : 15

 Given : (n = 8,k = 2)
 Result : 28
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment