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

a0x5cqrl  于 2021-07-13  发布在  Java
关注(0)|答案(2)|浏览(452)

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

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:内存错误:堆栈溢出我不知道我知道什么,
任何帮助!!

mmvthczy

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]
8fq7wneg

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)

相关问题