网格20x20的格子路径算法未能完成运行

Question

我写了以下的Python代码来解决Project Euler的第15个问题：

grid_size = 2
def get_paths(node):
        global paths

        if  node[0]  >= grid_size and node[1] >= grid_size:
                paths += 1
                return
        else:
                if node[0]<grid_size+1 and node[1] < grid_size+1:
                     get_paths((node[0]+1,node[1]))
                     get_paths((node[0],node[1]+1))
        return paths

def euler():
                print get_paths((0,0))

paths = 0
if __name__ == '__main__':
    euler()

虽然在一个2 X 2的网格上运行得很好，但在一个20 X 20的网格上却已经运行了好几个小时。有什么办法可以优化我的代码，让它在更大的网格上也能运行得快一点呢？这算不算是一种广度优先搜索的问题？（我觉得是的。）

我该如何评估我当前解决方案的复杂度呢？

Answer 1

在解决Project Euler上的问题时，建议在开始编码之前，先仔细思考一下问题背后的数学原理。其实这个问题可以完全不需要写代码就能解决。

我们要计算通过一个网格的不同走法。如果你注意到，不管走哪条路，向下（down）和向右（right）的移动次数是固定的，那么你只需要关注你是先向下走还是先向右走。因此，在2x2的情况下，以下几种组合都是可行的：

DDRR 
DRDR
RDRD
RRDD
RDDR
DRRD

注意，如果我们先决定了R（向右）的移动位置，那么D（向下）的移动位置就自动确定了。所以实际上，我们只需要从4个可用的移动位置中选择哪些位置放R移动。你能想到什么数学运算可以做到这一点吗？

Answer 2

你可能需要了解一下这个问题背后的数学原理。其实并不需要真的去遍历所有的路线。（实际上，你这样做是无法在1分钟内完成的）。

我可以给你一个提示，但除非你请求，否则我不会主动给，因为我不想破坏你的思路。

编辑：是的，你现在使用的算法永远不会是最优的，因为没有办法减少你问题的搜索范围。这意味着（正如pg1989所说的）你需要寻找其他解决这个问题的方法。

正如sverre所说，看看这里可能会给你一些启发：http://en.wikipedia.org/wiki/Binomial_coefficient

这里可以找到一个直接的解决方案（警告，剧透很大）：

http://www.joaoff.com/2008/01/20/a-square-grid-path-problem/

Answer 3

你的算法效率很低，主要是因为你对相同的输入重复计算了很多次 get_paths。要解决这个问题，可以使用一种叫做 记忆化 的方法，这样可以让它运行得更快。另外，你还需要去掉全局变量，改用返回值来处理。你也可以看看动态规划，这里有类似的思路。