4/7 算法题详解:Number of Ways to Traverse 2D Array 计算到达二维阵列对角的方案个数


(hbworld) #1

本视频来自于北美CS刷题神器BitTiger Pro


问题具体描述如下:给出一个二维阵列,计算出有多少种方案可以实现行从二维阵列左上角移动到右下角。要求所有的移动操作只能是向右或者向下。我们给出三种对于5x5阵列可行的三种方案作为示范,如下图所示:

![](data:image/svg+xml;utf8,)

很明显,左边的方案是从左上角方块出发,一路向右,到头后一路向下,最终到达右下角方块。中间的方案是向下走一格,然后向右走一格,然后再向下走一格,如此反复,最终到达目的地。右边的方案则是先向下再向右最后再向下,最终到达目的地。显而易见,方案远不止这三种,所以就需要我们来计算出一共有多少种可能的方案。

关键点

这个问题中,每一步路径轨迹不是向下就是向右,故而到达右下角的方法的数量等于直接进入其上方的方式的数量加上直接到达其左侧的方式的数量。为了计算到达右下方方块有多少种方案,我们有必要引进两个数字来作为箭头指针(arrow pointers),定位方块所处位置。

![](data:image/svg+xml;utf8,)

递归(recursion)

递归看起来像解决这个问题比较好的方法。首先我们定义一下基本情况,即到达左上角的方法数是1(左上角是我们的出发点,当然只有一个方法)。递归的公式是T(i,j)=T(i-1,j)+T(I,j-1),其中i和j就是我们之前提到的引入的两个数字,标记了方块的位置。值得注意的是第一行的方块,由于只能通过向右操作到达,所以他们的到达方法数为1,同理,第一列的方块方法数也是1。然而,递归的方式会引入指数时间复杂度(exponential time complexity),因为他会在同一个位置上,多次执行递归计算。比如假设当我们要计算T(2,2)的结果,所以我们需要递归地计算T(2,1)和T(1,2),为了计算T(2,1)和 T(1,2),都需要计算T(1,1),所以我们计算T(1,1) 2次。

动态规划(Dynamic Programming)

在深度递归调用中重复计算的开销是非常大的。动态规划能在这类问题中起到很大的作用。需要动态规划的重要特征是与子问题相关的解决方案也可能再次出现相同的子问题(即可能出现重复的计算)。

在这个问题中每个方块的路径方案结果都与其上面紧接的方块和紧接着它的左边的方块相关,而且这些方块的方案结果被多次计算,所以这个问题是一个经典的动态规划问题。

我们需要缓存子问题的结果,可以创建一个hash表来缓存已经计算过的结果,所以一个每个子问题只计算一次,前面的例子是一个5x5的阵列。当我们把所有结果放置到阵列中,就可以很轻松地求出最后结果是70,如下图所示:

![](data:image/svg+xml;utf8,)

该算法的时间复杂度为O(mn),其中m是行数,n是列数,而空间复杂度也是O(mn),因为我们需要存储所有子问题产生的结果。

实现代码如下:

![](data:image/svg+xml;utf8,)

要注意一点,语句if(numberOfWays[x][y] == 0)的判断是因为当数组的指定元素中的值如果为0,说明该元素还没计算过,需要通过递归调用方法来求值,否则直接返回值就可以了。

换个思路

这个问题也可以通过一个单一的组合公式(a single combination formula)来解决。接下来让我们尝试对路径继续编码。我们用R表示向右一格,D表示向下一格。很容易我们就可以知道下图中左边的路径为RRRRDDDD,中间的路径是DRDRDRDR,右边的是DDRRRRDD。

![](data:image/svg+xml;utf8,)

从前面的例子中我们发现为了到达右下角的方块,我们需要移动由四个右移动和四个向下移动组成的八个步骤,故而这个问题可以简化为用4个D和4个R来填充8个位置。当我们从数学角度看,这个问题就变成了一个简单的排列组合题:给出8个位置,选出4个放置R(或者D),问题答案就变成了C84的值,当然,当m和n(m是行数,n是列数)不固定的时候,编程公式就可以归纳成Cm+n_2n-1。

思考题

有很多这类问题的衍生题目,我们提出两个作为思考题,请大家在阅读完文章后自行思考。

1)用空间复杂度为O(min(n,m))的方法解决这个问题。提示:只需要首行和首列就可以计算结果。

2)在存在障碍物的情况下解决这个问题,特别是布尔型二维矩阵,其中存在true表示有障碍物。提示:我们既不能从别的方块到有障碍物的方块,也不能从有障碍物的方块到别的方块。


本视频来自于北美CS刷题神器BitTiger Pro

每月更新的BitTiger Pro是一个覆盖了CS和数据科学方向最新高频面试题的精讲视频库。订阅后,你可以在Code Evaluation System亲自练习这道题。

![](data:image/svg+xml;utf8,)