为什么这个组合解不等同于寻找“路径”数目的递归解呢？

Question

问题是：

给定一个m数组，获得从左上角到右下角的不同路径的数目，如果您只能向下、向右和对角向下移动的话。

这是我的回忆录递归解决方案，相对简单。这是因为从位置到位置的路径数(m1，n1)等效于#路径一个单元到右边+#路径一个单元向下+#路径一个单元对角线：

def numberOfPaths(m, n, cache = {}):
    if (m < 1 or n < 1):
        return 0
    if (m == 1 and n == 1):
        return 1
    if ((m, n) not in cache):
        cache[(m, n)] = numberOfPaths(m - 1, n, cache) + numberOfPaths(m, n - 1, cache) + numberOfPaths(m - 1, n - 1, cache)
    return cache[(m, n)]

现在我想写一个组合解。如果没有对角线，这会很容易。你必须把m-1单位移到右边，n-1单位向下，所以组合的数量只是(m-1+n-1)选择(m-1)。

对角线使它变得有点复杂，但我想我可以得到具有0对角的#路径+1对角+.+有min(m，n) -1对角的#路径(因为这是可能的最大对角线数；如果有更多的对角线，那么对角线就会从网格中消失)。

要计算每个项，我只需做(m +n-2-d)选择d(因为有m+n-2-d位置，右、下、对角可以转到对角线占据两个点)，然后乘以(m +n-2-2* d)选择(m-1-d) --你可以安排剩余的向下/右移动的方式的数目。

def combinatorial(m, n):
    factorial = math.factorial
    def combination(n, k):
        return factorial(n) / (factorial(k) * factorial(n - k))
    paths = 0
    for i in range(0, min(m, n)):
        # for 0 through min(m, n) - 1 diagonals,
        # sum up the number of combinations that exist with that number of diagonals
        paths = paths + combination(m + n - 2 - i, i) * combination(m + n - 2 - 2 * i, m - 1 - i)
    return int(paths)

这在很多情况下都有效(特别是方形网格)，但是为什么在某些输入上失败--例如，m= 18，n= 88？numberOfPaths返回399615234030198251385775，而combinatorial返回3996152340198283304960(稍微大一点)。有小费吗？

Answer 1

明白了。原来这是由于combination函数中浮点不精确所致。我把这一职能改为：

def combination(n, k):
    return factorial(n) // factorial(k) // factorial(n - k)

现在起作用了。恢复了理智。