【Day 59 】2021-11-07 - 688. “马”在棋盘上的概率

[azl397985856]

688. “马”在棋盘上的概率

入选理由

暂无

题目地址

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

前置知识

• 动态规划
• 数组

  题目描述

  
  已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。 

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

[yanglr]

思路:

这是一个概率dp问题。

方法: 动态规划

dp数组

3维的dp数组。

dp[i][j][k]: 跳k步后到达格子(i,j), 此时继续按"日"字向前跳, 跳到K步时留在棋盘上的概率之和(走法的总概率)。

递推关系:

f(i, j, k) = ∑1/8*f(x, y, k + 1)

做逆序遍历。

代码:

实现语言: C++

double f[25][25][101]; /* dp[i][j][k]: 跳k 步后到达格子(i,j), 此时继续按"日"字向前跳, 跳到大K步时留在棋盘上的概率之和(走法的总概率)。 */
class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        memset(f, 0.0, sizeof(f));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                f[i][j][K] = 1; /* 预处理边界 */
        int dx[] = {-2,-1,1,2,2,1,-1,-2}; /* 8组方向向量 */
        int dy[] = {1,2,2,1,-1,-2,-2,-1};
        for (int k = K - 1; k >= 0; k--)
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    for (int u = 0; u < 8; u++) /* 枚举8个方向, 累加其中合法方向的概率 */
                    {
                        int x = i + dx[u], y = j + dy[u];
                        if (x >= 0 && x < N && y >= 0 && y < N)
                            f[i][j][k] += f[x][y][k+1] / 8;                        
                    }        
        return f[r][c][0];
    }
};

复杂度分析

• 时间复杂度: O(k*N^2)
• 空间复杂度: O(k*N^2)

[st2yang]

思路

• dp 滚动数组

代码

• python

  class Solution:
  def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
      direct = [[-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1]]
  
      dp = [[0] * n for _ in range(n)]
      dp[row][column] = 1
  
      for _ in range(k):
          dp_temp = [[0] * n for _ in range(n)]
  
          for i in range(n):
              for j in range(n):
                  for d in direct:
                      lastR = i - d[0]
                      lastC = j - d[1]
                      if lastR >= 0 and lastR < n and lastC >= 0 and lastC < n:
                          dp_temp[i][j] += dp[lastR][lastC] * 0.125
  
          dp = dp_temp
  
      res = 0
      for i in range(n):
          for j in range(n):
              res += dp[i][j]
  
      return res

复杂度

• 时间: O(kn^2)
• 空间: O(kn^2)

[yachtcoder]

dfs + memo Count the number of valid moves then divide it with total moves (8^k) O(mnk), O(mnk)

class Solution:
    def knightProbability(self, n: int, k: int, r: int, c: int) -> float:
        dirs = [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]]
        @cache
        def dfs(x, y, k):
            if x < 0 or x >= n or y < 0 or y >= n: 
                return 0
            if k == 0:
                return 1
            valid = 0
            for d in dirs:
                nx, ny = x + d[0], y + d[1]
                valid += dfs(nx, ny, k-1)
            return valid
        valid = dfs(r, c, k)
        return valid/(8**k)

[zhy3213]

思路

由于只需要上一步的信息，dp数组可以使用两个二维数组滚动，节约了三维数组所需的空间。

[LAGRANGIST]

double f[25][25][101]; / dp[i][j][k]: 跳k 步后到达格子(i,j), 此时继续按"日"字向前跳, 跳到大K步时留在棋盘上的概率之和(走法的总概率)。 / class Solution { public: double knightProbability(int N, int K, int r, int c) { memset(f, 0.0, sizeof(f)); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) f[i][j][K] = 1; / 预处理边界 / int dx[] = {-2,-1,1,2,2,1,-1,-2}; / 8组方向向量 / int dy[] = {1,2,2,1,-1,-2,-2,-1}; for (int k = K - 1; k >= 0; k--) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int u = 0; u < 8; u++) / 枚举8个方向, 累加其中合法方向的概率 / { int x = i + dx[u], y = j + dy[u]; if (x >= 0 && x < N && y >= 0 && y < N) f[i][j][k] += f[x][y][k+1] / 8;
}
return f[r][c][0]; } };

[JiangyanLiNEU]

Idea

• memorization
• Runtime = Space = O(n^2*k)

  Python

  class Solution(object):
  def knightProbability(self, n, k, row, column):
      directions = [[1,2], [1,-2],[2,1],[2,-1],[-1,2],[-1,-2],[-2,1],[-2,-1]]
      memo = {}
      def update(row, column, k):
          if row < 0 or row >= n or column < 0 or column >= n:
              memo[(row, column, k)] = 0.0
              return
          if k == 0:
              if 0<=row<n and 0<=column<n:
                  memo[(row, column, k)] = 1.0
              else:
                  memo[(row, column, k)] = 0.0
          else:
              sub_result = 0
              for di, dj in directions:
                  newI, newJ = row+di, column+dj
                  if (newI, newJ, k-1) not in memo:
                      update(newI, newJ, k-1)
                  sub_result += memo[(newI, newJ, k-1)]/8
              memo[(row, column, k)] = sub_result
      update(row, column, k)
      return memo[(row, column, k)]

  JavaScript

  var knightProbability = function(n, k, row, column) {
  const directions = [[1,2], [1,-2],[2,1],[2,-1],[-1,2],[-1,-2],[-2,1],[-2,-1]];
  let memo = new Map();
  var update = (row, column, k) => {
      if (row<0 || row>=n || column<0 || column>=n){
          memo.set(row.toString()+'+'+column.toString()+'+'+k.toString(), 0);
      }else{
          if (k==0){
              if (row<0 || row>=n || column<0 || column>=n){
                  memo.set(row.toString()+'+'+column.toString()+'+'+k.toString(), 0);
              }else{
                  memo.set(row.toString()+'+'+column.toString()+'+'+k.toString(), 1);
              };
          }else{
              let sub_result = 0;
              for (let item of directions){
                  let newI = row+item[0];
                  let newJ = column+item[1];
                  if (!memo.has((newI, newJ, k-1))){
                      update(newI, newJ, k-1);
                  };
                  sub_result += memo.get(newI.toString()+'+'+newJ.toString()+'+'+(k-1).toString())/8;
              };
              memo.set(row.toString()+'+'+column.toString()+'+'+k.toString(), sub_result);
          };
      };
  };
  update(row, column, k);
  return memo.get(row.toString()+'+'+column.toString()+'+'+k.toString());
  };

[wangzehan123]

Java Code:

public class Solution {
    /**
     * @param N: int
     * @param K: int
     * @param r: int
     * @param c: int
     * @return: the probability
     */

