问题背景
在一个
n
×
n
n \times n
n×n 的国际象棋棋盘上，一个骑士从单元格
(
r
o
w
,
c
o
l
u
m
n
)
(row, column)
(row,column) 开始，并尝试进行
k
k
k 次移动。行和列是 从
0
0
0 开始 的，所以左上单元格是
(
0
,
0
)
(0,0)
(0,0)，右下单元格是
(
n
−
1
,
n
−
1
)
(n - 1, n - 1)
(n−1,n−1)。
象棋骑士有
8
8
8 种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
每次骑士要移动时，它都会随机从
8
8
8 种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
骑士继续移动，直到它走了
k
k
k 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
数据约束
- 1 ≤ n ≤ 25 1 \le n \le 25 1≤n≤25
- 0 ≤ k ≤ 100 0 \le k \le 100 0≤k≤100
- 0 ≤ r o w , c o l u m n ≤ n − 1 0 \le row, column \le n - 1 0≤row,column≤n−1
解题过程
自己写出了按方向的回溯，但是没有应用记忆化搜索导致超时。不过即使记录的中间过程的结果，答案也是不对的，因为考虑的是求最终所有的有效落点与所有可能落点的比值。事实上递归的过程中，某个状态是依赖于前一个状态的，要计算的是分阶段的概率。
最终记录答案时需要理解两个细节：
- 在不进行更深层次的递归时，当前的操作只可能是八选一。这种情况下概率是可以直接求和的，因为分母相同，等效于有效结果数除以所有可能结果数。
- 上一轮的概率会在记录并返回时被稀释（除以八），符合多步计算使用乘法公式的条件。
其它参考 灵神题解：定义状态
d
f
s
(
k
,
i
,
j
)
dfs(k, i, j)
dfs(k,i,j)，表示从
(
i
,
j
)
(i, j)
(i,j) 出发走
k
k
k 步后仍在棋盘上的概率。若从
(
i
,
j
)
(i, j)
(i,j) 出发，有
1
8
\frac {1} {8}
81 的概率走向
(
x
,
y
)
(x, y)
(x,y)，那么原问题与子问题的关系就是
d
f
s
(
k
,
i
,
j
)
=
1
8
Σ
(
x
,
y
)
d
f
s
(
k
−
1
,
x
,
y
)
dfs(k, i, j) = \frac {1} {8} \mathop{\Sigma}\limits_{(x, y)} dfs(k - 1, x, y)
dfs(k,i,j)=81(x,y)Σdfs(k−1,x,y)。
递归入口 是
d
f
s
(
k
,
r
o
w
,
c
o
l
u
m
n
)
dfs(k, row, column)
dfs(k,row,column)，也是答案。
递归边界 是当前位置仍在棋盘上，则
d
f
s
(
k
,
i
,
j
)
=
1
dfs(k, i, j) = 1
dfs(k,i,j)=1；当前位置出界，则
d
f
s
(
k
,
i
,
j
)
=
1
dfs(k, i, j) = 1
dfs(k,i,j)=1。
递归的做法实现完成之后，可以把它等效地翻译成递推。
考虑到棋盘上出界也会导致下标越界，而棋子最大的可能越界范围是边界以外距离为
2
2
2的位置，所以可以在初始化数组的时候在上下左右四个方向各扩展
2
2
2 个单位，通过偏移来修正表达式。
答案为
d
p
[
k
]
[
r
o
w
+
2
]
[
c
o
l
u
m
n
+
2
]
dp[k][row + 2][column + 2]
dp[k][row+2][column+2]。
初始值
d
p
[
0
]
[
i
]
[
j
]
dp[0][i][j]
dp[0][i][j] 表示尚未移动时，棋子一定在棋盘上。
目前总结出来的是，递归转换成递推时，表征递归层数的变量会在循环的最外层。
具体实现
递归
class Solution {
private static final int[][] DIRECTIONS = new int[][] {{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
public double knightProbability(int n, int k, int row, int column) {
double[][][] memo = new double[k + 1][n][n];
return dfs(n, k, row, column, memo);
}
private double dfs(int n, int k, int i, int j, double[][][] memo) {
if(i < 0 || i >= n || j < 0 || j >= n) {
return 0;
}
if(k == 0) {
return 1;
}
if(memo[k][i][j] != 0) {
return memo[k][i][j];
}
double res = 0.0;
for(int[] direction : DIRECTIONS) {
// 同层的概率可累加
res += dfs(n, k - 1, i + direction[0], j + direction[1], memo);
}
// 进入下一层之前计算最终结果，实际上也进行了稀释
return memo[k][i][j] = res / DIRECTIONS.length;
}
}
非递归
class Solution {
private static final int[][] DIRECTIONS = new int[][] {{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
public double knightProbability(int n, int k, int row, int column) {
double[][][] dp = new double[k + 1][n + 4][n + 4];
for(int i = 2; i < n + 2; i++) {
Arrays.fill(dp[0][i], 2, n + 2, 1);
}
for(int step = 1; step <= k; step++) {
for(int i = 2; i < n + 2; i++) {
for(int j = 2; j < n + 2; j++) {
for(int[] direction : DIRECTIONS) {
dp[step][i][j] += dp[step - 1][i + direction[0]][j + direction[1]];
}
dp[step][i][j] /= DIRECTIONS.length;
}
}
}
return dp[k][row + 2][column + 2];
}
}