Python中的Project Euler #15

Question

我刚开始学Python，正在做Project-Euler的第15题，遇到了一些困难，想在合理的时间内解决这个问题。问题出在memoize函数上。如果不使用memoize，代码运行得很好，但只适用于小的网格。我尝试使用了记忆化（Memoization），但这样的代码在所有网格中返回的结果都是“1”。

def memoize(f): #memoization
    memo = {}

    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper


@memoize
def search(node):
    global route
    if node[0] >= k and node[1] >= k:
        route += 1
        return route
    else:
        if node[0] < k + 1 and node[1] < k + 1:
            search((node[0] + 1, node[1]))
            search((node[0], node[1] + 1))
    return route


k = 2 #grid size
route = 0
print(search((0, 0)))

如果我注释掉代码来禁用memoize函数：

#@memoize

所有功能都正常，但对于大网格来说速度太慢。我到底哪里做错了？请帮我调试一下。非常感谢！

更新1：

感谢大家的帮助，我也找到了答案：

def memoize(f):
    memo = {}

    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper


@memoize
def search(node):
    n = 0
    if node[0] == k and node[1] == k:
        return 1
    if node[0] < k+1 and node[1] < k+1:
        n += search((node[0] + 1, node[1]))
        n += search((node[0], node[1] + 1))
    return n

k = 20
print(search((0, 0)))

问题并不在memoize函数上，正如我之前认为的那样。问题出在“search”函数上。如果不使用全局变量，它就能正常工作，正是我想要的。感谢大家的评论，真的很有用。

Answer 1

这个问题可以通过下面的代码在常量时间内解决，也就是说，不管输入多大，解决的速度都是一样的：

from math import factorial as f
n, m = map(int, input("Enter dimensions (separate by space)?").split())
print ("Routes through a", n, "x", m, "grid", f(n+m) // f(n) // f(m))

这里有一个链接，可以证明这个公式的正确性： Project Euler 问题 15 的解决方案

Answer 2

试试这个代码。即使是超过1000x1000的网格，它运行得也很快！不一定要是正方形的。不过我当时还不知道什么是记忆化...

import time
def e15():
    x=int(input("Enter X of grid: "))
    y=int(input("Enter Y of grid: "))
    start = time.time()
    lst=list(range(1,x+2))
    while lst[1]!=y+1:
        i=0
        for n in lst[1:]:
            i+=1
            lst[i]=n+lst[i-1]
    print(f"There are {lst[-1]} routes in {x}x{y} grid!")
    end = time.time() - start
    print("Runtime =", end)
e15()

Answer 3

你的记忆化函数在这个问题上是没问题的。不过如果是更一般的情况，我会使用这个：

def memoize(f):
    f.cache = {}                         # - one cache for each function
    def _f(*args, **kwargs):             # - works with arbitrary arguments
        if args not in f.cache:          #   as long as those are hashable
            f.cache[args] = f(*args, **kwargs)
        return f.cache[args]
    return _f

实际的问题是——正如Kevin在评论中提到的——记忆化只在函数没有副作用的情况下有效。虽然你的函数确实有return返回结果，但在递归计算中你并没有使用这个返回值，而是依赖于增加全局计数器变量。当你通过记忆化得到一个早期的结果时，那个计数器就不会再增加了，而且你也没有使用返回的值。

你需要修改你的函数，让它把递归调用的结果加起来，这样就能正常工作了。

你还可以稍微简化一下代码。特别是，在递归调用之前的if检查其实是没必要的，因为你已经在检查>= k了。你应该检查x组件或者 y组件是否>= k，而不是两个都检查；只要有一个达到了k，就只剩下一条通往目标的路了。此外，你可以尝试从0开始倒数，而不是往上数到k，这样代码就不需要k了。

@memoize
def search(node):
    x, y = node
    if x <= 0 or y <= 0:
        return 1
    return search((x - 1, y)) + search((x, y - 1))

print(search((20, 20)))