    private int[][] dir = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};

    public double knightProbability(int N, int K, int r, int c) {
        // Write your code here.
        double[][] dp = new double[N][N];
        dp[r][c] = 1;
        for (int step = 1; step <= K; step++) {
            double[][] dpTemp = new double[N][N];
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    for (int[] direction : dir) {
                        int lastR = i - direction[0];
                        int lastC = j - direction[1];
                        if (lastR >= 0 && lastR < N && lastC >= 0 && lastC < N)
                            dpTemp[i][j] += dp[lastR][lastC] * 0.125;
                    }
            dp = dpTemp;
        }
        double res = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                res += dp[i][j];

        return res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[zhangzz2015]

思路

• 和之前21点计算概率类似。定义dp 函数为 dp(x,y,k) 为在位置[x, y]跳k次待在board的概率。dp(x,y,k)= 0.125 (dp(x+1,y+2,k-1) + dp(x+1, y-2,k-1) + dp(x-1,y-2, k-1) + dp(x-1,y+2, k-1) + dp(x+2,y+1,k-1) + dp(x+2,y-1,k-1) + dp(x-2,y-1,k-1) + dp(x-2,y+1,k-1)) ，时间复杂度为O(8knn)，空间复杂度为O(knn)

• 方法1， 采用记忆化递归，利用bfs + memo。

• 方法2，可利用dp。从k=0 外推出k的情况。在k=0是，在board内部的概率为1。时间复杂度为 O(knn8), 空间复杂度为 O(knn) -方法3，因为dp函数只和k-1相关，可压缩，时间复杂度和方法2相同，空间复杂度为O(2n*n)

  关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {

        // use memorize dfs. 
       unordered_map<string, double> saveProbe ; 

        return dfs(n, k, row, column, saveProbe);

    }

    double dfs(int n, int k, int row, int col, unordered_map<string, double>& saveProbe)
    {
        if(row<0 || row>=n || col<0 || col>=n)
                return 0.;        
        if(k==0)
        {
                return 1.; 
        }

        string keyValue = to_string(row) +"#" + to_string(col) + "#" + to_string(k); 
        if(saveProbe.find(keyValue)!=saveProbe.end())
            return saveProbe[keyValue]; 
        //    2 1 2 -1 -2 1 -2 -1 2 
        //    2 1 2 -1 -2 1 -2 -1
        //    1 2 -1 -2 1 -2 -1 2
        //    1 2 1 -2 -1 2 -1 -2 
        vector<int> direction={2, 1, 2, -1, -2, 1, -2, -1, 2};
        double ret=0; 
        for(int i =0; i< direction.size()-1; i++)
        {
            int irow = row+direction[i]; 
            int icol = col+direction[i+1]; 
            ret +=dfs(n, k-1, irow, icol, saveProbe)*0.125;
        }

        saveProbe[keyValue] = ret; 
        return ret; 

    }
};

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,1)));
        vector<int> direction={2, 1, 2, -1, -2, 1, -2, -1, 2};
        for(int i=1; i<=k; i++)
        {
            for(int irow=0; irow<n; irow++)
            {
                for(int icol=0; icol<n; icol++)
                {
                    double probe =0; 
                    for(int ii =0; ii< direction.size()-1; ii++)
                    {
                        int jrow = irow+direction[ii]; 
                        int jcol = icol+direction[ii+1]; 
                        if(jrow>=0&&jrow<n&&jcol>=0&&jcol<n)
                            probe += dp[i-1][jrow][jcol]*0.125; 
                    }                     
                    dp[i][irow][icol] = probe;                     
                }
            }
        }

        return dp[k][row][column]; 

    }
};

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {

        vector<double> dp1(n*n,1);
        vector<double> dp2(n*n,1 );
        vector<int> direction={2, 1, 2, -1, -2, 1, -2, -1, 2};
        double* prev=&dp1[0]; 
        double* current = &dp2[0];
        for(int i=1; i<=k; i++)
        {
            for(int irow=0; irow<n; irow++)
            {
                for(int icol=0; icol<n; icol++)
                {
                    double probe =0; 
                    for(int ii =0; ii< direction.size()-1; ii++)
                    {
                        int jrow = irow+direction[ii]; 
                        int jcol = icol+direction[ii+1]; 
                        if(jrow>=0&&jrow<n&&jcol>=0&&jcol<n)
                            probe += prev[jrow*n+jcol]*0.125; 
                    }  
                    if(i==k && irow==row && icol==column)
                        return probe; 
                    current[irow*n+icol] = probe;                     
                }
            }
            swap(prev, current); 
        }

        return prev[row*n+column]; 

    }
};

[laofuWF]

# dfs with memo

# time/space: O(n^2*k)

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(1, 2), (2, 1), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (2, -1), (1, -2)]

        memo = {}

        def dfs(x, y, n, k, memo, curr_prob):            
            if x >= n or y >= n or x < 0 or y < 0 or k < 0:
                memo[(x, y, k)] = 0.0
                return

            if k == 0 and x <= n and x >= 0 and y <= n and y >= 0:
                memo[(x, y, k)] = curr_prob
                return

            sub_prob = 0.0

            for dx, dy in directions:
                new_x = x + dx
                new_y = y + dy

                if not (new_x, new_y, k - 1) in memo:
                    dfs(new_x, new_y, n, k - 1, memo, curr_prob * (1/8))
                sub_prob += memo[(new_x, new_y, k - 1)]

            memo[(x, y, k)] = sub_prob

        dfs(row, column, n, k, memo, 1)

        return memo[(row, column, k)]

[q815101630]

终于赶上进度~

688-KnightProbabilityinChessboard

Knight Probability in Chessboard

首先自己尝试backtrack解题，但是发现对于概率不熟悉。重点在于把整个棋盘每一步之后棋仍在棋盘上的所有概率考虑起来。具体看note

