题目：“马”在棋盘上的概率

  • 已知一个NxN的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为(0, 0)，最右下角的记为(N-1, N-1)。
  • 现有一个 “马”（也译作 “骑士”）位于(r, c)，并打算进行K 次移动。
  • 如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
  • image
    image
  • 现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了K次或跳到了棋盘外面。
  • 求移动结束后，“马” 仍留在棋盘上的概率。
示例：
输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。
注意：
  • N 的取值范围为 [1, 25]
  • K 的取值范围为 [0, 100]
  • 开始时，“马” 总是位于棋盘上

来源：力扣（LeetCode）第688题

链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard

分析：

  • 这道题的概率计算首先要先找到分子和分母，分母就是所有的情况，即K=1就是8种，K=2就是64种。
  • 然后是分子，分子是到第K步所有可能的情况。比如示例里面K=1有两种情况，k=2总共有4种可能，所以概率就是4/64
  • 因此这道题可以使用dp或者dfs来做。
  • 基本都是一些老套路。

代码：

  • dfs+记忆化搜索

    class Solution {
private int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
private int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
double[][][] memo;
public double knightProbability(int N, int K, int r, int c) {
    memo = new double[K+1][N][N];
    return dfs(N, K, r, c) / Math.pow(8, K);
}

public double dfs(int N, int K, int r, int c) {
    if (K == 0) return 1;
    if (memo[K][r][c] != 0) return memo[K][r][c];
    double ans = 0;
    for (int i = 0; i < 8; i++)
        if (r + dx[i] >= 0 && r + dx[i] < N && c + dy[i] >= 0 && c + dy[i] < N)
            ans += dfs(N, K-1, r + dx[i], c + dy[i]);
            memo[K][r][c] = ans;
    return ans;
}
}

  • 动态规划

    class Solution {
public double knightProbability(int N, int K, int r, int c) {
    int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
    int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
    double[][][] dp = new double[K+1][N][N];
    // i 第几步  j x位置 k y位置
    dp[0][r][c] = 1;
    for (int i = 1; i <= K; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (dp[i-1][j][k] != 0) {
                    for (int l = 0; l < 8; l++) 
                        if (j+dx[l] >= 0 && j+dx[l] < N && k+dy[l] >= 0 && k+dy[l] < N)
                            dp[i][j+dx[l]][k+dy[l]] += dp[i-1][j][k] / 8;
                }
            }
        }
    }
    double ans = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ans += dp[K][i][j];
    return ans;
}
}

  • 另外，为了节约空间，可以使用滚动数组。大幅度节省空间，速度还快了一点。

    class Solution {
public double knightProbability(int N, int K, int r, int c) {
    int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
    int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
    double[][][] dp = new double[2][N][N];
    // i 第几步  j x位置 k y位置
    dp[0][r][c] = 1;
    for (int ii = 1; ii <= K; ii++) {
        int i = ii & 1;
        int pi = i ^ 1;
        for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) dp[i][j][k] = 0;
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (dp[pi][j][k] != 0) {
                    for (int l = 0; l < 8; l++)
                        if (j+dx[l] >= 0 && j+dx[l] < N && k+dy[l] >= 0 && k+dy[l] < N)
                            dp[i][j+dx[l]][k+dy[l]] += dp[pi][j][k] / 8;
                }
            }
        }
    }
    double ans = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ans += dp[K&1][i][j];
    return ans;
}
}