矩形网格走道

网格走描述一类问题，在这些问题中，人们在特定的限制条件下计算穿过给定网格的路径数量。最常见的限制是，只有那些接近目标的移动才是有效的;事实上，这种情况非常普遍，以至于术语“网格游走问题”几乎总是包含这种限制。因此，在接下来的所有部分中，包括“无限制”部分，将始终假设有此限制。

由于网格游走问题的有限状态性质，它们特别适合于从<一个href="//www.parkandroid.com/wiki/problem-solving-dynamic-programming/" class="wiki_link" title="动态规划" target="_blank">动态规划，实际上，许多实用的方法都是从手动执行动态规划算法派生出来的或等效于此。

网格行走问题本身很重要，但也因为许多组合情况可能很重要<一个href="//www.parkandroid.com/wiki/bijection-injection-and-surjection-definition/" class="wiki_link" title="bijected" target="_blank">bijected到一个网格行走问题，从而立即建立他们的解决方案。例如，把<一个href="//www.parkandroid.com/wiki/identical-objects-into-distinct-bins/" class="wiki_link" title="不同的垃圾箱" target="_blank"> $米$相同的对象 $N + 1$不同的垃圾箱等价于遍历 $M \ n$网格。

考虑这个例子问题:

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

在这种情况下，除了距离减小的条件(在这种情况下开尔文只能向上和向右移动)，没有其他限制。

解决这个问题有两个重要的方法。第一次使用<一个href="//www.parkandroid.com/wiki/recursion/" class="wiki_link" title="递归" target="_blank">递归，第二篇文章使用了一个聪明的观察结果，适用于无限制的网格行走变体(但通常不适用于其他情况)。

解决方案1:假设开尔文达到这一点 $(m, n)$在某一时刻。那么开尔文肯定来自其中一个 $(m - 1, n)$或 $(m, n - 1)$(因为他只能向上和右跳)，意思是

路径的数目 $(m, n)$是路径数的和吗 $(m - 1, n)$以及路径的数量 $(m, n - 1)$．

此外，只有1条路径 $(x, 0)$和 $(0, y)$对于任何 $(x, y)$．所以我们可以填写一个表格:

$y =$5 $\水平间距{10毫米}$	1	6	21	56	126	252
$y =$4	1	5	15	35	70	126
$y =$3.	1	4	10	20.	35	56
$y =$2	1	3.	6	10	15	21
$y =$1	1	2	3.	4	5	6
$y =$0	1	1	1	1	1	1
	$x =$0 $\水平间距{10毫米}$	$x =$1 $\水平间距{10毫米}$	$x =$2 $\水平间距{10毫米}$	$x =$3. $\水平间距{10毫米}$	$x =$4 $\水平间距{10毫米}$	$x = 5$ $\水平间距{10毫米}$

所以有252条可能的路径。 $_ \广场$

这种策略对于较大的电网显然是不切实际的，但它有三个主要优势:

• 这种策略即使在面临额外限制的情况下也适用，后面的部分将说明这一点。
• 它也适用于非矩形网格，以及当有更多的移动可供选择时，而不仅仅是向上/向右移动(例如对角线)。
• 这对计算机来说很容易<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/rectangular-grid-walk-no-restriction/">执行，使用简单的动态规划算法。

此外，这种策略还揭示了<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/learn-and-practice-combinatorics-on-brilliant/">组合问题的基础。仔细检查上面的表格可以发现一些有趣的现象:

这有力地表明网格行走与<一个href="//www.parkandroid.com/wiki/properties-of-binomial-coefficients/" class="wiki_link" title="二项式系数" target="_blank">二项式系数．事实上，原因很简单:

解决方案2:达到 $(5,5)$开尔文必须向上跳5次，向右跳5次。开尔文没有其他到达目的地的方法。然而，他可以以任何可能的顺序进行这些移动，每个顺序对应于不同的网格行走。根据二项式系数理论，有 $\ binom {5 + 5} {5} = 252$可能的路径。 $_ \广场$

假设一个粒子从一个物体的左下角运动 $M \ n$网格到右上角，通过沿着网格的边缘做步骤。

确实有 $\ binom {m + n} {n}$控件中从左下角到右上角的路径 $M \ n$网格。

通常,一个<一个href="//www.parkandroid.com/wiki/cartesian-plane/" class="wiki_link" title="笛卡儿平面" target="_blank">笛卡儿平面是叠加在网格上的，这样问题就等价于从 $(0， \， 0)$来 $(m， \， n)$．

考虑另一个问题，创建一个“单词”(任何字母字符串)受某些限制:

