路径数网格问题python、内存错误和递归错误：

a0x5cqrl 于 2021-07-13 发布在 Java

关注(0)|答案(2)|浏览(465)

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

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)

这里nxm是一个网格的行和列，但是对于大的输入，例如不好。如果我输入-->18x18的n和m，它会给我一个运行时错误，所以我使用了动态方法

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]

如果我这样做，我有两种类型的错误
错误\u 1:递归错误：获取对象的str时超出最大递归深度
我得到了答案，即-->

sys.setrecursionlimit(100**8)

但在那之后，又出现了一个错误
错误2：内存错误：堆栈溢出我不知道我知道什么，
任何帮助！！

python dynamic dynamic-programming Grid

来源：https://stackoverflow.com/questions/67288188/number-of-path-grid-problem-python-memory-error-and-recursion-error

2条答案

按热度按时间

mmvthczy1#

当你达到你的基本情况下，你应该只是返回值，而不是存储在内存中 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]

赞(0）回复(0）举报 2021-07-13

8fq7wneg2#

这是一个综合问题。你可以计算答案，而不是走整个（非常大的）树。

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)

赞(0）回复(0）举报 2021-07-13

我来回答

路径数网格问题python、内存错误和递归错误：

2条答案

相关问题

热门标签

最新问答