2022.02.17
688. 骑士在棋盘上的概率
https://leetcode-cn.com/problems/knight-probability-in-chessboard/
在一个 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][x][y]，其中第一维step代表这是走第step步得到的每个位置的概率（范围是0~k），而后面两维x和y则是在棋盘上的位置，如dp[1][1][4]的元素代表的是走1步能够到达（1，4）这个位置的概率。当step=0时，只有输入的初始位置概率是1，其他位置都为0。
 而动态规划的思想体现在，由于每一个位置都可能由周围的8个位置走一步到达，那么如果求出这8个位置在上一步时的概率，全部加起来除以8即为这个位置在这一步的概率（棋盘外面的概率都视为0，因为不能走出去再走回来）。
 代码：（C++）
class Solution {
public:
double knightProbability(int n, int k, int row, int column) {
if(k==0){
return 1.0;
}
int directions[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};//初始化方向数组，某个位置加上这8个方向即为这个位置走一步能到的位置
float dp[101][26][26]={{{0.0}}};//dp数组的初始化（C++中，不能对动态数组进行初始化，因此使用最原始的超大数组方式）
dp[0][row][column]=1;
for(int i=1;i<=k;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
for(int l=0;l<8;l++){
int x=j+directions[l][0];
int y=k+directions[l][1];
if(x>=0 && x<=n-1 && y>=0 && y<=n-1){
dp[i][j][k]+=dp[i-1][x][y]/8;
}
}
}
}
}//4层循环，对每一步，每个位置对应的8个方向进行模拟，求出其概率和
double ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ans+=dp[k][i][j];
}
}//把第k步后棋盘上的概率全部加起来得到答案
return ans;
}
};