我被算法优化困住了。
目标是找出在棋盘上从 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 板找到解决方案。
有人有想法吗?
最佳答案
这样想:因为你的点 A 和 B 在同一个地方,你必须移动相同数量的 UPs 和 RIGHTs,但顺序会不同。所以你需要找到不同组合的数量。
关于python - 在不回溯的情况下找到从板的一个角到另一个角的许多唯一路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15451366/