python - 在 0's and 1' 的矩阵中查找路径

Question

最近我遇到了以下面试问题？

问题:给定一个包含 M 行和 N 列的二维矩阵。您最初位于 (0,0)，即数组的左上角单元格。您可以向右或向下移动。该数组由 1 和 0 填充。 1 表示您可以在该单元格中移动，0 表示您无法在该单元格中移动。返回从左上角单元格到右下角单元格的路径数(即(0,0)到(M-1,N-1))。由于答案可能很大，因此您必须返回 ans%(10^9+7)。

谁能告诉我如何处理或任何可能有帮助的算法？

编辑:

I have an approach 
1.Start with the top-left cell,initialize count=0
do 
2.Check if 1 exists in adjacent right or adjacent down cell.
3.Add the tuple (i,j) in the stack and choose the right path.
4.If we reach the bottom right cell , update count and pop from stack and go to that position (i,j).
while(stack is not empty)
5.Print count

我想知道是否有人有其他方法？

Answer 1

您可以将您的问题建模为 Directed Acyclic Graph (DAG) ，然后您正在查找从顶点 s 到顶点 t 的路径数，这在 DAG 中使用 Dynamic Programming (DP) 很容易做到.

在这里，将使用以下伪代码来完成:

D(0,0) = 1 
D(x,y) = 0                      if x < 0
D(x,y) = 0                      if  y < 0
D(x,y) = 0                      if matrix[x][y] = 0
         D(x,y-1) + D(x-1,y)    Otherwise

通过上面的动态规划方法，您将得到一个矩阵，其中D(x,y)表示从(0,0)开始的路径数到 (x,y)，您的解决方案是 D(n,m)。

该解决方案的时间复杂度为O(n*m)

<小时/>

实现这个解决方案是留给你的，因为在了解它是如何完成的之后，它应该相当容易。