arrays - 使用动态规划和一维数组的二项式系数

Question

大多数使用动态规划的二项式系数计算的实现都使用二维数组，如以下示例所示: 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) 的复杂性，而二维逻辑具有 O(nr) 的复杂性。

我是不是漏掉了什么？

Answer 1

如果你想要所有的值，那么二维逻辑肯定更有效。二维逻辑对于某些硬件上的某些参数可能更有效，例如，缺少硬件乘法和除法。在除法之前乘法时必须小心整数溢出，而二维循环中的整数加法总是没问题的。除此之外，不，一维递归更好。