1. 单词必须有长度 $M + n$．
2. 只能包含R和U两个字母。
3. 这个词必须包含 $米$R和 $n$你的。

这个问题的答案由二项式系数的定义之一给出:有 $\binom{m + n}{m} = \binom{m + n}{n}$有效的词汇。

现在，请注意，每个单词都描述了一个网格游走 $M \ n$网格，从左下角开始:

1. 正常阅读单词，一次一个字母，从左到右。
2. 每次读到R，向右移动 $1$单元在网格中。
3. 每读取一个U，就向上移动 $1$单元在网格中。

因为这个词包含 $米$R和 $n$U，当单词结束时，网格行走将在右上角结束。以这种方式描述的每个网格行走都是唯一的，因为两个单词中第一个不同的字母被视为两条路径之间的分叉。从左下角到右上角的任何网格移动都可以这样描述，因为每次向右移动都写R，每次向上移动都写U，就可以创建一个有效的单词。

由此可见，这样的网格行走的数量与有效单词的数量相同。所以有 $\binom{m + n}{m}$可能的网格行走。 $_ \广场$

因此，栅格行走“数”表确实等于二项式系数表。有几个组合恒等式可以从这个实现中推导出来，其中之一是<一个href="//www.parkandroid.com/wiki/hockey-stick-identity/" class="wiki_link" title="曲棍球棍身份" target="_blank">曲棍球棍身份．

考虑一个维度的网格游走问题 $(m + 1) \乘以n$，从原点出发，向 $(m + 1 \ n)$．

注意，这样的路径必须沿着线之间的边通过 $X = m$这条线 $X = m + 1$在某个时间点。此外，它必须精确地执行一次。一旦路径到达这条线 $X = m + 1$，只有一种方法可以到达 $(m + 1 \ n)$(向上，向上，向上)。由此可见，网格行走的“数字”之和为 $(m， \， 0)$通过 $(m， \， n)$一定是网格行走的“数字”为 $(m， \， n)$．换句话说，

曲棍球棍的身份

$n \ \ sum_ {k = 0} ^ binom {m + k} {m} = \ binom {m + n + 1} {m + 1}。$

回想一下示例问题:

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

计算机可以用相当直接的方式解决这样的问题。下面是一些Python代码:

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

defdp（米，n，加勒比海盗)：如果米= =0或n= =0：返回1如果米<0或n<0：返回0如果加勒比海盗［米] [n］! =0：返回加勒比海盗［米] [n］加勒比海盗［米] [n］＝dp（米-1，n，加勒比海盗）+dp（米，n-1，加勒比海盗）返回加勒比海盗［米] [n］米＝5n＝5加勒比海盗＝［0］＊（米+1）为我在范围（米+1)：加勒比海盗［我］＝［0］＊（n+1）打印（dp（米，n，加勒比海盗）)

但是，如果只需要计算二项式系数，创建这样一个程序有什么用呢?有时候，网格行走问题有进一步的限制，比如邪恶的怪物和不方便的墙壁，或者额外的允许动作，比如对角线向上和向右的步骤。

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．然而，一个邪恶的怪物住在 $(2, 2)$，所以开尔文不能跳过去。在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

没有一个立即可处理的数学解决方案，特别是当有许多限制条件时。但对于程序来说，只需稍加修改就能解决问题:

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

defdp（米，n，加勒比海盗)：如果米= =0或n= =0：返回1如果米= =2而且n= =2：返回0如果米<0或n<0：返回0如果加勒比海盗［米] [n］! =0：返回加勒比海盗［米] [n］加勒比海盗［米] [n］＝dp（米-1，n，加勒比海盗）+dp（米，n-1，加勒比海盗）返回加勒比海盗［米] [n］米＝5n＝5加勒比海盗＝［0］＊（米+1）为我在范围（米+1)：加勒比海盗［我］＝［0］＊（n+1）打印（dp（米，n，加勒比海盗）)

一个国王能从一个角落走多少条路 $8 \乘8$棋盘到对面的角落?

国王可以向任何方向移动1格，包括对角线。

在本例中，递归如下:

路径的数目 $(m, n)$是路径数的和吗 $(m - 1, n)$，到的路径数 $(m, n - 1)$的路径数 $(m - 1, n - 1)$．

解决方案。

根据新的递归公式对上述程序稍加修改，可得

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

defdp（米，n，加勒比海盗)：如果米= =0或n= =0：返回1如果米<0或n<0：返回0如果加勒比海盗［米] [n］! =0：返回加勒比海盗［米] [n］加勒比海盗［米] [n］＝dp（米-1，n，加勒比海盗）+dp（米，n-1，加勒比海盗）+dp（米-1，n-1，加勒比海盗）返回加勒比海盗［米] [n］米＝8n＝8加勒比海盗＝［0］＊（米+1）为我在范围（米+1)：加勒比海盗［我］＝［0］＊（n+1）打印（dp（米，n，加勒比海盗）)