class Solution:
    def knightProbability(self, N: int, k: int, row: int, column: int) -> float:
        dir = ((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2))

        dp = [[0]*N for _ in range(N)]
        dp[row][column] = 1

        for step in range(k):
            temp = [[0]*N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for di,dj in dir:
                        lastI, lastJ = i-di, j-dj
                        if 0<=lastI<N and 0<=lastJ<N:
                            temp[i][j] += dp[lastI][lastJ]/8

            dp = temp

        res = 0
        for i in dp:
            for j in i:
                res  += j

        return res

复杂度：

时间：O(kNN)

空间: O(NN)

[ZacheryCao]

Idea:

DP. dp[i][j] the times to get point (i, j) at current step. We also need to memorize all the points we've seen in last step and the times to get that point. It can be memorized with a dictionary of set, whose key is the ith step (1-based). value is the points we've seen at ith step

Code:

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0:
            return 1
        direction = {(-1, -2), (1, 2), (-1, 2), (1, -2), (2, 1), (-2, -1), (2, -1), (-2, 1)}
        dp = [[0 for _ in range(n)] for _ in range(n)]
        dp[row][column] = 1
        seen = {0:set()}
        seen[0].add((row, column))
        for t in range(k):
            if not seen:
                return 0
            l = len(seen[t])
            for _ in range(l):
                i, j = seen[t].pop()
                times = dp[i][j]
                dp[i][j] = 0
                for d in direction:
                    ii, jj = i + d[0], j + d[1]
                    if 0 <= ii < n and 0<=jj<n:
                        dp[ii][jj] += times
                        if t + 1 not in seen:
                            seen[t + 1] = set()
                        seen[t+1].add((ii, jj))
            seen.pop(t)
        return sum(sum(dp,[]))/8**k

Complexity:

Time: O(k * N^2). Two for loops, one if for the k steps, the other is to get the points we've seen last time, which can be N^2 points at worst case. Space: O(N^2). dp needs N^2. The dictionary also needs N^2, since every time we only record the points we saw at this step and clear the previous step's record.

[ginnydyy]

Problem

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

Notes

• DP problem
• The problem is asking at the kth step, the total possibilities that the knight stays within the board.
• To get the total possibliities, we need to get the possibilities of each cell, which is at the kth step, the possibility that the knight can reach this cell from the origin (row, coloumn).
• Need to figure out the relation between the current step and the previous step
  • for each cell, the possibility to reach here, is the possibility to reach its previous position / 8.0
  • so for each cell, we need to iterate all 8 directions to find the previous position's possibility, then calculate the possibility for the current cell
• Details:
  • instead of using k (steps) arrays to store the all the steps' possibilities, we can use two arrays, one is for the previous step's possibility, the other one is for the current step's.
  • so at the beginning of the step for loop, we need to new a current array;
  • in the middle of the for loop, calculate the current result based on the previous result
  • and at the end of the step for loop, we need to update the current result as a previous result
  • since starting from the cell (row, column), we need to initialize the pre[row][column] = 1.0

Solution

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = new int[][]{{1, 2}, {-1, -2}, {1, -2}, {-1, 2}, {2, 1}, {-2, -1}, {2, -1}, {-2, 1}};
        double[][] pre = new double[n][n]; // possibilities for the previous step
        pre[row][column] = 1.0;

        for(int s = 0; s < k; s++){ // iterate each step
            double[][] cur = new double[n][n]; // possibilities for the current step
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){ // iterate each cell
                    for(int d = 0; d < dirs.length; d++){ // for each step, iterate each direction
                        int pr = i - dirs[d][0];
                        int pc = j - dirs[d][1];
                        if(pr >= 0 && pr < n && pc >= 0 && pc < n){
                            cur[i][j] += pre[pr][pc] / 8.0; // based on the posibilies of the previous step, calculate the possibilities of the current step
                        }
                    }
                }
            }
            pre = cur; // update the possibilities of the previous step as the current step's result
        }

        double res = 0.0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                res += pre[i][j];
            }
        }

        return res;

    }
}

Complexity

• Time: O(kn^2). k is the number of steps, n is the width of the board. We iterate each step, for each step, we iterate each cell, there are n^2 cells. So total O(kn^2).
• Space: O(n^2). Extra space is required for the two arrays, the size is the number of cells.

[ForLittleBeauty]

思路

---

统计每一步后，留在棋盘上的骑士的次数，k步以后，次数之和最后除以总的可能数。

---

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        direction_list = [[-2,1],[2,1],[-2,-1],[2,-1],[1,2],[1,-2],[-1,2],[-1,-2]]

        dp = [[0 for _ in range(n)] for _ in range(n)]
        dp[row][column] = 1

        for _ in range(k):
            dp1 = [[0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    if dp[i][j] == 0:
                        continue
                    else:
                        for t in range(8):
                            x = direction_list[t][0]+i
                            y = direction_list[t][1]+j
                            if x<0 or x>n-1 or y<0 or y>n-1:
                                continue
                            dp1[x][y] += dp[i][j]
            dp = dp1

        return  sum(list(map(sum,dp)))/8**k

---

时间复杂度: O(kn^2)

空间复杂度: O(n^2)

[Daniel-Zheng]

思路

动态规划。

代码(C++)

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<double>> dp(n, vector<double>(n));
        vector<int> dr = {2, 2, 1, 1, -1, -1, -2, -2};
        vector<int> dc = {1, -1, 2, -2, 2, -2, 1, -1};
        dp[row][column] = 1;
        for (int step = k; step > 0; step--) {
            vector<vector<double>> dpTemp(n, vector<double>(n));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < 8; k++) {
                        int cr = i + dr[k];
                        int cc = j + dc[k];
                        if (cr >= 0 && cr < n && cc >= 0 && cc < n) dpTemp[cr][cc] += dp[i][j] / 8.0;
                    }
                }
            }
            dp = dpTemp;
        }
        double res = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) res += dp[i][j];
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(KN^2)
• 空间复杂度：O(N^2)

[kidexp]

thoughts

dp[k][(i,j)]表示在k个move 马在i，j的概率

