国际象棋国王从(1,1)途经(3,4)到(8,8)的路径数求解

嘿，我来帮你拆解这两个棋盘路径的问题，尤其是第二个国王多方向移动的场景，其实用动态规划就能轻松搞定，咱们一步步来：

问题1：普通棋盘（仅允许向上/向右移动）的路径数 #

首先咱们明确，这里的“普通棋盘”指的是只能**向右（R）或者向上（U）**移动的经典场景。比如从起点$(x_1,y_1)$到终点$(x_2,y_2)$（需满足$x_2\geq x_1$，$y_2\geq y_1$），你需要向右走$(x_2-x_1)$步，向上走$(y_2-y_1)$步，总共走$N=(x_2-x_1)+(y_2-y_1)$步。

这本质是个组合问题：从$N$步里选$(x_2-x_1)$步用来向右（剩下的自然就是向上），所以走法数就是组合数：
$$C(N, k) = \frac{N!}{k!(N-k)!}$$
这里$k$是向右的步数（换成向上的步数结果也一样）。举个例子，从(1,1)到(8,8)，需要向右7步、向上7步，总14步，走法就是$C(14,7)=3432$种。

问题2：国王多方向移动且必须经过指定点的路径数 #

国王可以向右、向上、甚至沿对角线（相当于同时向右+向上）移动，这种情况没法直接用组合数，咱们得用**动态规划（DP）**来算——因为每个点的路径数，都等于能走到它的三个前置点（左边、下边、左下边）的路径数之和。

核心思路：拆分路径 #

因为要求路径必须经过$(3,4)$，那咱们可以把整个路径拆成两段：
总路径数 = 从$(1,1)$到$(3,4)$的路径数 × 从$(3,4)$到$(8,8)$的路径数（乘法原理，两段路径互不干扰）

第一步：计算从$(1,1)$到$(3,4)$的路径数 #

咱们定义$dp[i][j]$为从$(1,1)$走到$(i,j)$的路径数，先定好边界条件：

• $dp[1][1] = 1$（起点本身只有1种方式）
• 第一行（$i=1$，$j>1$）：只能从左边$(1,j-1)$过来（没法向上或走对角线，因为左上方的点不存在），所以$dp[1][j] = dp[1][j-1]$，比如$dp[1][4]=1$
• 第一列（$j=1$，$i>1$）：只能从下边$(i-1,1)$过来，所以$dp[i][1] = dp[i-1][1]$，比如$dp[3][1]=1$

然后一步步算中间点：

• $dp[2][2] = dp[1][2] + dp[2][1] + dp[1][1] = 1+1+1=3$
• $dp[2][3] = dp[1][3] + dp[2][2] + dp[1][2] =1+3+1=5$
• $dp[2][4] = dp[1][4] + dp[2][3] + dp[1][3] =1+5+1=7$
• $dp[3][2] = dp[2][2] + dp[3][1] + dp[2][1] =3+1+1=5$
• $dp[3][3] = dp[2][3] + dp[3][2] + dp[2][2] =5+5+3=13$
• $dp[3][4] = dp[2][4] + dp[3][3] + dp[2][3] =7+13+5=25$

所以从$(1,1)$到$(3,4)$一共有25种路径。

第二步：计算从$(3,4)$到$(8,8)$的路径数 #

咱们可以把$(3,4)$当作新的起点，原终点$(8,8)$对应的新坐标是$(8-3+1, 8-4+1)=(6,5)$，当然直接用原坐标计算也没问题。

定义$dp'[i][j]$为从$(3,4)$走到$(i,j)$的路径数，同样先定边界：

• $dp'[3][4] =1$
• 当$i=3$，$j>4$：只能从左边来，所以$dp'[3][j] = dp'[3][j-1]$，比如$dp'[3][8]=1$
• 当$j=4$，$i>3$：只能从下边来，所以$dp'[i][4] = dp'[i-1][4]$，比如$dp'[8][4]=1$

通过递推计算所有中间点，最终得到$dp'[8][8] = 681$。

第三步：总路径数 #

把两段的路径数相乘：$25 × 681 = 17025$，这就是国王从$(1,1)$到$(8,8)$且必须经过$(3,4)$的总路径数。

通用技巧：国王移动的DP公式 #

以后遇到国王可以向右、向上、对角线移动的路径问题，都可以用这个递推公式：
$$dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]$$
边界条件就是第一行、第一列的点只能从单侧递推，起点为1，这样不管哪两个点，都能一步步算出路径数。

内容的提问来源于stack exchange，提问作者frostpad