题目地址：

https://www.lintcode.com/problem/knight-probability-in-chessboard/description

给定一个$N\times N$的棋盘，一个国际象棋里的”马“从坐标$(r,c)$出发，问其走$K$步之后仍然在棋盘上的概率。要求中途不能出界。

法1：记忆化搜索。首先，设已经走过的步数是$s$，$A$表示没走出界这个事件，那么由条件概率公式，得：$$P(A|s=k)=\frac{1}{8}\sum P(A|s=k+1)$$我们可以开一个记忆数组。设$f[i][j][k]$代表已经走了$k$步并且走到了$(i,j)$的情况下，走完$K$步没出界的概率。那么就有：$$f[i][j][k]=\frac{1}{8}\sum f[i\pm 1][j\pm 2][k+1]+f[i\pm 2][j\pm 1][k+1]$$边界条件，如果$k=K$，那么$f$的取值就取决于有没有出界，如果出界了，则取$0$，否则取$1$。代码如下：

import java.util.Arrays; public class Solution { /** * @param N: int * @param K: int * @param r: int * @param c: int * @return: the probability */ public double knightProbability(int N, int K, int r, int c) { // Write your code here. double[][][] dp = new double[N][N][K]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { Arrays.fill(dp[i][j], -1); } } return dfs(r, c, N, 0, K, dp); } private double dfs(int x, int y, int N, int step, int K, double[][][] dp) { // 出界了，取0 if (outBound(x, y, N)) { return 0.0; } // 走完K步仍然没出界，条件概率等于1 if (step == K) { return 1.0; } // 有记忆则调取记忆 if (dp[x][y][step] >= 0) { return dp[x][y][step]; } // 开八个方向 int[] dx = {1, 2, 1, 2, -1, -2, -1, -2}, dy = {2, 1, -2, -1, 2, 1, -2, -1}; double prob = 0; for (int i = 0; i < 8; i++) { int nextX = x + dx[i], nextY = y + dy[i]; prob += 0.125 * dfs(nextX, nextY, N, step + 1, K, dp); } // 存一下记忆 dp[x][y][step] = prob; return prob; } private boolean outBound(int x, int y, int N) { return !(0 <= x && x < N && 0 <= y && y < N); } }

时空复杂度$O(N^{2}K)$。

法2：动态规划。设$f[i][j][k]$是走$k$步到达$(i,j)$这个位置的概率。则$$f[i][j][k]=\frac{1}{8}\sum f[i\pm 1][j\pm 2][k-1]+f[i\pm 2][j\pm 1][k-1]$$这个式子其实也是条件概率公式。那么最后的答案就是将$f[0:N-1][0:N-1][k]$全加起来。代码如下：

public class Solution2 { /** * @param N: int * @param K: int * @param r: int * @param c: int * @return: the probability */ public double knightProbability(int N, int K, int r, int c) { // Write your code here. double[][][] dp = new double[N][N][K + 1]; dp[r][c][0] = 1.0; for (int k = 1; k <= K; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // 枚举八个方向 int[] dx = {1, 2, 1, 2, -1, -2, -1, -2}, dy = {2, 1, -2, -1, 2, 1, -2, -1}; for (int l = 0; l < 8; l++) { int prevX = i + dx[l], prevY = j + dy[l]; if (0 <= prevX && prevX < N && 0 <= prevY && prevY < N) { dp[i][j][k] += 0.125 * dp[prevX][prevY][k - 1]; } } } } } double res = 0.0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res += dp[i][j][K]; } } return res; } }

时空复杂度$O(N^{2}K)$。