根据每一步的每一个坐标推算下一个坐标的概率 dp[k+1][(new_i, new_j)] = 0.125*sum(dp[k][(i,j]) 其中i,j能走到new_i和new_j

把最后一步的所有valid坐标的概率加在一起就是最后的概率

可以用滚动数组优化空间

code

from collections import defaultdict

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = {i: defaultdict(float) for i in range(k + 1)}
        dp[0][(row, column)] = 1
        for step in range(1, k + 1):
            for i, j in dp[step - 1]:
                for delta_i, delta_j in [
                    (-2, -1),
                    (-2, 1),
                    (-1, -2),
                    (-1, 2),
                    (1, -2),
                    (1, 2),
                    (2, -1),
                    (2, 1),
                ]:
                    new_i, new_j = i + delta_i, j + delta_j
                    if 0 <= new_i < n and 0 <= new_j < n:
                        dp[step][(new_i, new_j)] += 0.125 * dp[step - 1][(i, j)]
        return sum(dp[k].values())

complexity

Time O(kn^2) Space O(kn^2)

[james20141606]

Day 59: 688. Knight Probability in Chessboard (DP)

• Problem Link

  • 688. Knight Probability in Chessboard

• Ideas

  • we need a 2D dp array, cur, and we also need a nxt 2d array! use cur to update the nxt! and after the double loop we replace cur with nxt (instead of a 3D dp[i][j][steps])
  • within the i,j loop, we have eight options of cur[i][j] to jump to, decide if the potential jump x,y is within the board and if yes, add cur[i][j] / 8

• Complexity: hash table and bucket

  • Time: O(N^2*K)
  • Space: O(N^2)

• Code

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        cur = [[0] * N for _ in range(N)]
        cur[r][c] = 1
        for _ in range(K):
            nxt = [[0] * N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for x, y in ((i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), 
                                (i + 1, j + 2), (i - 1, j + 2), (i + 1, j - 2), (i - 1, j - 2)):
                        if 0 <= x < N and 0 <= y < N:
                            nxt[x][y] += cur[i][j] / 8
            cur = nxt
        print (cur, list(map(sum, cur)))
        return sum(map(sum, cur))

• other resources:
  • https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/688-ma-zai-qi-pan-shang-de-gai-lu-dong-t-85ln/
  • https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/688-ma-zai-qi-pan-shang-de-gai-lu-dong-t-85ln/

[CoreJa]

思路

7个月前做过这题，但那个时候还不太懂动规的基本步骤和操作，只写出了回溯法，显然超时

棋盘二维数组用来定义马落子在该格子的概率，所以在棋盘上的概率就是所有格子之和即可。

那么动规方程就有dp[r][c]+=1/8*dp[r+r_delta][c+c_delta]，r_delta 和 c+c_delta 分别取8个方向即可，初始化将棋子最一开始的位置为1即可。

题目的关键在于上一次棋盘的状态和这一次棋盘的状态该如何区分，比较机智的思路就是直接用两个二维数组来回取代即可。用一个dp2来表示基于原dp得到的状态，更新好dp2后再讲dp=dp2即可，即dp2[r][c]+=1/8*dp[r+r_delta][c+c_delta]

此外还有一个优化点是，因为我们只需要更新dp中有概率的点，对于dp中概率为0的点，其对dp2对应点的影响为0，所以可以跳过。但需要调整一下动规方程，之前的动规方程是以当前dp2的行列下标来搜dp中行列下标的8个位置。为了这个优化，我们需要基于dp中的行列的下标来更新dp2

即dp2[r + r_delta][c + c_delta] += 1 / 8 * dp[r][c]

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(-2, +1), (-1, +2), (+1, +2), (+2, +1), (+2, -1), (+1, -2), (-1, -2), (-2, -1)]
        dp = [[0.0] * n for _ in range(n)]
        dp[row][column] = 1.0
        for _ in range(k):
            dp2 = [[0.0] * n for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    if dp[r][c] == 0.0:
                        continue
                    for r_delta, c_delta in directions:
                        if 0 <= r + r_delta < n and 0 <= c + c_delta < n:
                            dp2[r + r_delta][c + c_delta] += 1 / 8 * dp[r][c]
            dp = dp2
        return sum(map(sum, dp))

复杂度分析

TC: O(n^3) SC: O(n^2)

[chenming-cao]

解题思路

动态规划。参考题解。用二维数组储存到达该格子的概率。这里用到两个二维数组，dp用于储存移动之前的概率情况，dpTemp用于储存移动一步之后的概率状况。遍历二维数组dp，找到移动之前概率不为0的格子，由此格子出发找到8个可能到达的格子，如果新到达的格子坐标在范围（0 - n）中，说明格子在板子上，更新dpTemp数组中对应坐标的概率，加上dp / 8。遍历结束后，我们更新状态，dp = dpTemp。按照此方式循环k次，最后得到的dp数组中的概率值即为最终值。将所有概率值求和，最后即为棋子还在板子上的概率。

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        // save the possible moving directions into an array
        int[][] dir = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
        // use a 2D array to store the probability to move to the cell
        double[][] dp = new double[n][n];
        dp[row][column] = 1; // set the initial probability as 1

        // simulate the moving process, calculate the probability after each move, repeat for k times
        for (int step = 1; step <= k; step++) {
            // use a different 2D array to save the temporary probability after each move, easy to update
            // also we will need to refer to previous state to calculate the new state, 
            // we would not like to overwrite previous state
            double[][] dpTemp = new double[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    double prob = dp[i][j];
                    // only need to do the calculation starting from cell with probability > 0
                    if (prob > 0) {
                        // update the probability of 8 possible cells
                        for (int m = 0; m < 8; m++) {
                            int newRow = i + dir[m][0];
                            int newCol = j + dir[m][1];
                            // if still on the board after move, store probability results in dpTemp
                            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                                dpTemp[newRow][newCol] += prob / 8;
                            }
                        }
                    }
                }
            }
            dp = dpTemp; // update dp when one move is done, status in dpTemp will be set as previous state
        }
        double res = 0; // use double here
        // calculate the total probability
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(kn^2)，循环k次，每次遍历n*n的数组
• 空间复杂度：O(n^2)

[nonevsnull]

思路

• 拿到题的直觉解法
  • dp考察的就是递归函数的推导，能推出来就做出来了大半
  • 这题看了半天没想出思路，参考答案理解了
  • 从起点出发，每次行动都更新一下概率
  • 每次都会从上一次的结果中形成新的可以走到的位置，以及对应的概率

AC

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] directions = new int[][]{{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};

        double[][] dp = new double[n][n];

        dp[row][column] = 1;

        for(int step = 0;step < k;step++){
            double[][] dpt = new double[n][n];

            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    for(int[] direction: directions){
                        int nr = i + direction[0];
                        int nc = j + direction[1];
                        if(nr >= 0 && nr < n && nc >= 0 && nc < n){
                            dpt[i][j] += dp[nr][nc] * 0.125;
                        }
                    }
                }
            }
            dp = dpt;
        }
        double res = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                res += dp[i][j];
            }
        }
        return res;
    }
}

复杂度

time: O(k*N^2) space: O(N^2)

[ymkymk]

思路

动态规划(参考官网) 令 f[r][c][steps] 代表马在位置 (r, c) 移动了 steps 次以后还留在棋盘上的概率 根据题目我们可以知道 (dr,dc) 的可能数据对是 (2,1), (2,−1), (−2,1), (−2,−1), (1,2), (1,−2), (−1,2), (−1,−2)。 我们将使用二维的 dp 和 dp2 来存储我们的数据，而不是使用三维数组 f。dp2 代表 f[][][steps]，dp 代表 f[][][steps-1]。

代码

``

class Solution {

    public double knightProbability(int N, int K, int sr, int sc) {
        double[][] dp = new double[N][N];
        int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
        int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};

