Skip to content

Latest commit

 

History

History
 
 

061. Unique Paths

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

刚看到这道题,有点摸不着头脑。你说最短路径,我可以想到 Dijkstra,但你问有多少种,的确有点懵。

我觉得,还是需要先简化问题:走到 End 需要多少步,那么 走到 End 的前一格,需要多少步?

这样的问题,突然就让我想到了背包问题,OK,动态规划。这样往前推演,你会发现,我们能够总结这样一张地图:

qq20141112-1 2x

别看画的潦草,那可都是我一步一步数出来的。(是的,就是这么笨,要不然今天这会才提交?)

说明一下:格子上的数字,是从start开始走,到这个格子的路径个数。连线咋回事?连线的两个格子,相加可以推算出线右下的那个格子所需要的路径个数。这个很容易理解,你要不就是从上面下来的,要不就是从左边横过来的,把这两种可能性加起来,不就是到这个格子的所有可能性吗?

什么?你没看出来动态规划?我们数过的格子,可以被后面的格子直接利用。这难道还不眼熟吗。

有了上面的示意图,我们很容易就写出核心代码。

for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
        steps[j] += steps[j-1];

由于我们只需要知道到 End 的步数,所以我们仅需要存储 End 这一行与其上一行的步数即可。而恰巧,我们是斜边相加。所以我们只需要将最后一行的前一格(真实的最后一行值)与自身(还处于倒数第二行的值)相加即可。故一个数组搞定。

还有就是,对于第一行,第一列,都是无需计算的,因为都是 1. 而想让上面那个双层for循环更加高效,我们假设的是m < n的。就如题意里给出的 3*7 一样。但是这是无法保证的。

针对这两种情况,我们需要判断:

if (m > n) std::swap(m, n); // 如果m比n大,交换之。并不影响结论。
if (m < 2) return m; // 如果m == 0,那么不存在什么path,如果 m == 1,那么自古华山只有一条道。

由于第一行第一列的特殊性,还可以在循环时忽略i == 0 和 j == 0的情况。