Following are common definition ofBinomial Coefficients.
1) Abinomial coefficientC(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.
2) A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.
The Problem
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.
1) Optimal Substructure
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients.
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
2) Overlapping Subproblems
Following is simple recursive implementation that simply follows the recursive structure mentioned above.
package DP;
public class BionomialCoefficient {
public static void main(String[] args) {
int n = 5, k = 2;
System.out.println(binomialCoeffRec(n, k));
System.out.println(binomialCoeffDP_2D(n, k));
System.out.println(binomialCoeffDP_1D(n, k));
}
public static int binomialCoeffRec(int n, int k){
if(k==0 || k==n){
return 1;
}
return binomialCoeffRec(n-1, k-1) + binomialCoeffRec(n-1, k);
}
// Returns value of Binomial Coefficient C(n, k)
// Time Complexity: O(n*k), Auxiliary Space: O(n*k)
public static int binomialCoeffDP_2D(int n, int k){
int[][] dp = new int[n+1][k+1];
// Caculate value of Binomial Coefficient in bottom up manner
for(int i=0; i<=n; i++){
for(int j=0; j<=Math.min(i, k); j++){
if(j==0 || j==i){ // Base Cases
dp[i][j] = 1;
}else{ // Calculate value using previosly stored values
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
}
return dp[n][k];
}
// A space optimized Dynamic Programming Solution
// Time Complexity: O(n*k), Auxiliary Space: O(k)
public static int binomialCoeffDP_1D(int n, int k){
int[] dp = new int[k+1];
dp[0] = 1;
for(int i=1; i<=n; i++){
for(int j=Math.min(i, k); j>0; j--){ // 逆序
dp[j] += dp[j-1];
}
}
return dp[k];
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/
分享到:
相关推荐
C#,二项式系数(Binomial Coefficient)的七种算法与源代码 二项式系数(binomial coefficient),或组合数,在数学里表达为:(1 + x)ⁿ展开后x的系数(其中n为自然数)。从定义可看出二项式系数的值为整数。 二项...
二项式二项式系数。 如果参数都是非负整数且 0 <= K <= N,则BINOMIAL(N, K) = N!/K!/(NK)!,这是不同集合的数量可以从 N 个不同的对象中选择 K 个对象。 当 N 或 K(或两者)是 ND 矩阵时, BINOMIAL(N, K) ...
二项堆(Binomial Heap)的c语言完全实现,包括添加,删除,和找到最小值,删除最小值
二项式_系数 计算二项式系数的三种不同方法。 使用阶乘的朴素方法乘法方法,这是最有效的方法帕斯卡三角法
给定 m <= n 的非负整数 m 和 n,该程序计算二项式系数 C(n,m)。 是时候有人编写代码来做到这一点了! 我在任何地方都找不到。
二项式系数 var binomial = require ( 'binomial' ) ; binomial ( 4 , 2 ) ; // => 6 binomial ( 10 , 3 ) ; // => 120 执照 麻省理工学院许可证 (MIT) 版权所有 (c) 2014 Olivier Wietrich 特此授予任何人免费...
Binomial distribution calculator是一款好用的二项式分布计算器,主要用于计算二项式分布的概率,只需输入相关的参数就可执行相应的操作生成对应的图形。软件绿色免安装,操作简单,欢迎下载
eager binomial heaps python实现。使用双向链表,make_heap, insert, merge, find_min, extractMin.
二项式摆动应用程序计算二项式系数的线程化 Java Swing 应用程序
这是《算法导论》中第19章二项堆的源代码实现,在VC6.0下编译通过,包括插入、删除、提取最小结点等操作实现。
二项式GPU 这个包提供了一个rand_binomial!函数rand_binomial! 生产CuArrays与二项分布的条目,类似于CUDA.rand_poisson! 适用于Poisson发行的广告。安装使用内置的包管理器: import Pkg; Pkg . add ( " ...
1. Basic counting principle 3. Combinations: Binomial coefficient 二项系数 4. Binomi
二项式抽样 二项分布的采样算法 入门 安装 $ npm install binomial-sampling 如何使用 var binomial = require ( 'binomial-sampling' ) ; // binomial(n, p) // n is the size of sample // p is the ...
欧洲二项式期权定价R 以par-binomial.R的并行CPU使用为例 快速开始: 提供以下功能: binomial_option( type , sigma , T , r , X , S , N ) 在哪里: type :欧洲看跌期权为“放盘”,欧洲看涨期权为“看涨” ...
负二项回归属于广义线性回归(GLM)的分支,与...负二项回归家族庞大,逐渐应用于社会科学领域各个学科的统计分析建模之中,本书详细介绍了负二项回归分析的原理以及该模型的多种变体,为该方法的学习提供了重要指导。
负二项式随机变量 创建一个或数组,其中填充了来。 安装 $ npm install distributions-negative-binomial-random 要在浏览器中使用,请使用 。 用法 var random = require ( 'distributions-negative-binomial-...
安装$ npm install distributions-binomial-mean 要在浏览器中使用,请使用 。用法 var mean = require ( 'distributions-binomial-mean' ) ;均值(n,p [,选项]) 计算参数为n和p的分布的。 (元素方面)。 n可以...
二项堆(Binomial Heap)是二项树(Binomial Tree)的集合(collection)
test_binomial_proportions 测试所有给定的比例是否来自相同的(指定的)二项分布。 该函数还检测不是来自该分布的比例。 输入- n - m 元素向量,包含每个比例的观察数; - k - m 元素向量,包含每个比例的成功次数...
二项式系数 动态编程 算法 有关更多信息: :