        dp[sr][sc] = 1;
        for (; K > 0; K--) {
            double[][] dp2 = new double[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    for (int k = 0; k < 8; k++) {
                        int cr = r + dr[k];
                        int cc = c + dc[k];
                        if (0 <= cr && cr < N && 0 <= cc && cc < N) {
                            dp2[cr][cc] += dp[r][c] / 8.0;
                        }
                    }
                }
            }
            dp = dp2;
        }
        double ans = 0.0;
        for (double[] row: dp) {
            for (double x: row) ans += x;
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(nnk)

空间复杂度：O(n*n)

[biancaone]

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        memo = {}
        directions = {(2,1),(1,2),(-1,2),(-2,1),(-1,-2),(-2,-1),(2,-1),(1,-2)}

        def dfs(row, col, p, moves):
            if 0<=row<N and 0<=col<N:
                if moves>0:
                    sm = 0
                    for (x,y) in directions:
                        if (row+x, col+y, moves) not in memo:
                            memo[(row+x, col+y, moves)] = dfs(row+x, col+y, p/8, moves-1)
                        sm+=memo[(row+x, col+y, moves)]
                    return sm
                else:
                    return p # it will return pow(1/8, K) 
            else:
                return 0

        return dfs(r,c,1.0,K)

[joeytor]

思路

dp[i][j] 每一轮到达 点 (i,j) 的 概率

base case 第一轮开始前, dp[row][column] = 1

动态转移

​ dp1[ r1 ][ c1 ] = dp[i][j] * 1/8

每次对于所有的点的所有的方向, 如果这个移动之后的点 (r1, c1) 是在棋盘内的, 那么在这一轮的概率数组 dp1 上加上 上一轮 dp[i][j] 的 概率 * 1/8, 因为每次有 8 种不同的跳的路径

return sum([sum(x) for x in dp]) 最后一轮所有点的概率的和, 所有落在 dp 数组中的点都是在棋盘上的点, 符合条件, 全部加起来即可

from collections import defaultdict
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

        dp = [[0 for _ in range(n)] for _ in range(n)]
        directions = [(2,1),(1,2),(-1,-2),(-2,-1),(2,-1),(1,-2),(-2,1),(-1,2)]
        dp[row][column] = 1
        for _ in range(k):
            dp1 = [[0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for d1, d2 in directions:
                        r1, c1 = i + d1, j + d2
                        if 0<=r1<n and 0<=c1<n:
                            dp1[r1][c1] += dp[i][j] * 1/8

            dp = dp1
        return sum([sum(x) for x in dp])

复杂度

时间复杂度: O(n^2 * k) 遍历的时间复杂度

空间复杂度: O(n^2) 每次最多两个 dp 数组, 每个的空间复杂度是 O(n^2)

[ghost]

题目

688. Knight Probability in Chessboard

思路

DP

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0: return 1
        dp = [[1]*n for i in range(n)]
        directions = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]]

        for _ in range(k):
            temp = [[0]*n for i in range(n)]
            for i in range(n):
                for j in range(n):
                    for d in directions:
                        x = i + d[0]
                        y = j + d[1]

                        if x<0 or x>=n or y<0 or y>=n: continue
                        temp[i][j] += dp[x][y]
            dp = temp

        return dp[row][column]/pow(8,k)

## **复杂度**

Space: O(n*n)
Time: O(k*n*n)

[xixvtt]

看答案 复习

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = new int[][]{{1, 2}, {-1, -2}, {1, -2}, {-1, 2}, {2, 1}, {-2, -1}, {2, -1}, {-2, 1}};
        double[][] pre = new double[n][n]; // possibilities for the previous step
        pre[row][column] = 1.0;

        for(int s = 0; s < k; s++){ // iterate each step
            double[][] cur = new double[n][n]; // possibilities for the current step
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){ // iterate each cell
                    for(int d = 0; d < dirs.length; d++){ // for each step, iterate each direction
                        int pr = i - dirs[d][0];
                        int pc = j - dirs[d][1];
                        if(pr >= 0 && pr < n && pc >= 0 && pc < n){
                            cur[i][j] += pre[pr][pc] / 8.0; // based on the posibilies of the previous step, calculate the possibilities of the current step
                        }
                    }
                }
            }
            pre = cur; // update the possibilities of the previous step as the current step's result
        }

        double res = 0.0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                res += pre[i][j];
            }
        }

        return res;

    }
}

[cicihou]

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        '''
        题意就是马走日，指定步数、棋盘大小、马所在的初始行列之后，求 马在走了相应步数之后，落出棋盘的概率
        1. 马的初始状态为 1，其他位置都为 0
        2. 按步更新二维数组每个位置的概率，每个（棋盘内合法）位置我们都计算上一轮的马跳一次能否到达这个位置
            （因为每一步都有八种选择路线，因此选择到该位置的概率是 1/8 ）
            如果当前位置有效，我们把概率加到当前位置上
            if 0 <= lastR < n and 0 <= lastC < n:
                dpTemp[i][j] += dp[lastR][lastC] * 0.125
        3. 完成每个步数时，我们把本次的棋盘作为上一轮的棋盘状态，在下一轮开始前把当前棋盘清零，下次循环使用时的概率累加到上一轮的状态棋盘即可

        time: K * N^2
        space: N^2
        '''
        direc = [(-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1)]
        dp = [[0 for _ in range(n)] for _ in range(n)]
        dp[row][column] = 1

        for step in range(1, k+1):
            dpTemp = [[1 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for r, c in direc:
                        lastR = i - r
                        lastC = j - c
                        if 0 <= lastR < n and 0 <= lastC < n:
                            dpTemp[i][j] += dp[lastR][lastC] * 0.125
            dp = dpTemp
        return sum(sum(d) for d in dp)

[ychen8777]

思路

DP

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {

        int[] dRow = new int[]{2, 2, -2, -2, 1, 1, -1, -1};
        int[] dCol = new int[]{1, -1, 1, -1, 2, -2, 2, -2};
        double[][] dp = new double[n][n];

        int curRow = row;
        int curCol = column;
        dp[row][column] = 1.0;

        for (int i = 1; i <= k; i++) {
            double[][] dp2 = new double[n][n];

            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    for (int j = 0; j < 8; j++) {
                        curRow = r + dRow[j];
                        curCol = c + dCol[j];

                        if (curRow >= 0 && curRow < n && curCol >= 0 && curCol < n) {
                            dp2[curRow][curCol] += dp[r][c] / 8.0;
                            //System.out.println(i + " " + dp[r][c] + " " + dp2[curRow][curCol]);
                        }
                    }

                }
            }

            dp = dp2;

        }

        double res = 0.0;
        for (double[] arr : dp) {
            for (double prob : arr) {
                //System.out.println(prob);
                res += prob;
            }

        }

        return res;

    }
}

复杂度

时间: O(k*n^2) \ 空间: O(n^2)

[L-SUI]

function knightProbability(n: number, k: number, row: number, column: number): number { const dirs = [[-1, -2], [-2, -1], [1, 2], [2, 1], [-1, 2], [2, -1], [-2, 1], [1, -2]]; // cache[i][j][step]表示在step步时位于i,j位置仍在棋盘的概率 const cache = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => new Array(k + 1).fill(-1))); const dfs = (i: number, j: number, step: number) => { if (i < 0 || i >= n || j < 0 || j >= n) { // 出界，概率为0 return 0; } if (step === 0) { // 最后一步仍未出界，概率为1 return 1; } if (cache[i][j][step] !== -1) { // 有缓存的结果，直接返回 return cache[i][j][step]; } let sum = 0; for (let dir of dirs) { const [x, y] = dir; sum += dfs(i + x, j + y, step - 1); } // 在step步数时当前位置的概率和除以总数即是当前位置的概率 cache[i][j][step] = sum / dirs.length; return cache[i][j][step]; } return dfs(row, column, k); };

[shixinlovey1314]

Title:688. Knight Probability in Chessboard

Question Reference LeetCode

Solution

DP, use dp[i][j][k] to represent the possiblity for knight to be still in chessboard, when the knight starts from chessboard[i][j] and it needs to go through k steps. Then we know that, dp[i][j][0] = 1.0, - the knight does not need to move, and it is always stay in the chessboard. Now we have the transition formula: dp[i][j][k] = sum(all 8 postions that needs to move k-1 steps) / 8.

Code

class Solution {
public:
    vector<pair<int, int>> steps = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<float>>> dp (n, vector<vector<float>>(n, vector<float>(k + 1, 0.0)));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j][0] = 1.0;

        for (int l = 1; l <= k; l++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    for (auto& step : steps) {
                        int x = i + step.first;
                        int y = j + step.second;

                        if (x < 0 || x >= n || y < 0 || y >= n)
                            dp[i][j][l] += 0.0;
                        else
                            dp[i][j][l] += dp[x][y][l-1];
                    }
                    dp[i][j][l] /= 8;
                }

        return dp[row][column][k];
    }
};

