algorithm - 计算迷宫中唯一路径的数量

Question

我知道计算矩阵中路径 [0,0] 到 [n,n] 的回溯方法。但无法通过动态规划解决。没有回溯甚至可能吗？？

你只能向右或向下移动

1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
`

从左上角到右下角的路径数是4

Answer 1

是的。假设 p(i,j) 是到 i,j 的部分路径的数量。如果我们使用零索引那么你想要的是 p(n-1,n-1)。你所知道的是 p(0,0)=1，如果你可以从 p(i-1,j) 移动到 p(i,j)，那么 p(i,j) 也是左边值的总和, 如果你可以从 p(i,j-1) 移动到 p(i,j)，则上面的值。

因此，您使用所有这些来填充矩阵。 DP 几乎就是这样:矩阵填充。一旦您弄清楚如何填写矩阵，您就大功告成了。