# 算法设计：如何计算二项式系数？（动态规划）

2021年3月27日18:00:40 发表评论 2,637 次浏览

## 本文概述

``二项式系数C(n, k)可定义为(1 + x)^n展开后x^k的系数。``
``二项式系数C(n, k)也给出了从n个对象中更正式地选择k个对象的方法的数量，而不考虑顺序，即n个元素集合的k个元素子集(或k个组合)的数量。``

1)最优子结构

``````C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1``````

## C ++

``````// A naive recursive C++ implementation
#include <bits/stdc++.h>
using namespace std;

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff( int n, int k)
{
// Base Cases
if (k == 0 || k == n)
return 1;

// Recur
return binomialCoeff(n - 1, k - 1) +
binomialCoeff(n - 1, k);
}

/* Driver code*/
int main()
{
int n = 5, k = 2;
cout << "Value of C(" <<n<< ", " <<k<< ") is " <<
binomialCoeff(n, k);
return 0;
}

// This is code is contributed by rathbhupendra``````

## C

``````// A Naive Recursive Implementation
#include<stdio.h>

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff( int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;

// Recur
return  binomialCoeff(n-1, k-1) +
binomialCoeff(n-1, k);
}

/* Driver program to test above function*/
int main()
{
int n = 5, k = 2;
printf ( "Value of C(%d, %d) is %d " , n, k, binomialCoeff(n, k));
return 0;
}``````

## Java

``````// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;

class GFG {

// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff( int n, int k)
{

// Base Cases
if (k == 0 || k == n)
return 1 ;

// Recur
return binomialCoeff(n - 1 , k - 1 ) +
binomialCoeff(n - 1 , k);
}

/* Driver program to test above function */
public static void main(String[] args)
{
int n = 5 , k = 2 ;
System.out.printf( "Value of C(%d, %d) is %d " , n, k, binomialCoeff(n, k));
}
}

// This code is contributed by Arnav Kr. Mandal.``````

## python

``````# A naive recursive Python implementation

def binomialCoeff(n , k):

if k = = 0 or k = = n :
return 1

# Recursive Call
return binomialCoeff(n - 1 , k - 1 ) +
binomialCoeff(n - 1 , k)

# Driver Program to test ht above function
n = 5
k = 2
print "Value of C(%d, %d) is (%d)" % (n , k , binomialCoeff(n , k))

# This code is contributed by Nikhil Kumar Singh (nickzuck_007)``````

## C#

``````// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using System;

class GFG {

// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff( int n, int k)
{

// Base Cases
if (k == 0 || k == n)
return 1;

// Recur
return binomialCoeff(n - 1, k - 1) +
binomialCoeff(n - 1, k);
}

/* Driver program to test above function */
public static void Main()
{
int n = 5, k = 2;
Console.Write( "Value of C(" + n + ", "
+ k + ") is " +
binomialCoeff(n, k));
}
}

// This code is contributed by Sam007.``````

## 的PHP

``````<?php
// PHP Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)

// Returns value of
// Binomial Coefficient C(n, k)
function binomialCoeff( \$n , \$k )
{
// Base Cases
if ( \$k ==0 || \$k == \$n )
return 1;

// Recur
return binomialCoeff( \$n - 1, \$k - 1) +
binomialCoeff( \$n - 1, \$k );
}

// Driver Code
\$n = 5;
\$k = 2;
echo "Value of C" , "(" , \$n , \$k , ") is "
, binomialCoeff( \$n , \$k );

// This code is contributed by aj_36
?>``````

``Value of C(5, 2) is 10``

2)重叠子问题

C(5, 2)的二项式系数递归树

## C ++

``````// A Dynamic Programming based solution that uses
// table C[][] to calculate the Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;

// Prototype of a utility function that
// returns minimum of two integers
int min( int a, int b);

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff( int n, int k)
{
int C[n + 1][k + 1];
int i, j;

// Caculate value of Binomial Coefficient
// in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;

// Calculate value using previously
// stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}

return C[n][k];
}

// A utility function to return
// minimum of two integers
int min( int a, int b)
{
return (a < b) ? a : b;
}

// Driver Code
int main()
{
int n = 5, k = 2;
cout << "Value of C[" << n << "]["
<< k << "] is " << binomialCoeff(n, k);
}

// This code is contributed by Shivi_Aggarwal``````

## C

``````// A Dynamic Programming based solution
// that uses table C[][] to
// calculate the Binomial Coefficient
#include<stdio.h>

// Prototype of a utility function that
// returns minimum of two integers
int min( int a, int b);

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff( int n, int k)
{
int C[n+1][k+1];
int i, j;

// Caculate value of Binomial Coefficient
// in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;

// Calculate value using
// previously stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}

return C[n][k];
}