Complexity

Time Complexity and Explanation

O(nnk);

Space Complexity and Explanation

O(nnk);

[zhiyuanpeng]

class Solution:
    def knightProbability(self, N: int, k: int, row: int, column: int) -> float:
        dir = ((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2))

        dp = [[0]*N for _ in range(N)]
        dp[row][column] = 1

        for step in range(k):
            temp = [[0]*N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for di,dj in dir:
                        lastI, lastJ = i-di, j-dj
                        if 0<=lastI<N and 0<=lastJ<N:
                            temp[i][j] += dp[lastI][lastJ]/8

            dp = temp

        res = 0
        for i in dp:
            for j in i:
                res  += j

        return res

[yingliucreates]

link:

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

代码 Javascript

const knightProbability = (N, K, r, c) => {
  const dirs = [
    [-2, -1],
    [-1, -2],
    [1, -2],
    [2, -1],
    [2, 1],
    [1, 2],
    [-1, 2],
    [-2, 1],
  ];

  const dp = [...Array(K + 1)].map(() =>
    [...Array(N)].map(() => Array(N).fill(0))
  );
  dp[0][r][c] = 1;

  for (let k = 1; k <= K; k++) {
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        for (const [dx, dy] of dirs) {
          const x = i + dx;
          const y = j + dy;
          if (x >= 0 && x < N && y >= 0 && y < N) {
            dp[k][i][j] += dp[k - 1][x][y] / 8;
          }
        }
      }
    }
  }

  let res = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      res += dp[K][i][j];
    }
  }
  return res;
};

[tongxw]

思路

• dp[i][j][k]：马移动了k次后，落在位置(i, j)的概率。
• 初始状态dp[row][col][0] = 1，其他位置为0。
• 转移方程，对于棋盘上任意位置(i, j)，马可以从跟它相邻的8个位置跳过来，所以概率为dp[i][j][k] = sum(dp[i - dx][j - dy][k - 1] / 8
• 迭代计算k次，最后把棋盘上所有的位置的概率加起来，就是马留在棋盘上的概率。

• 由于第k次的概率只跟第k-1次有关，所以可以用两个二维数组计算。

  代码

  public double knightProbability(int n, int k, int row, int col) {
  int[] dx = new int[] {1, -1, 1, -1, 2, -2, 2, -2};
  int[] dy = new int[] {2, 2, -2, -2, 1, 1, -1, -1};
  
  double[][] dp = new double[n][n];
  dp[row][col] = 1.0;
  
  for (int step = 1; step <= k; step++) {
  double[][] next = new double[n][n];
  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      for (int c=0; c<8; c++) {
        int prevRow = i + dx[c];
        int prevCol = j + dy[c];
        if (prevRow >=0 && prevRow < n && prevCol >= 0 && prevCol < n) {
          next[i][j] += (dp[prevRow][prevCol] / 8.0);
        }
      }
    }
  }
  
  dp = next;
  }
  
  double ans = 0.0f;
  for (int i=0; i<n; i++) {
  for (int j=0; j<n; j++) {
    ans += dp[i][j];
  }
  }
  
  return ans;
  }

TC: O(k * n^2) SC: O(n^2)

[kennyxcao]

688. Knight Probability in Chessboard

Intuition

• Top Down DP

Code

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
const knightProbability = function(n, k, row, column) {
  const dirs = [[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]]; // 8 dirs
  const memo = Array.from({length: n}, () => Array.from({length: n}, () => ({})));
  return dfs(row, column, 0) / Math.pow(8, k);

  function dfs(r, c, move) {
    if (r < 0 || r >= n || c < 0 || c >= n) return 0;
    if (move === k) return 1;
    if (memo[r][c].hasOwnProperty(move)) return memo[r][c][move];
    const sum = dirs.reduce((acc, [dr, dc]) => acc + dfs(r + dr, c + dc, move + 1), 0);
    return memo[r][c][move] = sum;
  }
};

Complexity Analysis

• Time: O(k*n^2)
• Space: O(k*n^2)

[laurallalala]

代码

class Solution:
    def knightProbability(self, N: int, k: int, row: int, column: int) -> float:
        dir = ((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2))

        dp = [[0]*N for _ in range(N)]
        dp[row][column] = 1

        for step in range(k):
            temp = [[0]*N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for di,dj in dir:
                        lastI, lastJ = i-di, j-dj
                        if 0<=lastI<N and 0<=lastJ<N:
                            temp[i][j] += dp[lastI][lastJ]/8

            dp = temp

        res = 0
        for i in dp:
            for j in i:
                res  += j

        return res

复杂度

• 时间复杂度: O(knn)
• 空间复杂度: O(n*n)

[thinkfurther]

思路

判断k次，从所有可能的位置转移到当前位置的概率

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

        directions = ((-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1))

        dp = [[0 for i in range(n)] for j in range(n)]

        dp[row][column] = 1

        for step in range(1, k + 1):
            dp_temp = [[0 for i in range(n)] for j in range(n)]

            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        last_row = i - direction[0]
                        last_column = j - direction[1]
                        if 0 <= last_row < n and 0 <= last_column < n:
                            dp_temp[i][j] += 0.125 * dp[last_row][last_column]

            dp = dp_temp

        return sum([sum(nums) for nums in dp])

复杂度

时间复杂度 ：O(K*N^2)

空间复杂度：O(N^2)

[AnhTom2000]

代码:Java

class Solution {
  public double knightProbability(int N, int K, int sr, int sc) {
        double[][] dp = new double[N][N];
        int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
        int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};

        dp[sr][sc] = 1;
        for (; K > 0; K--) {
            double[][] dp2 = new double[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    for (int k = 0; k < 8; k++) {
                        int cr = r + dr[k];
                        int cc = c + dc[k];
                        if (0 <= cr && cr < N && 0 <= cc && cc < N) {
                            dp2[cr][cc] += dp[r][c] / 8.0;
                        }
                    }
                }
            }
            dp = dp2;
        }
        double ans = 0.0;
        for (double[] row: dp) {
            for (double x: row) ans += x;
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(n²k)

空间复杂度：O(n²)

标签

数组,动态规划

[ai2095]

688. Knight Probability in Chessboard

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

Topics

• DP
• BFS

思路

Solution 1: DP : dp[i][j][s] is the probabilities at [i,j] at steps s. Use two 2D matrix to save space. Solution 2: BFS : Use two dict to keep the BFS layers.

代码 Python

#DP
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[0 for _ in range(n)] for _ in range(n)]
        dp[row][column] = 1.0
        directions = [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
        for _ in range(k):
            dp_2 = [[0 for _ in range(n)] for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    val = dp[r][c]
                    for dr, dc in directions:
                        if 0 <= r + dr < n and 0 <= c + dc < n:
                            dp_2[r+dr][c+dc] += val / 8.0
            dp = dp_2

        return sum(map(sum, dp))

#BFS
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]

        d_1 = defaultdict(float)
        d_1[(row, column)] = 1.0
        for _ in range(k):
            d_2 = defaultdict(float)
            for (cur_row, cur_col), cur_val in d_1.items():   
                for d in directions:
                    new_row, new_col, new_val = cur_row+d[0], cur_col+d[1], cur_val/8.0
                    if 0<= new_row < n and 0<= new_col < n:
                        d_2[(new_row, new_col)] += cur_val/8.0
            d_1 = d_2
        return sum(d_1.values())

复杂度分析

DP 时间复杂度： O(K*N^2)
空间复杂度：O(N^2)

BFS 时间复杂度： O(max(8^K, N^2))
空间复杂度：O(28K)

[m-z-w]

var knightProbability = function(n, k, row, column) {
    const dirs = [
        [2, 1],
        [1, 2],
        [2, -1],
        [1, -2],
        [-1, 2],
        [-2, 1],
        [-1, -2],
        [-2, -1]
    ]
    let dp = new Array(n)
    let res = 0
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(n).fill(0)
    }
    dp[row][column] = 1
    for (let step = 0; step < k; step++) {
        const dpTemp = new Array(n)
        for (let i = 0; i < n; i++) {
            dpTemp[i] = new Array(n).fill(0)
        }
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                for (let dir of dirs) {
                    const newR = i + dir[0]
                    const newC = j + dir[1]
                    if (newC >= 0 && newC < n && newR >= 0 && newR < n) {
                        dpTemp[newR][newC] += dp[i][j] / 8
                    }
                }
            }
        }
        dp = dpTemp
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            res += dp[i][j]
        }
    }
    return res
};

