已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。
现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。
如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 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） 链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
类似题目： LeetCode 552. 学生出勤记录 II（动态规划） LeetCode 576. 出界的路径数（动态规划） LeetCode 935. 骑士拨号器（动态规划）
dp[i][j][k] 表示在 (i, j) 时还剩 k 次跳动机会时的概率 class Solution { public: double knightProbability(int N, int K, int r, int c) { vector<vector<vector<double>>> dp(N, vector<vector<double>>(N, vector<double>(K+1, 0.0))); dp[r][c][K] = 1.0; vector<vector<int>> dir = {{2,1},{1,2},{-2,1},{-1,2},{2,-1},{1,-2},{-1,-2},{-2,-1}}; int i, j, k, x, y, d; for(k = K; k > 0; k--) { for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { for(d = 0; d < 8; d++) { x = i + dir[d][0]; y = j + dir[d][1]; if(x>=0 && x<N && y>=0 && y<N) { dp[x][y][k-1] += dp[i][j][k]/8.0; } } } } } double ans = 0.0; for(i = 0; i < N; i++) for(j = 0; j < N; j++) ans += dp[i][j][0]; return ans; } };28 ms 8 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