输出产生答案 $\盒装{265729}。$ $_ \广场$

也有一个数学框架来处理这类问题。

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．然而，一个邪恶的怪物住在 $(2, 2)$，所以开尔文不能跳过去。在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

---

解由<一个href="//www.parkandroid.com/wiki/principle-of-inclusion-and-exclusion-pie/" class="wiki_link" title="包容-排斥原则" target="_blank">包容-排斥原则．

此时，忽略怪物的存在，这样就有252条路径 $(5,5)$．如果路径数为 $(5,5)$都经过了 $(2, 2)$可以计算出，那么有多少呢 $(2, 2)$避免路径可以通过简单的减法计算。

所以有多少条路径 $(2, 2) ?$首先开尔文要从 $(0,0)$来 $(2, 2)$没有限制，这是有的 $\ binom {2 + 2} {2} = 6$方法。然后他就得从 $(2, 2)$来 $(5,5)$也就是从原点跳到 $(3)$，所以有 $\ binom {3 + 3} {3} = 20$这样的路径。因此，有 $6 \cdot 20 = 120$经过的路径 $(2, 2)$，这意味着 $252 - 120 = 132$没有的路径。 $_ \广场$

这就有了另一个公式:

确实有 $\ binom {m + n} {n} - \ binom {a + b} {b} \ binom {(m + n) - (a + b)} {nb}$从原点到 $(m, n)$不经过这个点 $(一,\ b)$．

换句话说，就是从 $\ (0, 0)$来 $(m \ n)$同时避免一个限制点在 $(一,\ b)$是由到达的路径数给出的 $(m \ n)$没有限制，减去到达的路径数 $(m \ n)$都经过了 $(一,\ b)$．

下面的定理提供了一种比较一般的方法<一个href="//www.parkandroid.com/wiki/sets/" class="wiki_link" title="集" target="_blank">集限制点。

一般来说，给定限制点 $S = \{P_1， \， P_2， \， \dots， \， P_k\}$,让 ${Path} \文本(T)$是到达的方法的数量 $\ (0, 0)$来 $(m \ n)$在经过所有的点的时候 $T$．然后,

$(\text{避免路径数}S) = \sum_{T \subsetneq S} (-1)^{|T|} \text{Path}(T)。$

请注意, $\text{Path}(\emptyset) = \binom{m + n}{n}$而且,如果 $P = (a，\，b)$,然后 $\text{Path}(\{P\}) = \binom{(m+n)-(a+b)}{n-b}$．

当 $M = n$， $K = n - 1$, $P_i = (i，\，i)$对所有 $I \le n-1$时，定理转化为(2倍)的公式<一个href="//www.parkandroid.com/wiki/catalan-numbers/" class="wiki_link" title="加泰罗尼亚的数字" target="_blank">加泰罗尼亚的数字．

这个定理直接从<一个href="//www.parkandroid.com/wiki/principle-of-inclusion-and-exclusion-generalized/" class="wiki_link" title="广义的包容-排斥原则" target="_blank">广义的包容-排斥原则．直观地说，该定理形式化了这样一个概念:“我们可以到达那里的方法的数量等于到达那里的所有可能方法的数量，减去看起来没有吸引力的方法的数量，加上看起来没有吸引力但我们仍然可以工作的方法的数量，减去看起来没有吸引力但可行的方法的数量，实际上被阻塞了……”换句话说，每个部分和都是计算答案的一次尝试，它比前一个部分和的尝试有所改进。

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．然而，一个邪恶的怪物住在 $(2, 2)$，所以开尔文不能跳过去。另一个邪恶的怪物住在 $(3)$，所以开尔文也不能走过去。在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

---

从上面的问题中，有120条路径经过(2,2)。类似地，有120条路径经过(3,3)，因此两者都从252条无限制路径中减去。然而，这将一些路径减去两次，即经过(2,2)的路径而且(3,3)所以这些必须加回去。有 $\ binom {2 + 2} {2} \ cdot \ binom {1 + 1} {1} \ cdot \ binom {2 + 2} {2} = 72$在这些路径中，总共有 $252-120-120 + 72 = 84$路径。 $_ \广场$

如果网格中有墙(或缺线)，这意味着某些单单元移动是非法的，那么包含-排除论点就变得有点复杂了。例如,

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．然而，两者之间有一堵墙 $(2, 2)$而且 $(2、3)$，开尔文不能跳过去。在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

---