时间：O(n^2 * k) 空间：O(n^2)

[RocJeMaintiendrai]

题目

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

思路

DP. 初始化状态dp[row][col] = 1, 状态转移用两个dp数组，cur记录当前的概率，next记录下次移动的概率 next[x][y] += cur[i][j] / 8.0. 返回所有cur的位置的和。

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[i].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

复杂度分析

时间复杂度

O(n^2k)

空间复杂度

O(n^2)

[Richard-LYF]

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: N=n r=row c=column K=k cur = [[0] N for in range(N)] cur[r][c] = 1 for in range(K): nxt = [[0] N for _ in range(N)] for i in range(N): for j in range(N): for x, y in ((i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i - 1, j + 2), (i + 1, j - 2), (i - 1, j - 2)): if 0 <= x < N and 0 <= y < N: nxt[x][y] += cur[i][j] / 8 cur = nxt return sum(map(sum, cur))

[simonsayshi]

class Solution {
private:
    unordered_map<int, unordered_map<int, unordered_map<int, double>>>dp;
public:
    double knightProbability(int N, int K, int r, int c) {
        if(dp.count(r) && dp[r].count(c) && dp[r][c].count(K)) return dp[r][c][K];
        if(r < 0 || r >= N || c < 0 || c >= N) return 0;
        if(K == 0) return 1;
        double total = knightProbability(N, K - 1, r - 1, c - 2) + knightProbability(N, K - 1, r - 2, c - 1) 
                     + knightProbability(N, K - 1, r - 1, c + 2) + knightProbability(N, K - 1, r - 2, c + 1) 
                     + knightProbability(N, K - 1, r + 1, c + 2) + knightProbability(N, K - 1, r + 2, c + 1) 
                     + knightProbability(N, K - 1, r + 1, c - 2) + knightProbability(N, K - 1, r + 2, c - 1);
        double res = total / 8;
        dp[r][c][K] = res;
        return res;
    }
};

[Yufanzh]

Intuition

DP\ doesn't quite understand the explanation in solution\

Algorithm in python3

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dx = [-2, -1, 1, 2, 2, 1, -1, -2]
        dy = [-1, -2, 2, 1, -1, -2, 2, 1]
        dp = [[0.0 for _ in range(n)] for _ in range(n)]
        #initialize
        dp[row][column] = 1

        for s in range(k):
            dp_temp = [[0.0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for m in range(8):
                        last_row = i - dx[m]
                        last_col = j - dy[m]

                        if last_row >= 0 and last_row < n and last_col >= 0 and last_col < n:
                            dp_temp[i][j] += dp[last_row][last_col] * 0.125
            dp = dp_temp

        res = 0
        for i in range(n):
            for j in range(n):
                res += dp[i][j]
        return res

Complexity Analysis

• Time complexity: O(k*n^2)
• Space complexity: O(n^2)

[jiahui-z]

思路: store the probablity of staying on the board with a 3D array, the formula is: the probability of reaching (row, column) after k steps = the sume of probability of reaching (row+delta, column+delta) after k-1 steps, there are 8 possible cases (8 directions)

class Solution {
    private int[][] directions = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};

    private double[][][] dp;

    public double knightProbability(int n, int k, int row, int column) {
        dp = new double[n][n][k+1];

        return calculate(n, k, row, column);
    }

    // after k steps, the probability of being on the board
    private double calculate(int n, int k, int row, int column) {
        if (row < 0 || row >= n || column < 0 || column >= n) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }

        if (dp[row][column][k] != 0) {
            return dp[row][column][k];
        }

        double rate = 0;
        for (int i = 0; i < directions.length; i++) {
            rate += 0.125 * calculate(n, k - 1, row + directions[i][0], column + directions[i][1]);
        }
        dp[row][column][k] = rate;

        return rate;
    }
}

Time Complexity: O(n^2k) Space Complexity: O(nn*k)

[biscuit279]

思路：本次还在棋盘上的概率等于上次在棋盘上的概率再乘上8种情况下还在棋盘上的概率之和

class Solution(object):
    def knightProbability(self, n, k, row, column):
        """
        :type n: int
        :type k: int
        :type row: int
        :type column: int
        :rtype: float
        """
        dp = [[0]*n for _ in range(n)]
        dp[row][column] = 1
        for _ in range(k):
            dp2 = [[0]*n for _ in range(n)]
            for r,row in enumerate(dp):
                for c,val in enumerate(row):
                    for dr,dc in ((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)):
                        if 0<=r+dr<n and 0<=c+dc<n:
                            dp2[r+dr][c+dc] += val/8.0
            dp = dp2
        return sum(map(sum,dp))

时间复杂度：O（kn^2） 空间复杂度：O（n^2）

[yan0327]

思路： 果然还是缺乏对动态规划整合在一起的思想。 比如这题，能联想到小岛问题，只是这题考虑到是概率，且与次数有关。 小岛问题的位移[8][2]=》8个方向的数组，判断是否越界。 动态方程 dp[i][j][k] += da[tempi][tempj][k] 然后再除以8

