【LeetCode每日一题】688. 骑士在棋盘上的概率【中等】【DP】

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

示例 1：

输入: n = 3, k = 2, row = 0, column = 0 输出: 0.0625 解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。 在每一个位置上，也有两种移动可以让骑士留在棋盘上。 骑士留在棋盘上的总概率是0.0625。 示例 2：

输入: n = 1, k = 0, row = 0, column = 0 输出: 1.00000  

提示:

1 <= n <= 25 0 <= k <= 100 0 <= row, column <= n

题解： 这道题是一道比较有趣的动态规划题，使用一个三维数组进行存储，dp[step][i][j] 表示骑士从棋盘上的点 (i, j) 出发，走了 step 步时仍然留在棋盘上的概率。当step为0时，初始值为1。八个方向使用坐标数组进行存储。

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
        //八个方向
        vector<int> dx = {-2, -2, 2, 2, -1, -1, 1, 1};
        vector<int> dy = {-1, 1, -1, 1, -2, 2, -2, 2};
        for(int step = 0; step <= k; step++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(step == 0){
                        dp[step][i][j] = 1;
                    }
                    else{
                        for(int k = 0; k < 8; k++){
                            int nx = i + dx[k], ny = j + dy[k];
                            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                                //递推关系式
                                dp[step][i][j] += 0.125 * dp[step - 1][nx][ny];
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
};

时间复杂度和空间复杂度均为：O(k * n^2)。