动态规划求解棋盘骑士停留概率的计算错误排查

我正在解决LeetCode上的「骑士在棋盘上的概率」问题：给定n、k、row和column，求初始位于[row,column]的骑士在k步后仍停留在n×n棋盘上的概率。我采用累加思路，用动态规划数组dp[x][y][k]记录k步后到达[x,y]的路径数，将k步时所有单元格的路径数求和后除以8^k得到概率。但以n=4、起点[0,0]为例：第一步的结果正确，但第二步求和得16，概率为16/8²=0.25，实际正确答案为0.125；第三步求和得46，概率为46/8³≈0.0898，实际正确答案约为0.039。请问该动态规划思路的错误出在哪里？

第一步后路径数矩阵： #

0   0   0   0
0   0   1   0
0   1   0   0
0   0   0   0

第二步后路径数矩阵： #

4   0   2   0
0   0   0   2
2   0   0   0
0   2   0   4

第三步后路径数矩阵： #

0   6   0   0
6   0   11  0
0   11  0   6
0   0   6   0

第二步计算示例说明 #

以回到起点[0,0]为例，第一步到达的两个位置[1,2]和[2,1]，每个位置都有2种走法能回到[0,0]，所以累计4种路径，对应第二步矩阵中[0,0]的值为4。

错误核心原因 #

你的DP递推逻辑错误地将已经出界的路径也算入了后续步骤的路径累加中。

骑士的每一步移动如果跳出棋盘，这条路径就已经失效，不再属于“仍在棋盘上”的有效路径，不能再参与后续步骤的计算。但你当前的计算方式，是默认所有可能的前驱位置（包括那些已经出界的位置）都能贡献路径数，实际上应该只从k-1步时仍在棋盘内的位置进行递推。

举个具体例子：n=4时，第一步的有效位置是[1,2]和[2,1]，每个位置路径数为1。计算第二步时，[1,2]的骑士尝试移动时，有部分方向会直接跳出棋盘（比如走到[-1,0]），这些出界的路径应该被彻底丢弃，不能再计入任何第二步的棋盘内位置。但你的计算中，错误地认为每个位置都有8种走法，只要能跳回棋盘的路径都被累加，导致路径数被过度计算。

修正后的正确递推逻辑 #

1. 初始化：dp[0][row][column] = 1（0步时在起点的有效路径数为1）
2. 对于每一步step从1到k：
   • 遍历棋盘内的每个位置(x,y)：
     • dp[step][x][y]等于所有能跳到(x,y)的**棋盘内前驱位置(x', y')**的dp[step-1][x'][y']之和
3. 最终概率 = （k步时所有棋盘内位置的路径数之和） / 8^k

这样就能彻底排除出界路径的干扰，得到正确的结果。

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