矩阵中的路径数

Question

甲 p x q尺寸矩阵给出,和大小的矩阵a x b从右上角除去.找到总数没有.从左上角到右下角的路径,只允许向右和向下移动.没有路径应该进入移除的矩阵.

例如-

 _
|_|_
|_|_|

这是从右上角(2x2)移除矩阵后的(1x1)矩阵.没有.方式 - 5.

我能够找出路径的总数,但我想要消除进入被删除部分的路径的方法是非常基本的,因此效率不高.

那么,有没有更好的算法呢？

Answer 1

您可以利用网格的结构:

方形网格上从一个角到另一个角的路径数由pascal三角形的网格大小给出: (x+y) choose x

每条路径必须恰好跨越每个对角线上的一个点.

取对角线上穿过内角的所有点,计算通过每个点的路径数量和总和.

这导致O(min(p-a, q-b))假设恒定时间算法的算法.

你的情况:(两个路径到中心)*(从中心两个路径)+(通过拐角一个路径)=(四个路径通过中心)+(通过拐角一个路径)=(5个路径)

+-+-+
| | |
+-+-A-+-+
| | | | |
+-B-+-+-+
| | | | |
C-+-+-+-+
| | | | |
+-+-+-+-+

  (1+2) choose 1 * (2+3) choose 2 (through A)
+ (2+1) choose 2 * (3+2) choose 3 (through B)
+ (3+0) choose 3 * (4+1) choose 4 (through C)

= 3 choose 1 * 5 choose 2
+ 3 choose 2 * 5 choose 3
+ 3 choose 3 * 5 choose 4

= 3*10
+ 3*10
+ 1*5

= 30+30+5 = 65 paths

Answer 2

在代表问题的DAG ¹上进行拓扑排序.

然后从最后(接收器)迭代到第一个(源):

f(v) = Sum(f(u)) for each (v,u) in E
base: f(sink) = 1

复杂性在图形的大小上是线性的(每个顶点恰好迭代一次)(使用矩阵的维度O(p*q-a*b))

(1)图G =(V,E)是:

V = { (i,j) | for each i,j in the matrix that was not deleted }
E = { ((i1,j1),(i2,j2)) | (i1,j1) is to the left/up of (i2,j2) }