python - 在不回溯的情况下找到从板的一个角到另一个角的许多唯一路径

Question

我被算法优化困住了。

目标是找出在棋盘上从 A 点到 B 点可以使用多少种不同的方法，其中:

• A 是左下角的正方形。
• B 是右上角的正方形。
• 棋子每回合只能向上或向右移动一格。

这是一个虚拟的解决方案:

# -*- conding: utf-8 -*-
import time

def solution(n, m, x, y):
   ret = 0
   if x < n-1:
      ret += solution(n, m, x+1, y)
   if y < m-1:
      ret += solution(n, m, x, y+1)
   if x == n-1 and  y == m-1:
     ret = 1
   return ret

def wrapper(n, m):
    start = time.time()
    reponse = solution(n, m, 0, 0)
    stop = time.time()
    print "Response: %dx%d = %d\nTime : %f\n" % (n, m, reponse, stop-start)



if __name__ == "__main__":
    for i in range(10):
        wrapper(i+1,i+1)
    #wrapper(7,7)
    #wrapper(10,10)
    #wrapper(100,100)
    #wrapper(1000,1000)
    #wrapper(10000,10000) <- way too slow

虽然我留在小棋盘上，但它工作正常并且结果相关。但我的目标是为 10000x10000 板找到解决方案。

有人有想法吗？

Answer 1

这样想:因为你的点 A 和 B 在同一个地方，你必须移动相同数量的 UPs 和 RIGHTs，但顺序会不同。所以你需要找到不同组合的数量。