文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

已知一個 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
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 688. “马”在棋盘上的概率（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。