题目

https://leetcode.com/problems/knight-probability-in-chessboard/

题解

左神讲过类似问题：
给定5个参数，N，M，row，col，k
表示在N*M的区域上，醉汉Bob初始在(row,col)位置
Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
任何时候Bob只要离开N*M的区域，就直接死亡
返回k步之后，Bob还在N*M的区域的概率

对于本题来说，k步之后留在棋盘上的概率 = 留在棋盘上的方法数/总方法数

class Solution {
    // k步之后留在棋盘上的概率 = 留在棋盘上的方法数/总方法数
    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[n][n][k + 1]; // int overflow
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = 1;
                for (int step = 1; step <= k; step++) {
                    dp[i][j][step] = -1;
                }
            }
        }
        return process(n, row, column, k, dp) / Math.pow(8, k);
    }

    // 在(i,j)位置，剩余k步可以跳的情况下，返回能够留在棋盘上的方法数
    public double process(int n, int i, int j, int step, double[][][] dp) {
        if (i < 0 || i >= n || j < 0 || j >= n) return 0;
        if (dp[i][j][step] >= 0) return dp[i][j][step];

        dp[i][j][step] = process(n, i - 2, j + 1, step - 1, dp) +
                process(n, i - 2, j - 1, step - 1, dp) +
                process(n, i + 2, j + 1, step - 1, dp) +
                process(n, i + 2, j - 1, step - 1, dp) +
                process(n, i - 1, j + 2, step - 1, dp) +
                process(n, i - 1, j - 2, step - 1, dp) +
                process(n, i + 1, j - 2, step - 1, dp) +
                process(n, i + 1, j + 2, step - 1, dp);

        return dp[i][j][step];
    }
}