[奇技淫巧] 路径组合计数问题的线性递推解法

Prev 0. 引入

试看如下例题：

假设某小区的道路组成了一个的网格结构（每条路就是一条横向或纵向排列的线段），小明住在网格左下角的处，他想到达网格右上角的处拜访好友。若小明采取最短路径移动，那么请问总共有多少条可能的路径？

非常明显，这是一道组合数的题目。根据题目条件，很容易知道最短路径的长度是，即只向右或向上走到终点。那么总共的路径条数就是“从总共的步中选出步向右（或选出步向上）的总组合数”，答案就是条（或条）。

但是，如果我们将方格稍作改动，变成如下的形式：

就很欢愉了~

接下来讨论用线性 DP 的思想（线性递推）来解决包括以上两道经典例题以内的路径计数问题。

Div 1. 线性递推

开始之前先对“最佳路径”进行一个简单的定义：从给定终点到给定终点的最短路径；并定义“ 最佳路径”为从给定起点开始，经过点，到达给定终点的最佳路径。

这里的线性递推指的是由先前已知的状态，通过特定的计算方式得出当前状态的过程。在此类问题中表现为“用只走一步就可转移到当前格点的前驱格点的路径总数进行加法运算得到从起点开始并以当前格点为终点的路径总条数（满足路径为最佳路径）”。

空说比较晦涩，我们以上一节的第一个题为例实操一下：

例 1.1

问从点到点的最佳路径总数是多少？

刚刚我们已经从组合数角度探讨了本题的解法。接下来从线性递推的角度思考这道题。

考虑到“最佳路径”的定义，小明每次只能从某个格点移动到它上边或者是右边的点，换句话说：对于某个点（起点除外），小明只能从它左侧（最左一列除外）或者是下边（最下一行除外）相邻的点走过来。那么以当前点为终点的最佳路径条数就是左侧点的最佳路径条数与下边点的最佳路径条数之和。如此递推到点，就可以求出答案。

考虑到有一些特殊点（最左边一列、最下边一行），由于这一列/行的点只能由起点沿一条直线走过来，所以这些点的最佳路径总数都是。有了初始值，我们就可以依次递推了。特殊地，我们把起点的最佳路径总数设为。递推结果如下图：

右上角的就是答案，不难发现，除开上述特殊位置外，每个点的最佳路径总数就是它左边点和下边点的最佳路径之和。相比于普通的组合数法，这个方法在网格规模较大时计算次数较多（因为必须要枚举网格上个点，除去特殊位置也有个普通点）；但优点是计算量小（仅使用了加法）、无需重复计算。大家可以根据考题数据来选用合适的方法。

接下来探讨求有限制的最佳路径问题。

例 1.2

求由到经过点的最佳路径条数

这个问题可以分割为两个部分——从到、以及从到。对于前一个子问题，我们只需要将递推进行到点即可，的最佳路径条数共条；接下来，把作为新起点，作为新终点，此时的最佳路径条数是条，根据分布乘法原理，的总最佳路径条数为 ~~我还能说什么呢，曼巴出去~~。

如果用组合数原理求解，也是需要分解成上述两个子问题，计算起来就是。

Div 2. 缺刻网格

~~缺刻简直是学生物学的（确信）~~

我们接着来解决刚才提到的另一个网格路径计数问题：

例 2.1

求出从点到点的最佳路径总数

这个网格不再是一个完整的网格，而是缺了一角。放在生活中也很常见，道路维修之类的……接下来先探讨组合数解法（考纲内解法）。

首先，最短路径肯定是步（），但是这里绝对不是简简单单的或者了。当小明从点出发向右移动一格后，留给他的选择就只有朝上了。那么正难则反，用反向法求解。

如果这个网格是一个完整的网格，那么就是条最佳路径。如图，有两个点不能走，减去经过这两个点的最佳路径总数，也就是。接下来，由于去除了两个方格，空缺处上边的两个点显然是不能直接从下边走上去的，需要减掉。除此之外，还有一条从点出发，向右走两格（到达被删去的点之一），向上走一格，再向右走一格到达右下角点的路径，显然也是不合法的，再减去。因此答案是条。