在矩阵路径数 [英] Number of paths in a matrix

问题描述

A PXQ 尺寸矩阵，并给出了大小的矩阵 AXB 从右上角的删除。找到总量不。中从左上到右下，只有右，下允许运动从上路径。没有路径应该进入删除矩阵。

A p x q size matrix is given, and a matrix of size a x b is removed from top right corner. Find the total no. of paths from top left to bottom right, with only right and down movements allowed. No path should go into the removed matrix.

例如： -

 _
|_|_
|_|_|

这是删除（1×1）从右上角的矩阵后（2×2）矩阵。没有。方法 - 5

this is (2x2) matrix after removing (1x1) matrix from top right corner. no. of ways - 5.

我能找到的路径的总数，但该方法我想消除进入去除部分的路径是非常初级的，因此效率不高。

I am able to find out the total number of paths, but the method I am thinking of eliminating the paths that go into the removed portion is very elementary and hence not efficient.

那么，是否有任何更好的算法？

So, are there any better algorithm for it ?

推荐答案

您可以利用电网的结构：

You can exploit the structure of the grid:

的路径的数量从一个角落到另一个在一个方形网格的网格的大小由下式给出了杨辉三角：（X + Y）选择X

The number of paths from one corner to the other on a square grid is given by the size of the grid by the pascal's triangle: (x+y) choose x

每个路径必须跨越正好一个点上的每一个角。

Each path must cross exactly one point on each diagonal.

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

Take all points on the diagonal that passes through the inner corner, calculate the number of paths through each, and sum.

这导致了一个 0（分（PA，QB））算法假设固定时间的算术。

This leads to an O(min(p-a, q-b)) algorithm assuming constant-time arithmetic.

在你的情况：（两个路径到中心）*（从中心两个路径）+（一个路径通过的角）=（通过中心四个路径）+（一个路径通过的角）=（5路径）

In your case: (two paths to the center) * (two paths from the center) + (one path through the corner) = (four paths through the center) + (one path through the corner) = (five paths)

+-+-+
| | |
+-+-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

这篇关于在矩阵路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！