// A utility function to return
// minimum of two integers
int min( int a, int b)
{
return (a<b)? a: b;
}

/* Drier program to test above function*/
int main()
{
int n = 5, k = 2;
printf ( "Value of C(%d, %d) is %d " , n, k, binomialCoeff(n, k) );
return 0;
}``````

## Java

``````// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient

class BinomialCoefficient
{
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff( int n, int k)
{
int C[][] = new int [n+ 1 ][k+ 1 ];
int i, j;

// Calculate  value of Binomial
// Coefficient in bottom up manner
for (i = 0 ; i <= n; i++)
{
for (j = 0 ; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1 ;

// Calculate value using
// previously stored values
else
C[i][j] = C[i- 1 ][j- 1 ] + C[i- 1 ][j];
}
}

return C[n][k];
}

// A utility function to return
// minimum of two integers
static int min( int a, int b)
{
return (a<b)? a: b;
}

/* Driver program to test above function*/
public static void main(String args[])
{
int n = 5 , k = 2 ;
System.out.println( "Value of C(" +n+ ", " +k+ ") is " +
binomialCoeff(n, k));
}
}
/*This code is contributed by Rajat Mishra*/``````

## python

``````# A Dynamic Programming based Python
# Program that uses table C[][]
# to calculate the Binomial Coefficient

# Returns value of Binomial Coefficient C(n, k)
def binomialCoef(n, k):
C = [[ 0 for x in range (k + 1 )] for x in range (n + 1 )]

# Calculate value of Binomial
# Coefficient in bottom up manner
for i in range (n + 1 ):
for j in range ( min (i, k) + 1 ):
# Base Cases
if j = = 0 or j = = i:
C[i][j] = 1

# Calculate value using
# previously stored values
else :
C[i][j] = C[i - 1 ][j - 1 ] + C[i - 1 ][j]

return C[n][k]

# Driver program to test above function
n = 5
k = 2
print ( "Value of C[" + str (n) + "][" + str (k) + "] is "
+ str (binomialCoef(n, k)))

# This code is contributed by Bhavya Jain``````

## C#

``````// A Dynamic Programming based solution that
// uses table C[][] to calculate the Binomial
// Coefficient
using System;

class GFG {

// Returns value of Binomial Coefficient
// C(n, k)
static int binomialCoeff( int n, int k)
{
int [, ]C = new int [n+1, k+1];
int i, j;

// Calculate value of Binomial
// Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= Math.Min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i, j] = 1;

// Calculate value using previously
// stored values
else
C[i, j] = C[i-1, j-1] + C[i-1, j];
}
}

return C[n, k];
}

// A utility function to return minimum
// of two integers
static int min( int a, int b)
{
return (a < b) ? a : b;
}

/* Driver program to test above function*/
public static void Main()
{
int n = 5, k = 2;
Console.WriteLine( "Value of C(" + n
+ ", " + k + ") is "
+ binomialCoeff(n, k));
}
}

// This code is contributed by anuj_67.``````

## 的PHP

``````<?php
// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient

// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff( \$n , \$k )
{
\$C = array ( array ());
\$i ; \$j ;

// Caculate value of Binomial
// Coefficient in bottom up manner
for ( \$i = 0; \$i <= \$n ; \$i ++)
{
for ( \$j = 0; \$j <= min( \$i , \$k ); \$j ++)
{

// Base Cases
if ( \$j == 0 || \$j == \$i )
\$C [ \$i ][ \$j ] = 1;

// Calculate value using
// previously stored values
else
\$C [ \$i ][ \$j ] = \$C [ \$i - 1][ \$j - 1] +
\$C [ \$i - 1][ \$j ];
}
}

return \$C [ \$n ][ \$k ];
}

// Driver Code
\$n = 5;
\$k = 2;
echo "Value of C(" , \$n , " " , \$k , ") is" , " "
, binomialCoeff( \$n , \$k ) ;

// This code is contributed by anuj_67.
?>``````

``Value of C[5][2] is 10``

## C ++

``````// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;

