为何棋盘骑士概率问题的递归记忆化解法出错？
问题来源
来自LeetCode的「Knight Probability in Chessboard」题目
问题描述
骑士从指定位置出发，每次随机选择8种可能的移动方式之一，总共移动k次，求最终仍留在棋盘上的概率（每次移动的概率为1/8）。
原解法思路
假设无循环路径且每层有2种有效移动时，概率本质为 $(1/8)^k × 有效路径的叶子节点数$；考虑循环路径时，计划通过记忆化利用深度差计算贡献：若节点x在剩余步数为kOfX时被访问过，其对父节点的贡献为 $(1/8)^{k - kOfX}$。
原代码实现
public class KnightProbabilityInChessboard { class Pair{ int row, col; int k; Pair(int row, int col, int k){ this.row = row; this.col = col; this.k = k; } Pair(int row, int col){ this.row = row; this.col = col; } } // 执行入口 public double knightProbability(int n, int k, int row, int column) { int isVisited[][] = new int[n][n]; double value[][][] = new double[n][n][k + 1]; knightProbabilitycalc2(k , value, isVisited, row, column, new ArrayList<>()); return value[row][column][k]; } // 核心逻辑 void knightProbabilitycalc2(int k, double value[][][], int visited[][], int row, int column, List<Pair> parents) { // 记忆化判断：若节点已被访问，复用已有计算结果 if (visited[row][column] > k && k!= 0) { for(int i = parents.size() - 1; i >= 0; --i){ Pair parent = parents.get(i); double res = Math.pow((1/8.0), parent.k - k - 1) * value[row][column][k]; value[parent.row][parent.col][parent.k - k] += res; } return; } // 未到最后一步，递归搜索后续移动 if(k != 0) { int n = value.length; List<Pair> validMoves = getAllMoves(row, column).stream().filter((move) -> isValid(move.row, move.col, n - 1, n - 1)).collect(Collectors.toList()); parents.add(new Pair(row, column, k)); for (Pair move : validMoves) { knightProbabilitycalc2(k - 1, value, visited, move.row, move.col, parents); } parents.remove(parents.size() - 1); } // 递归结束后，更新所有父节点的概率值 for(int i = parents.size() - 1; i >= 0; --i){ Pair parent = parents.get(i); double res = Math.pow((1/8.0), parent.k - k); value[parent.row][parent.col][parent.k - k] += res; } // 标记该位置当前剩余步数已计算完成 visited[row][column] = k; } List<Pair> getAllMoves(int row, int col){ List<Pair> validMoves = new ArrayList<>(); validMoves.add(new Pair(row - 2, col - 1)); validMoves.add(new Pair(row - 2, col + 1)); validMoves.add(new Pair(row + 2, col + 1)); validMoves.add(new Pair(row + 2, col - 1)); validMoves.add(new Pair(row + 1, col - 2)); validMoves.add(new Pair(row + 1, col + 2)); validMoves.add(new Pair(row - 1, col - 2)); validMoves.add(new Pair(row - 1, col + 2)); return validMoves; } boolean isValid(int r, int c, int maxR, int maxC){ return (0 <= r && r <= maxR && 0 <= c && c <= maxC); } }
问题现象
代码在k≤3时能正确运行，但k≥4时结果严重偏低。例如n=8、k=30时，预期输出0.0019，实际输出为e-25量级。已确认移动生成和有效性检查逻辑无误，问题出在递归记忆化部分。
错误原因分析
记忆化判断逻辑完全错误
原代码用visited[row][column] > k判断是否复用已有结果，但visited是二维数组，仅记录某个位置最后处理的剩余步数k值。实际上，value[row][col][k]表示位置(row,col)剩余k步时留在棋盘的概率，每个(k, row, col)都是独立状态，二维的visited无法区分不同剩余步数的状态，导致错误复用了无关状态的计算结果。比如之前处理过k=5的状态，现在处理k=3时，会错误触发记忆化，复用k=5的结果，而这两个状态完全不同。记忆化时的贡献计算指数错误
触发记忆化时，代码计算贡献用了parent.k - k - 1作为指数，正确的指数应该是parent.k - k（父节点剩余步数减当前节点剩余步数，即从父节点到当前节点走了几步）。指数少1意味着概率被多除以8，直接导致结果被大幅缩小。visited数组设计不合理
由于每个状态是三维的（剩余步数、行、列），仅用二维数组记录无法区分不同剩余步数的状态，应该用三维的标记数组，或者直接检查value[row][col][k]是否已完成计算（比如初始化为-1，计算后赋值，判断是否不等于-1）。
内容的提问来源于stack exchange，提问作者tester test
