number of path grid problem Python, Memory Error and Recursion Error:

Question

所以我试图解决一个简单的网格问题，我是这样解决的：\

def grid_count (n,m):
    if m == 1 and n == 1:
        return 1
    if m == 0 or n == 0:
        return 0
    return grid_count(m-1,n) + grid_count(m,n-1)

这里 N X M 是网格的行和列，但不适合大输入例如。如果我为 N 和 M 输入 --- > 18X18 它会给我一个运行时错误所以我用了动态方法和

dic ={}
def grid_count (n,m):
    # key  = str(n)+","+str(m)
    key = n*m
    if key in dic:
        return dic[key]
    if m == 1 and n == 1:
        dic[key] = 1
    if m == 0 or n == 0:
        dic[key] = 0
    dic[key] = grid_count(m-1,n) + grid_count(m,n-1)
    return dic[key]

如果我这样做，我会遇到两种类型的错误

error_1 1：递归错误：获取对象的 str 时超出最大递归深度

我得到了答案即 --- >

sys.setrecursionlimit(100**8)

但之后又出现了一个错误

error_2 2：内存错误：堆栈溢出我不知道我知道什么，

任何帮助!!

Answer 1

当您达到基本情况时，您应该 return 值而不是将其存储在 dic 中。:

    if m == 1 and n == 1:
        return 1
    if m == 0 or n == 0:
        return 0

或者，您可以使用已知值初始化 dic：

dic = {0: 0, 1: 1}
def grid_count (n,m):
    key = n*m
    if key in dic:
        return dic[key]
    dic[key] = grid_count(m-1,n) + grid_count(m,n-1)
    return dic[key]

Answer 2

这是一个组合问题。您可以计算答案而不是遍历整个（非常大的）树。

from math import factorial

def grid_count(n,m):
    if m == 1 and n == 1:
        return 1
    if m == 0 or n == 0:
        return 0
    return grid_count(m-1,n) + grid_count(m,n-1)

def grid_calc(n,m):
    m -= 1
    num = factorial(m + n - 1)
    den = factorial(m) * factorial(n - 1)
    return num//den

for c in [grid_count, grid_calc]:
    print(c(12,12))

时间是

%%timeit
grid_count(12,12)
# 364 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
grid_calc(12,12)
# 503 ns ± 3.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

number of path grid problem Python, Memory Error and Recursion Error:

number of path grid problem Python, Memory Error and Recursion Error:

python

grid

dynamic

dynamic-programming