首页 > 代码库 > compute Binomial Coefficient or combinations with dynamic programming
compute Binomial Coefficient or combinations with dynamic programming
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 def ComputeBinomialCoefficients(n,k):2 # ComputeBinomialCoefficients(5,2) shoud return 103 table = [0] * (k+1)4 table[0] = 15 for i in range(1, n+1):6 for j in range(min(i,k), 0, -1): # why begin with min(i,k): 1) we do not need any results more than k. 2) Yang Hui (Pascal) Triangle: j must be less than i7 table[j] = table[j] + table[j - 1] # this comes from YANG Hui Triangle (or Pascal Trianle) of Binomial Coefficients8 9 return table[k]
referece:
http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/
http://en.wikipedia.org/wiki/Pascal%27s_triangle
compute Binomial Coefficient or combinations with dynamic programming
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。