int binomialCoeff( int n, int k)
{
int C[k+1];
memset (C, 0, sizeof (C));

C[0] = 1;  // nC0 is 1

for ( int i = 1; i <= n; i++)
{
// Compute next row of pascal triangle using
// the previous row
for ( int j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}

/* Drier program to test above function*/
int main()
{
int n = 5, k = 2;
printf ( "Value of C(%d, %d) is %d " , n, k, binomialCoeff(n, k) );
return 0;
}``````

## Java

``````// JAVA Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
import java.util.*;

class GFG {

static int binomialCoeff( int n, int k)
{
int C[] = new int [k + 1 ];

// nC0 is 1
C[ 0 ] = 1 ;

for ( int i = 1 ; i <= n; i++)
{
// Compute next row of pascal
// triangle using the previous row
for ( int j = Math.min(i, k); j > 0 ; j--)
C[j] = C[j] + C[j- 1 ];
}
return C[k];
}

/* Driver program  */
public static void main(String[] args)
{
int n = 5 , k = 2 ;
System.out.printf( "Value of C(%d, %d) is %d "
, n, k, binomialCoeff(n, k));
}
}``````

## python

``````# Python program for Optimized
# Dynamic Programming solution to
# Binomail Coefficient. This one
# uses the concept of pascal
# Triangle and less memory

def binomialCoeff(n , k):

# Declaring an empty array
C = [ 0 for i in xrange (k + 1 )]
C[ 0 ] = 1 #since nC0 is 1

for i in range ( 1 , n + 1 ):

# Compute next row of pascal triangle using
# the previous row
j = min (i , k)
while (j> 0 ):
C[j] = C[j] + C[j - 1 ]
j - = 1

return C[k]

# Driver Program to test the above function
n = 5
k = 2
print "Value of C(%d, %d) is %d" % (n, k, binomialCoeff(n, k))

# This code is contribtued by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````// C# Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
using System;

class GFG {

static int binomialCoeff( int n, int k)
{
int [] C = new int [k + 1];

// nC0 is 1
C[0] = 1;

for ( int i = 1; i <= n; i++)
{
// Compute next row of pascal
// triangle using the previous
// row
for ( int j = Math.Min(i, k);
j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}

/* Driver program */
public static void Main()
{
int n = 5, k = 2;
Console.WriteLine( "Value of C("
+ n + " " + k + ") is "
+ binomialCoeff(n, k));
}
}

// This code is contribtued by anuj_67.``````

## 的PHP

``````<?php
// PHP program for space optimized
// Dynamic Programming Solution of
// Binomial Coefficient
function binomialCoeff( \$n , \$k )
{
\$C = array_fill (0, \$k + 1, 0);

\$C [0] = 1; // nC0 is 1

for ( \$i = 1; \$i <= \$n ; \$i ++)
{
// Compute next row of pascal
// triangle using the previous row
for ( \$j = min( \$i , \$k ); \$j > 0; \$j --)
\$C [ \$j ] = \$C [ \$j ] + \$C [ \$j - 1];
}
return \$C [ \$k ];
}

// Driver Code
\$n = 5; \$k = 2;
echo "Value of C[\$n, \$k] is " .
binomialCoeff( \$n , \$k );

// This code is contributed by mits.
?>``````

``Value of C(5, 2) is 10``

O(n * k)

1 ========== >> >> n = 0, C(0, 0)= 1

1–1 ======== >>>> n = 1, C(1, 0)= 1, C(1, 1)= 1

1–2–1 ====== >> n = 2, C(2, 0)= 1, C(2, 1)= 2, C(2, 2)= 1

1–3–3–1 ==== >> n = 3, C(3, 0)= 1, C(3, 1)= 3, C(3, 2)= 3, C(3, 3) = 1

1–4–6–4–1 == >> n = 4, C(4, 0)= 1, C(4, 1)= 4, C(4, 2)= 6, C(4, 3) = 4, C(4, 4)= 1

C [j] = C [j] + C [j-1]

``````Let's say we want to calculate C(4, 3), i.e. n=4, k=3:

All elements of array C of size 4 (k+1) are
initialized to ZERO.

i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;
Then C[0] is set to 1

For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1, 1) = 1

For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2, 2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2, 1) = 2

For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3, 3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3, 2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3, 1) = 3

For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4, 4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4, 3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4, 2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4, 1) = 4

C(4, 3) = 4 is would be the answer in our example.``````

## C ++

``````// A Dynamic Programming based
// solution that uses
// table dp[][] to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table C++ implementation
#include <bits/stdc++.h>
using namespace std;

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeffUtil( int n, int k, int ** dp)
{
// If value in lookup table then return
if (dp[n][k] != -1) //
return dp[n][k];

// store value in a table before return
if (k == 0) {
dp[n][k] = 1;
return dp[n][k];
}

// store value in table before return
if (k == n) {
dp[n][k] = 1;
return dp[n][k];
}

// save value in lookup table before return
dp[n][k] = binomialCoeffUtil(n - 1, k - 1, dp) +
binomialCoeffUtil(n - 1, k, dp);
return dp[n][k];
}

