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

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

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

别看画的潦草，那可都是我一步一步数出来的。（是的，就是这么笨，要不然今天这会才提交？）

说明一下：格子上的数字，是从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的情况。