func knightProbability(n int, k int, row int, column int) float64 {
    return method_dp(n,k,row,column)    
}
func method_dp(n int,k int,r int, c int) float64{
    steps := [8][2]int{{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}
    dp := make([][][]float64,n)
    for i:=0;i<n;i++{
        dp[i] = make([][]float64,n)
        for j:=0;j<n;j++{
            dp[i][j] = make([]float64,k+1)
        }
    }
    for m:=0;m <= k;m++{
        for i:=0;i<n;i++{
            for j:=0;j<n;j++{
                if m == 0{
                    dp[i][j][0]= 1
                }else{
                    for _,step := range steps{
                        tempi,tempj := i+step[0],j+step[1]
                        if tempi<0 || tempi >=  n||tempj<0||tempj>=n{
                            continue
                        }
                        dp[i][j][m] += dp[tempi][tempj][m-1]
                    }
                    dp[i][j][m] /= 8
                }
            }
        }
    }
    return dp[r][c][k]
}

时间复杂度：O(NNK) 空间复杂度：O（NNK）

[Bingbinxu]

方法 不连续的动态规划 代码

实现语言: C++
class Solution {
    double f[25][25][101];
public:
    double knightProbability(int N, int K, int r, int c) {
        memset(f, 0.0, sizeof(f));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                f[i][j][K] = 1; 
        int dx[] = {-2,-1,1,2,2,1,-1,-2}; 
        int dy[] = {1,2,2,1,-1,-2,-2,-1};
        for (int k = K - 1; k >= 0; k--)
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    for (int u = 0; u < 8; u++) 
                    {
                        int x = i + dx[u], y = j + dy[u];
                        if (x >= 0 && x < N && y >= 0 && y < N)
                            f[i][j][k] += f[x][y][k+1] / 8;                        
                    }        
        return f[r][c][0];
    }
};

复杂度分析 时间复杂度: O(K×N×N) 空间复杂度: O(N×N)

[for123s]

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<double>> dp(n,vector<double>(n,0));
        dp[row][column] = 1;
        vector<vector<int>> d = {{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
        for(;k>0;k--)
        {
            vector<vector<double>> dp2(n,vector<double>(n,0));
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    for(int idx=0;idx<8;idx++)
                    {
                        int row_d = i + d[idx][0];
                        int column_d = j + d[idx][1];
                        if(row_d>=0&&row_d<n&&column_d>=0&&column_d<n)
                            dp2[row_d][column_d] += dp[i][j] / 8.0;
                    }
                }
            }
            dp = dp2;
        }
        double res = 0.0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                res += dp[i][j];
        return res;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

[falconruo]

思路: DP问题:

• 马每次移动有8种可能，对应的相对位置为{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, 每种的概率为1/8
• 使用二维数组dp记录不同坐标对应的概率，起始坐标 dp[row][column] = 1
• 每移动一次计算新的坐标(dy, dx)， 如果在棋盘内, 则更新临时概率tmp[y][x] += dp[dy][dx]/8;
• 每步结束更新dp的概率，最后返回从起始点的概率dp[row][column]

复杂度分析:

• 时间复杂度: O(K* N^2), 其中K为走的步数， N为棋盘的长或宽
• 空间复杂度: O(N^2), 二维数组的空间

代码(C++):

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        const vector<pair<int, int>> dirs = { {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {-1, 2}, {1, -2}, {-1, -2} };
        vector<vector<double>> dp(n, vector<double>(n, 1));

        dp[row][column] = 1;

        for (int i = 0; i < k; ++i) { // k steps
            vector<vector<double>> tmp = dp;
            for (int y = 0; y < n; ++y) {
                for (int x = 0; x < n; ++x) {
                    tmp[y][x] = 0;
                    for (auto d : dirs) { // 8 directions
                        int dy = y + d.first;
                        int dx = x + d.second;
                        if (dy >= 0 && dy < n && dx >= 0 && dx < n)
                            tmp[y][x] += dp[dy][dx]/ 8;
                    }
                }
            }

            swap(tmp, dp);
        }

        return dp[row][column];
    }
};

[mm12344]

思路

DP

代码

class Solution(object):
    def knightProbability(self, N, K, r, c):
        dp = [[0] * N for _ in xrange(N)]
        dp[r][c] = 1
        for _ in xrange(K):
            dp2 = [[0] * N for _ in xrange(N)]
            for r, row in enumerate(dp):
                for c, val in enumerate(row):
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                   (1,2),(1,-2),(-1,2),(-1,-2)):
                        if 0 <= r + dr < N and 0 <= c + dc < N:
                            dp2[r+dr][c+dc] += val / 8.0
            dp = dp2

        return sum(map(sum, dp))

复杂度

时间复杂度：O(N^2*K) 空间复杂度：O(N^2)

[itsjacob]

Intuition

• [tags] dynamic programming, 3D dp problem
• the probability is simply getting the numerator and the denominator, where the denominator is 8^k, the numerator is the total possible moves that can make the knight stay at (row, col) at k moves
• Very similar to numerical solution to time-dependent PDE, where we simplify the numeric derivative to a gathering operation?
• intial condition is all 1's for the 2d dp table
• the meaning of the dp table dp[k][j][i] is the number of all possible moves that can land the knight to position (j, i) at time step k
• the return is then easily accessible from dp[j][row][col]

Implementation

class Solution
{
public:
  double knightProbability(int n, int k, int row, int column)
  {
    if (k == 0) return 1.0;
    // Time evolution of the check bord dp[k][j][i]
    // dp[k][j][i] is the total possible paths that we land to position (j, i) at time step k
    // dp[k][j][i] := sum(dp[k-1][y][x]), for (y,x) as neighbors of (j, i)
    std::vector<std::pair<int, int>> dirs{ { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 },
                                           { -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1 } };
    std::vector<std::vector<double>> dp_prev(n, std::vector<double>(n, 1));
    for (int kk = 0; kk < k; kk++) {
      std::vector<std::vector<double>> dp_curr(n, std::vector<double>(n, 0));
      for (int jj = 0; jj < n; jj++) {
        for (int ii = 0; ii < n; ii++) {
          for (auto const &dir : dirs) {
            int y = jj + dir.second;
            int x = ii + dir.first;
            if (x < 0 || x >= n || y < 0 || y >= n) continue;
            dp_curr[jj][ii] += dp_prev[y][x];
          }
        }
      }
      dp_prev = dp_curr;
    }
    return dp_prev[row][column] / std::pow(8, k);
  }
};

Complexity

• Time complexity: O(kn^2)
• Space complexity: O(n^2)

[florenzliu]

Explanation

• dynamic programming
• check back

Code

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        def isValid(x, y):
            return x >= 0 and y >= 0 and x < n and y < n
        direction = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]
        dp = [[0 for _ in range(n)] for _ in range(n)]
        dp[row][column] = 1
        for _ in range(k):
            dp2 = [[0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for dx, dy in direction:
                        if isValid(i+dx, j+dy):
                            dp2[i+dx][j+dy] += dp[i][j] / 8
            dp = dp2
        return sum([dp[i][j] for i in range(n) for j in range(n)])

Complexity

• Time: O(N^2 K)
• Space: O(N^2)