从哪条路出发 $(2, 2)$来 $(2、3)$，它必须从原点移动到 $(2, 2)$，向右移动，然后旅行到 $(5,5)$．有 $\ binom {2 + 2} {2} \ cdot \ binom {3 + 2} {3} = 6 \ cdot 10 = 60$有这样的路径 $252 - 60 = 192$避开墙的路径。 $_ \广场$

确实有 $\binom{a+b}{a} \cdot \binom{(m+n)-(a+b+1)}{n-b}$从这里出发的路径 $\ (0, 0)$来 $(m \ n)$而使用之间的路径 $(一,\ b)$而且 $(+ 1, \ b)$．因此，有确切的 $\ binom {m + n} {n} - \ binom {a + b}{一}\ cdot \ binom {(m + n) - (a + b + 1)} {nb}$从这里出发的路径 $\ (0, 0)$来 $(m \ n)$同时避开中间的一堵墙 $(一,\ b)$而且 $(+ 1, \ b)。$

任何穿过墙的路径都必须到达某个点(在穿过墙之前) $(一,\ b)$．有 $\ binom {a + b}{一}$如何从… $\ (0, 0)$来 $(一,\ b)$．从这一点，有一条路可以到达 $(+ 1, \ b)$，这需要翻墙。从 $(+ 1, \ b)$，有 $\ binom {m + n - a - b - 1} {m - a - 1} = \ binom {m + n - a - b - 1} {n - b}$路径 $(m \ n)$．既然必须避开这堵墙，就有 $\盒装{\ binom {m + n} {n} - \ binom {a + b}{一}\ cdot \ binom {(m + n) - (a + b + 1)} {nb}}$可能的路径。

由上述定理中的公式，对于具有多壁的问题，可以采用类似的方法。特别是，如果 $S = \{W_1， \， W_2， \， \dots， \， W_k\}$是一套墙和 $文本\ {Path} _2 (T)$是多少种方法 $\ (0, 0)$来 $(m \ n)$在研究过程中墙在 $T$,然后

$(\text{避免路径数}S) = \sum_{T \subsetneq S} (-1)^{|T|} \text{Path}_2(T)。$

青蛙开尔文住在原点，并希望拜访他的朋友在 $(5,5)$．然而，两者之间有一堵墙 $(2, 2)$而且 $(2、3)$还有一堵墙 $(3)$而且 $(3、4)$，开尔文不能跳过去。在任何时候，青蛙开尔文只能向上跳一个单位或者向右跳一个单位。从开尔文到他的朋友有多少条路径?

---

从上面的问题来看，有 $60$穿过第一堵墙的路径。类似地，有 $\binom{3 + 3}{3} \cdot \binom{2 + 1}{2} = 60$穿过第二面墙的路径。然而，有 $\ binom {2 + 2} {2} \ cdot \ binom {1 + 0} {1} \ cdot \ binom {2 + 1} {2} = 18$穿过两面墙的路径。因此，有 $252 - 60 - 60 + 18 = 150$路径。 $_ \广场$

当标准移动(向右和向上)之外的移动可用时，递归方法通常优于双射方法。即使存在简单的双射，发现它通常也需要分析递归。例如,

一个国王能从一个角落走多少条路 $8 \乘8$棋盘到对面的角落?

国王可以向任何方向移动1格，包括对角线。

---

有可能解决这些运动的一般情况，称为king-walks，在 $N \乘N$网格。然而，并没有一个封闭的形式，当只有两种可能的移动类型时，表达式也不一样。

总之，多走王者之路 $(n, n)$是

$n \ \ sum_ {k = 0} ^ binom {n} {k} \ cdot \ binom {n + k} {k}。$

注意，如果我们知道有多少次向右移动，我们也就知道有多少次向上移动;一定有相同的数字。此外，向右移动的次数加上对角线移动的次数必须为 $n$．所以如果有 $k$右移，然后我们可以计算移动的次数<一个href="//www.parkandroid.com/wiki/combinations/" class="wiki_link" title="结合" target="_blank">结合，知道有 $n + k$移动总: $n - k$对角线移动时, $k$右移，然后 $k$移动。对所有可能的值求和 $k$，天桥的数量应该是

$n \ \ sum_ {k = 0} ^压裂{(n + k) !} {k k (n - k) ! ! !{\sum_{k=0}^n \frac{n!}{(n-k)!k!} \cdot \frac{(n+k)!}{n!k!｝＝n \ \ sum_ {k = 0} ^ binom {n} {k} \ cdot \ binom {n + k} {k}。\ _ \广场$

• 动态规划
• 相同的对象放入不同的箱子
• 包容与排斥原则
• 递归