二项式系数

Question

大多数使用动态编程二项式系数计算的实施方式利用了2维阵列，在这些例子中： http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm

http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/

我的问题是，为何不只是使用的一维阵列是这样计算它：

def C(n, r): 
    memo = list() 
    if (r > int(n/2)): 
     r = n - r 
    memo.append(1.0) 
    for i in range(1,r+1): 
     now = ((n-i+1)*memo[i-1])/i 
     memo.append(now) 
    return memo[r] 

基本上使用递归公式： C（n，r）=（（n-r + 1）/ r）* C（n，r-1）

这具有O（r）复杂性，而2维逻辑具有O nr）复杂性。

我在这里错过了什么吗？

Answer 1

如果你想要所有的值，那么2D逻辑当然更有效率。对于某些硬件上的某些参数，例如缺乏硬件乘法和除法，2D逻辑可能更有效。在分割之前相乘时必须小心整数溢出，而2D重复中的整数加法总是很好。除此之外，不，一维复发更好。