我在 Project Euler 中偶然发现了一个问题,https://projecteuler.net/problem=15 .我通过组合学解决了这个问题,但我想知道是否有动态编程解决方案来解决这个问题或这些类型的问题。并说网格的一些正方形被取消了 - 可以导航吗?我正在使用 Python。我该怎么做?任何提示表示赞赏。提前致谢。
最佳答案
你可以做一个简单的回溯并探索这样一个隐式图:(评论解释了大部分)
def explore(r, c, n, memo):
"""
explore right and down from position (r,c)
report a rout once position (n,n) is reached
memo is a matrix which saves how many routes exists from each position to (n,n)
"""
if r == n and c == n:
# one path has been found
return 1
elif r > n or c > n:
# crossing the border, go back
return 0
if memo[r][c] is not None:
return memo[r][c]
a= explore(r+1, c, n, memo) #move down
b= explore(r, c+1, n, memo) #move right
# return total paths found from this (r,c) position
memo[r][c]= a + b
return a+b
if __name__ == '__main__':
n= 20
memo = [[None] * (n+1) for _ in range(n+1)]
paths = explore(0, 0, n, memo)
print(paths)
关于python - 导航网格,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48464979/