int binomialCoeff( int n, int k)
{
int ** dp; // make a temporary lookup table
dp = new int *[n + 1];

// loop to create table dynamically
for ( int i = 0; i < (n + 1); i++) {
dp[i] = new int [k + 1];
}

// nested loop to initialise the table with -1
for ( int i = 0; i < (n + 1); i++) {
for ( int j = 0; j < (k + 1); j++) {
dp[i][j] = -1;
}
}

return binomialCoeffUtil(n, k, dp);
}

/* Driver code*/
int main()
{
int n = 5, k = 2;
cout << "Value of C(" << n << ", " << k << ") is "
<< binomialCoeff(n, k) << endl;
return 0;
}

// This is code is contributed by MOHAMMAD MUDASSIR``````

## Java

``````// A Dynamic Programming based
// solution that uses
// table dp[][] to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table Java implementation
import java.util.*;
class GFG{

// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeffUtil( int n, int k, Vector<Integer> []dp)
{
// If value in lookup table
// then return
if (dp[n].get(k) != - 1 )
return dp[n].get(k);

// store value in a table
// before return
if (k == 0 )
{
return dp[n].get(k);
}

// store value in table
// before return
if (k == n)
{
return dp[n].get(k);
}

// save value in lookup table
// before return
dp[n].add(k, binomialCoeffUtil(n - 1 , k - 1 , dp) +
binomialCoeffUtil(n - 1 , k, dp));
return dp[n].get(k);
}

static int binomialCoeff( int n, int k)
{
// Make a temporary lookup table
Vector<Integer> []dp = new Vector[n+ 1 ];

// Loop to create table dynamically
for ( int i = 0 ; i < (n + 1 ); i++)
{
dp[i] = new Vector<Integer>();
for ( int j = 0 ; j <= k; j++)
}
return binomialCoeffUtil(n, k, dp);
}

// Driver code
public static void main(String[] args)
{
int n = 5 , k = 2 ;
System.out.print( "Value of C(" + n +
", " + k + ") is " +
binomialCoeff(n, k) + "\n" );
}
}

// This code is contributed by Rajput-Ji``````

## Python3

``````# A Dynamic Programming based solution
# that uses table dp[][] to calculate
# the Binomial Coefficient. A naive
# recursive approach with table
# Python3 implementation

# Returns value of Binomial
# Coefficient C(n, k)
def binomialCoeffUtil(n, k, dp):

# If value in lookup table then return
if dp[n][k] ! = - 1 :
return dp[n][k]

# Store value in a table before return
if k = = 0 :
dp[n][k] = 1
return dp[n][k]

# Store value in table before return
if k = = n:
dp[n][k] = 1
return dp[n][k]

# Save value in lookup table before return
dp[n][k] = (binomialCoeffUtil(n - 1 , k - 1 , dp) +
binomialCoeffUtil(n - 1 , k, dp))

return dp[n][k]

def binomialCoeff(n, k):

# Make a temporary lookup table
dp = [ [ - 1 for y in range (k + 1 ) ]
for x in range (n + 1 ) ]

return binomialCoeffUtil(n, k, dp)

# Driver code
n = 5
k = 2

print ( "Value of C(" + str (n) +
", " + str (k) + ") is" , binomialCoeff(n, k))

# This is code is contributed by Prateek Gupta``````

## C#

``````// C# program for the
// above approach

// A Dynamic Programming based
// solution that uses
// table [, ]dp to calculate
// the Binomial Coefficient
// A naive recursive approach
// with table C# implementation
using System;
using System.Collections.Generic;
class GFG{

// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeffUtil( int n, int k, List< int > []dp)
{
// If value in lookup table
// then return
if (dp[n][k] != -1)
return dp[n][k];

// store value in a table
// before return
if (k == 0)
{
dp[n][k] = 1;
return dp[n][k];
}

// store value in table
// before return
if (k == n)
{
dp[n][k] = 1;
return dp[n][k];
}

// save value in lookup table
// before return
dp[n][k] = binomialCoeffUtil(n - 1, k - 1, dp) +
binomialCoeffUtil(n - 1, k, dp);
return dp[n][k];
}

static int binomialCoeff( int n, int k)
{
// Make a temporary lookup table
List< int > []dp = new List< int >[n + 1];

// Loop to create table dynamically
for ( int i = 0; i < (n + 1); i++)
{
dp[i] = new List< int >();

for ( int j = 0; j <= k; j++)
}
return binomialCoeffUtil(n, k, dp);
}

// Driver code
public static void Main(String[] args)
{
int n = 5, k = 2;
Console.Write( "Value of C(" + n +
", " + k + ") is " +
binomialCoeff(n, k) + "\n" );
}
}

// This code is contributed by 29AjayKumar``````

``Value of C(5, 2) is 10``

http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm