【原】算法|计算让汽车路程最近有多少种方法

问题描述

我们现在有一个问题，如下图：

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

这里有16个节点，我们的汽车从起始点节点1出发，到终点节点16，现在相邻的两个节点距离都是相同的，汽车只能走上下左右四个方向（不可以斜着走），我们要求的汽车到终点距离最短的情况下共有多少种方式可以到达终点。

解决方案

首先我们先来观察这个4*4的正方形地图，由于相邻两个节点之间的距离是相同的。我们可以根据矩形的一些性质的出，汽车从节点1开始，只往右走和只往下走，最终到达节点16的所有方法的距离是相同并且最短的。那么我们如何得知一共可以有多少种方法呢？

我们可以把复杂问题简单化，找找有没有什么规律（我们只求最短路程的）。

1

比如只有一个节点的时候，到达终点的方法就只有一种。

1

2

当有两个节点的时候，还是只有一种方法。当两个节点这样放也是一样的。

1

2

我们继续增加节点：

1	2
3	4

当有4个节点的时候，到达终点的方式就有2种（默认左上角为起点，右下角为终点）。

1	2	3
4	5	6

1	2
3	4
5	6

再来看看这两种，第一种我们可以1到2或者1到4。如果1到2，那么到2之后就有的到了2*2的地图，2*2的地图我们也算出有2种方式到达终点因此，2*3的地图很容易就得到有3种方法到达终点。第二中也是一样，1到3之后就是2*2的地图。由此可见，我们可以将这种地图看成一张二维表，我们每走一个节点，剩下的地图就更简单。因此我们也可以从简单慢慢到复杂的。接下来我用二维表来表示一下（节点中的数字代表起点到达这里有几种方法是路程最短）。

1	1	1	1
1	2	3	4
1	3	6	10
1	4	10	20

我们将二维表从1*1慢慢增大到4*4，并且我们发现每一个节点的数字都等于它自己上面的节点的数字加上左边的节点的数字。由此可见，任何一个二维表给我们，我们都可以用这种方法的到起点到终点的所有路程最短的方法的数量。

我们在代码中可以使用递归的方法来完成我们刚刚分析出来的所有计算步骤。

我们将二维表的横坐标和纵坐标作为参数，结果为上面的坐标的方法数加上左边的坐标的方法数。如此结果就得到我们想要的答案。

结语

将复杂的问题简单化分析，有简单到复杂的解决问题，一步一步的找到解题的规律，最后得到答案。