azl397985856 commented 2 years ago

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 次或跳到了棋盘外面。

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

charlestang commented 2 years ago

思路

动态规划

dp(i, r, c) 表示，第 i 步，<r, c> 这个位置的概率。

dp(i, r, c) = sum(dp(i - 1, r', c') / 8)，意思是，上一轮，能从 <r', c'> 这个位置跳到当前位置 <r, c> 的概率只有 1/8。

显然，dp(0, row, column) = 1.0 第 0 轮，出发点<row, column> 的概率为 1.

我们要求的留在棋盘上的概率，就是最后第 k 轮，棋盘上所有概率不为零的格子的概率总和。

这里有一些小技巧，我们用一个集合记录每一轮可能到达的格子。不用遍历那些没可能到达的格子。

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        dp[0][row][column] = 1
        s = set([(row, column)])
        news = []
        for i in range(1, k + 1):
            for e in s:
                px, py = e[0], e[1]
                for dx, dy in [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]:
                    x = px + dx
                    y = py + dy
                    if 0 <= x < n and 0 <= y < n:
                        dp[i][x][y] += dp[i - 1][px][py] / 8
                        news.append((x, y))
            s = set(news)
            news = []
        ans = 0
        for i in range(n):
            ans += sum(dp[k][i])
        return ans

时间复杂度 O(n^2) 棋盘上所有的格子均有可能

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

ZacheryCao commented 2 years ago

Idea

DP

Code

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0:
            return 1
        if row == n or column == n:
            return 0
        direction = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2],[1, 2], [2, 1], [2, -1]]
        dp = {(row, column): 1}
        for i in range(k):
            tmp_dp = {}
            for p in dp:
                cur = dp[p]
                for d in direction:
                    rr, cc = p[0]+d[0], p[1]+d[1]
                    if 0 <= rr <n and 0 <=cc <n:
                        tmp_dp[(rr, cc)] = tmp_dp.get((rr, cc), 0) + cur
            dp = tmp_dp
        return sum(dp.values())/(8**k)

Complexity:

Time: (K N N) Space: (N * N)

yetfan commented 2 years ago

思路全跑一遍, 数组记录位置，计数，做除法。（超时）

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        total = 8 ** k
        rest = 0

        q = collections.deque([(row, column)])

        if k == 0:
            return 1

        while q and k>0:
            # print(len(q))
            for i in range(len(q)):  # 队中每个数需要判断下一步跳点
                cur = q.popleft()

                for x,y in [(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)]:
                    newx = cur[0] + x
                    newy = cur[1] + y

                    if newx >= 0 and newx < n and newy >= 0 and newy < n:
                        if k == 1:  # 最后一轮直接计数 不再加入队列 少一层
                            rest += 1
                            continue
                        q.append((newx,newy))

            k -= 1  # 这一轮 都跳完了
        return rest / total

复杂度 时间 O(8^k) 空间 O(8^(k-1))

思路集合替换列表，从而减少重复。另放一个n*n的列表来表示每个位置被棋子走过的次数（用计数替换重复出现的位置元素）。

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        total = 8 ** k
        rest = 0
        dp = [[0]*n for _ in range(n)]
        dp[row][column] = 1

        q = collections.deque([(row, column)])

        if k == 0:
            return 1

        while q and k>0:
            tempdp = [[0]*n for _ in range(n)]
            tempq = set()

            for i in range(len(q)):  # 队中每个数需要判断下一步跳点
                cur = q.popleft()

                for x,y in [(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)]:
                    newx = cur[0] + x
                    newy = cur[1] + y

                    if newx >= 0 and newx < n and newy >= 0 and newy < n:
                        tempdp[newx][newy] += dp[cur[0]][cur[1]] 
                        tempq.add((newx,newy))

            k -= 1  # 这一轮 都跳完了
            q = collections.deque(tempq)
            dp = tempdp
        return sum(map(sum,dp)) / total

复杂度 时间 O(kn^2) 空间 O(n^2)

进阶思路： 直接求概率，每一层+ 1/8 * 落点的值

zjsuper commented 2 years ago

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        ans = [[0 for _ in range(n)] for _ in range(n)]
        ans[row][column] = 1
        dic = [(-2,1),(-1,2),(1,2),(2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)]
        for i in range(k):
            ans2 = [[0 for _ in range(n)] for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    for a,b in dic:
                        if r+a >=0 and c+b>=0 and r+a <n and c+b<n:
                            ans2[r+a][c+b] += 0.125*ans[r][c]
            ans = ans2
        a = 0
        for i in range(n):
            for j in range(n):
                a += ans[i][j]
        return a

laofuWF commented 2 years ago

# 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)]

cszys888 commented 2 years ago

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0:
            return 1
        if n == 1:
            return 0
        dp = [[0]*(n+4) for _ in range(n+4)]
        dp[row+2][column+2] = 1
        dx = [-1,-1,1,1,-2,-2,2,2]
        dy = [2,-2,2,-2,1,-1,1,-1]
        for iteration in range(k):
            dp_new = [[0]*(n+4) for _ in range(n+4)]
            for row in range(2,n+2):
                for col in range(2, n+2):
                    for deltax, deltay in zip(dx,dy):
                        dp_new[row+deltax][col+deltay] += dp[row][col]
            dp_new[0] = [0]*(n+4)
            dp_new[1] = [0]*(n+4)
            dp_new[n+2] = [0]*(n+4)
            dp_new[n+3] = [0]*(n+4)
            for row in range(2,n+2):
                dp_new[row][0:2] = [0,0]
                dp_new[row][(n+2):(n+4)] = [0,0]
            dp = dp_new
        return sum([sum(x[2:(n+2)]) for x in dp[2:(n+2)]])/(8**k)

time complexity: O(K*N^2) space complexity: O(N^2)

Toms-BigData commented 2 years ago

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

思路

非标准dp,思路跟常规dp一样，不过需要通过“马”的行走规律来决定状态方程

golang代码

func knightProbability(n int, k int, sr int, sc int) float64 {
    dp := make([][]float64, n)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]float64, n)
    }

    dr := []int{2, 2, 1, 1, -1, -1, -2, -2}
    dc := []int{1, -1, 2, -2, 2, -2, 1, -1}

    dp[sr][sc] = 1
    for ; k > 0; k-- {
        dp2 := make([][]float64, n)
        for i := 0; i < len(dp); i++ {
            dp2[i] = make([]float64, n)
        }
        for r := 0; r < n; r++ {
            for c := 0; c < n; c++ {
                for k := 0; k < 8; k++ {
                    cr := r + dr[k]
                    cc := c + dc[k]
                    if 0 <= cr && cr < n && 0 <= cc && cc < n {
                        dp2[cr][cc] += dp[r][c] / 8.0
                    }
                }
            }
        }
        dp = dp2
    }
    ans := 0.0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            ans += dp[i][j]
        }
    }
    return ans
}

复杂度

时间:O(8kn2) 空间:O(kn2)

QinhaoChang commented 2 years ago

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: 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 [(1, 2), (2, 1), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (2, -1), (1, -2)]：
            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)]

CoreJa commented 2 years ago

思路

现在懒得写记忆化了，直接加@cache解决问题，面试可能需要自己补充，平时练习就不写了。

DFS+记忆化：直接朴素递归模拟并记忆化即可，每次跳的时候试探可跳的8个位置，形参有坐标和剩余步数。不过记忆化需要三维数组，写起来略微麻烦，直接@cache处理。复杂度$O(n^2k)$
DP：其实这题是个三维数组的动规，不过因为下一状态只和当前状态有关，所以同样可以用二维的滚动更新数组替代三维数组。状态转移方程$dp[i][j][k]=\sum dp[\hat i][\hat j][k-1]\quad (\hat i,\hat j为所有可能的位置)$，最后二维数组求和即可。复杂度$O(n^2k)$

代码

class Solution:
    # DFS+记忆化：直接朴素递归模拟并记忆化即可，每次跳的时候试探可跳的8个位置，形参有坐标和剩余步数。不过记忆化需要三维数组，
    # 写起来略微麻烦，直接`@cache`处理。复杂度$O(n^2k)$
    def knightProbability1(self, n: int, k: int, row: int, column: int) -> float:
        @cache
        def dfs(i, j, step):
            if not (0 <= i < n and 0 <= j < n):
                return 0
            if step == 0:
                return 1
            ans = 0
            for dx, dy in [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]:
                ans += dfs(i + dx, j + dy, step - 1) / 8
            return ans

        return dfs(row, column, k)

    # DP：其实这题是个三维数组的动规，不过因为下一状态只和当前状态有关，所以同样可以用二维的滚动更新数组替代三维数组。状态转
    # 移方程$dp[i][j][k]=\sum dp[\hat i][\hat j][k-1]\quad (\hat i,\hat j为所有可能的位置)$，最后二维数组求和即可。
    # 复杂度$O(n^2k)$
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[0] * n for _ in range(n)]
        dp[row][column] = 1
        for _ in range(k):
            dp_new = [[0] * n for _ in range(n)]
            for i, j in product(range(n), range(n)):
                if dp[i][j] != 0:
                    for dx, dy in [(2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2)]:
                        x, y = i + dx, j + dy
                        if 0 <= x < n and 0 <= y < n:
                            dp_new[x][y] += dp[i][j] / 8
            dp = dp_new
        return sum(map(sum, dp))

tongxw commented 2 years ago

思路

dp(i, j, k) = sum(dp(i + dx, j + dy, k-1)) / 8 dp(row, col, 0) = 1.0; return sum(dp(i, j, k));

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[n][n][2];
        dp[row][column][0] = 1.0;

        int[] dx = {2, 2, 1, -1, -2, -2, -1, 1};
        int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};

        for (int step=1; step<=k; step++) {
            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    dp[i][j][step%2] = 0.0;
                    for (int t=0; t<8; t++) {
                        int r = i + dx[t];
                        int c = j + dy[t];
                        if (r >= 0 && r < n && c >= 0 && c < n) {
                            dp[i][j][step%2] += dp[r][c][(step-1)%2];
                        }
                    }

                    dp[i][j][step%2] /= 8;
                }
            }
        }

        double sum = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                sum += dp[i][j][k%2];
            }
        }

        return sum;
    }
}

TC: O(mnk) SC: O(mn)

yan0327 commented 2 years ago

思路：果然还是缺乏对动态规划整合在一起的思想。比如这题，能联想到小岛问题，只是这题考虑到是概率，且与次数有关。小岛问题的位移[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）

falconruo commented 2 years ago

思路:

DP + Memorization

复杂度分析:

时间复杂度: 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>> moves = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

        vector<vector<double>> dp(n, vector<double>(n, 0));
        dp[row][column] = 1;

        for (int s = 0; s < k; ++s) {
            vector<vector<double>> tmp(n, vector<double>(n, 0));
            for (int y = 0; y < n; ++y) {
                for (int x = 0; x < n; ++x) {
                    for (auto m : moves) {
                        int new_y = y + m.first;
                        int new_x = x + m.second;
                        if (new_y >= 0 && new_y < n && new_x >= 0 && new_x < n)
                            tmp[y][x] += dp[new_y][new_x] * 0.125;
                    }
                }
            }
            dp = tmp;
        }

        double res = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                res += dp[i][j];

        return res;
    }
};

shamworld commented 2 years ago

var knightProbability = function(n, k, row, column) {
      // 每一个点可以移动的位置
  const MOVE = [
    [2, 1],
    [2, -1],
    [-2, 1],
    [-2, -1],
    [1, 2],
    [1, -2],
    [-1, 2],
    [-1, -2],
  ];
  // dp[i][j] 表示在位置 [i,j] 的概率
  let dp = Array.from({ length: n }).map(() => new Array(n).fill(0));
  dp[row][column] = 1; // 百分百在
  for (let s = 0; s < k; s++) {
    //   每一步都依赖上一步的图，但是对应的概率要按新的来处理
    const tempDp = Array.from({ length: n }).map(() => new Array(n).fill(0));
    //   要走 k 步
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        for (let item of MOVE) {
          //   每一个点都可以向 8 个位置走一遍
          const tempR = i + item[0];
          const tempC = j + item[1];
          if (tempR >= 0 && tempR < n && tempC >= 0 && tempC < n) {
            // 表明这个方向是可选的
            tempDp[i][j] += dp[tempR][tempC] * 0.125;
          }
        }
      }
    }
    dp = tempDp;
  }
  let res = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      res += dp[i][j];
    }
  }

  return res;

};

Tesla-1i commented 2 years ago

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0:
            return 1
        if n == 1:
            return 0
        dp = [[0]*(n+4) for _ in range(n+4)]
        dp[row+2][column+2] = 1
        dx = [-1,-1,1,1,-2,-2,2,2]
        dy = [2,-2,2,-2,1,-1,1,-1]
        for iteration in range(k):
            dp_new = [[0]*(n+4) for _ in range(n+4)]
            for row in range(2,n+2):
                for col in range(2, n+2):
                    for deltax, deltay in zip(dx,dy):
                        dp_new[row+deltax][col+deltay] += dp[row][col]
            dp_new[0] = [0]*(n+4)
            dp_new[1] = [0]*(n+4)
            dp_new[n+2] = [0]*(n+4)
            dp_new[n+3] = [0]*(n+4)
            for row in range(2,n+2):
                dp_new[row][0:2] = [0,0]
                dp_new[row][(n+2):(n+4)] = [0,0]
            dp = dp_new
        return sum([sum(x[2:(n+2)]) for x in dp[2:(n+2)]])/(8**k)

LinnSky commented 2 years ago

思路

动态规划

代码

     var knightProbability = function(n, k, row, column) {
        function isOut(r,c) {
            return r < 0 || c < 0 || r >= n || c >= n;
        }
        let dp1 = new Array(n).fill(0).map(i => new Array(n).fill(0));
        let dp2 = new Array(n).fill(0).map(i => new Array(n).fill(0)); 
        dp1[row][column] = 1;
        let steps = 1;
        let next = [[2,-1], [2,1], [-2,1], [-2,-1], [1,2], [1,-2], [-1,2], [-1,-2]];
        while (steps <= k) {
            for (let r=0; r<n; r++) {
                for (let c=0; c<n; c++) {
                    for (let [nx, ny] of next) {
                      let adder = isOut(r+nx, c+ny) ? 0 : dp1[r+nx][c+ny];
                      dp2[r][c] += adder / 8;
                  }
              }
          }

          let t = dp2;
          dp2 = dp1;
          dp1 = t;
          for (let r=0;r<n;r++) {
              for(let c=0; c<n; c++) {
                  dp2[r][c] = 0;
              }
          }
          steps += 1;
      }
      let res = 0;
      for (let r=0;r<n;r++) {
          for(let c=0; c<n; c++) {
              res += dp1[r][c];
          }
      }
      return res;
  };

xinhaoyi commented 2 years ago

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

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

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

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

思路一

动态规划

//马每一次都有八种走法
//令 f[r][c][steps] 代表马在位置 (r, c) 移动了 steps 次以后还留在棋盘上的概率，根据马的移动方式，我们有以下递归：
//f[r][c][steps] = ∑f[r + dr][c + dc][steps - 1] * 1/8，求和是把8组(dr,dc)加在一起，因为是都移动到了r,c位置
//而上一轮最多有8个点可以通过移动一次到达(r,c)，这一轮移动只有1/8的概率到达这个(r,c)点
//上式还可以等于∑... + ∑... + ∑... 
//最后不断的发散出去，我们最后求结果，也不清楚马到底可以跳到哪些个位置，但只要遍历整个棋盘，累加起来即可
//但这样可能要一个三维数组，我们观察到状态转移方程只需要保存当前轮次(step - 1)和下一轮(step)，所以用两个二维数组就可以
//用curDp代表当前轮次，用nextDp代表下一轮次

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        //马每一次都有八种走法
        //令 f[r][c][steps] 代表马在位置 (r, c) 移动了 steps 次以后还留在棋盘上的概率，根据马的移动方式，我们有以下递归：
        //f[r][c][steps] = ∑f[r + dr][c + dc][steps - 1] * 1/8，求和是把8组(dr,dc)加在一起，因为是都移动到了r,c位置
        //而上一轮最多有8个点可以通过移动一次到达(r,c)，这一轮移动只有1/8的概率到达这个(r,c)点
        //上式还可以等于∑... + ∑... + ∑... 
        //最后不断的发散出去，我们最后求结果，也不清楚马到底可以跳到哪些个位置，但只要遍历整个棋盘，累加起来即可
        //但这样可能要一个三维数组，我们观察到状态转移方程只需要保存当前轮次(step - 1)和下一轮(step)，所以用两个二维数组就可以
        //用curDp代表当前轮次，用nextDp代表下一轮次

        //8种不同跳法
        int[] dr = new int[]{1,2,2,1,-1,-2,-2,-1};
        int[] cr = new int[]{2,1,-1,-2,-2,-1,1,2};
        //特殊处理
        if(k == 0){
            return 1;
        }
        double[][] curDp = new double[n][n];
        //最初，step = 0时，就是还没有跳的时候，马处在(row,column)的概率是1
        curDp[row][column] = 1;
        for(int step = 1; step <= k; step++){
            double[][] nextDp = new double[n][n];
            //开始遍历各个棋盘上的点，用这个棋盘点上的当前轮次概率 * 1/8 后累加到对应的棋盘上的跳跃后的点上
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    //8种不同跳法
                    for(int type = 0; type < 8; type ++){
                        int newRow = i + dr[type];
                        int newColumn = j + cr[type];
                        if(newRow >= 0 && newRow < n && newColumn >=0 && newColumn < n){
                            nextDp[newRow][newColumn] += curDp[i][j] / 8;
                        }
                    }
                }
            }
            //在开始下一轮step前，更新curDp和nextDp
            curDp = nextDp;
        }

        //最后要返回的结果
        double p = 0;

        //遍历curDp，把各个点的概率累加起来
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                p += curDp[i][j];
            }
        }

        return p;

    }
}

复杂度分析

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

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

moirobinzhang commented 2 years ago

Code:

public class Solution { public double KnightProbability(int n, int k, int row, int column) { double[,] dp = new double[n, n]; int[] dr = new int[]{-2, -1, 1, 2, 2, 1, -1, -2}; int[] dc = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
dp[row, column] = 1;

    for (int i = 1; i <= k; i++)
    {
        double[,] dpTemp = new double[n, n];
        for ( int r = 0; r < n; r++)
        {
            for (int c = 0; c < n; c++)
            {
                for (int s = 0; s < 8; s++)
                {
                    int cr = r + dr[s];
                    int cc = c + dc[s];
                    if (cr >= 0 && cr < n && cc >= 0 && cc < n)
                        dpTemp[cr, cc] += dp[r, c] / 8.0;
                }
            }
        }

        dp= dpTemp;            
    }

    double res = 0;
    for (int r = 0; r < n; r++)
    {
        for (int c = 0; c < n; c++)
        {
            res += dp[r, c];
        }
    }

    return res;
}

}

GaoMinghao commented 2 years ago

思路

还是得加强判断在复杂条件中如何得到状态转移关系，自己思考的时候想的是从当前位置出发，可以到达哪些地方，而不是从哪些位置可以到达当前位置

代码

class Solution {
    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 row, int column) {
        double[][] dp = new double[n][n];
        dp[row][column] = 1;
        for(int i = 0; i < k; i++) {
            double[][] dpTemp = new double[n][n];
            for(int a = 0; a < n; a ++ ){
                for(int b = 0; b < n; b++) {
                    for(int[] dirOpt:dir) {
                        if(a+dirOpt[0]<n && a+dirOpt[0]>=0 && b+dirOpt[1] <n && b+dirOpt[1] >=0 ) {
                            dpTemp[a][b] += dp[a+dirOpt[0]][b+dirOpt[1]]*0.125;
                        }
                    }
                }
            }
            dp = dpTemp;
        }
        double ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n;j++) {
                ans += dp[i][j];
            }
        }
        return ans;
    }

}

时间复杂度

O(K*N^2)

xuhzyy commented 2 years ago

class Solution(object):
    def knightProbability(self, n, k, row, column):
        """
        :type n: int
        :type k: int
        :type row: int
        :type column: int
        :rtype: float
        """
        cur = [[0] * n for _ in range(n)]
        cur[row][column] = 1
        directions = [[1,2],[2,1],[-1,-2],[-2,-1],[2,-1],[-2,1],[1,-2],[-1,2]]
        for _ in range(k):
            nxt = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for di, dj in directions:
                        ni, nj = i + di, j + dj
                        if 0 <= ni and ni < n and 0 <= nj and nj < n:
                            nxt[i][j] += float(cur[ni][nj]) / 8
            cur = nxt
        return sum(map(sum, cur))

ACcentuaLtor commented 2 years ago

(看评论学习，新年第一题，懒惰啊……) 思路：动态，DFS 1.定义状态dp[i][j]为位置(i,j)有马的概率 2.初始化状态 dp[r][c] = 1 3.状态转移用两个dp数组cur和nxt来记录当前以及从当前[i,j]下次移动到[x,y]的概率，有nxt[x][y] += cur[i][j]/8 4.返回cur所有位置的概率和

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+1,j+2),(i+1,j-2),(i-1,j+2),(i-1,j-2),(i-2,j+1),(i-2,j-1)):
                        if 0 <= x < n and 0 <= y < n:
                            nxt[x][y] += cur[i][j]/8
            cur = nxt
        return sum(map(sum,cur))

时间复杂度O(nnk)，空间复杂度O(n*n)

haixiaolu commented 2 years ago

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        # current prob
        current = [[0] * n for _ in range(n)]
        # initialize state
        current[row][column] = 1
        for _ in range(k):
            # the prob after move once
            next = [[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:
                            next[x][y] += current[i][j] / 8

            current = next 
        return sum(map(sum, current))

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

hdyhdy commented 2 years ago

思路：数组和动态规划

func knightProbability(N int, K int, r int, c int) float64 {
    return method_dp(N, K, r, c)
}

/*
定义三维dp[r][c][k], r,c表示棋盘上位置, k表示移动次数
设定dp[r][c][0] = 1, 即移动0次时概率是1

马走的8个坐标
{
    {-2, -1},
    {-2, 1},
    {-1, -2},
    {-1, 2},
    {1, -2},
    {1, 2},
    {2, -1},
    {2, 1},
}
依次计算移动1次时所有坐标的上概率， 再计算第二次移动 .... 直到第K次即为结果
dp[r][c][k] = dp[r-2][c-1][k-1] + .... dp[r-2][c-1][k-2] / 8
*/
func method_dp(N int, K int, r int, c int) float64 {
    steps := [][]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 {
                        temp_i, temp_j := i+step[0], j+step[1]
                        if temp_i < 0 || temp_i >= N || temp_j < 0 || temp_j >= N {
                            continue
                        }
                        dp[i][j][m] += dp[temp_i][temp_j][m-1]
                    }
                    dp[i][j][m] /= 8
                }
                // fmt.Print(dp[i][j][m], " ")
            }
            // fmt.Println("")
        }
        // fmt.Println("")
    }

    return dp[r][c][K]
}

时间复杂度：O（n2k）空间复杂度;O（n2）

LannyX commented 2 years ago

思路

DP

代码

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

        for(int step = 0; step < k; step++){
            double[][] nxt = new double[n][n];
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    for(int[] dir : dirs){
                        //上一次的位置
                        int x = i - dir[0], y = j - dir[1];
                        if(x >= 0 && x < n && y >= 0 && y < n){
                            nxt[x][y] += cur[i][j] / 8.0;
                        }
                    }
                }
            }
            cur = nxt;
        }
        double res = 0;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                res += cur[i][j];
            }
        }
        return res;
    }
}

复杂度分析

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

zhangzz2015 commented 2 years ago

利用Top down 方法 dp[k][i][j] = 1/8( dp[k-1] [ i+1] [j+2] + dp[k-1][i+1[j-2] ... ) 可利用dfs + mem。另外也可以使用bottom up dp方法。从k=0 开始，递推到 k的情况，时间复杂度为O（k n^2) ，空间复杂为度为 O(kn^2) 。

关键点

代码

语言支持：C++

C++ Code:


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

        /// dp[i][j]  =  1/8(dp[])

      vector<vector<vector<double>>> mem(k+1, vector<vector<double>>(n, vector<double>(n, -1))); 

      return dfs(n, k, row, column, mem); 
    }

    //  row  [0, n-1]
    //  col  [0, n-1]
    // pos row col   if(row)
    double  dfs(int n, int k, int row, int col, vector<vector<vector<double>>>& mem)
    {
        if(row<0||row>=n||col<0||col>=n)
            return 0; 
        if(k==0)
            return 1; 
        //    1  2  
        //    2  -1
        //    -1  2
        //    2   1
        //    1  -2
        //   -2   -1
        //   -1  -2
        //   -2  1
        if(mem[k][row][col]>0)
            return mem[k][row][col]; 
        vector<int> direction={1, 2, -1, 2, 1, -2, -1, -2, 1}; 
        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, mem)/8.0); 
        }
//        cout << "k:" << k << "row:" << row << "col:" << col << "ret:" << ret<<"\n";
        mem[k][row][col] = ret; 
        return ret; 
    }

};

KennethAlgol commented 2 years ago

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;
    }
}

kbfx1234 commented 2 years ago

688. 骑士在棋盘上的概率

// 2-8
class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        // 马每次移动有8种可能 对应着每次的概率为1/8
        vector<pair<int, int>> dir = {{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
        vector<vector<double>> dp(n, vector<double> (n, 1));

        dp[row][column] = 1;

        for (int i = 0; i < k; i++) {
            vector<vector<double>> tmp = dp;
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    tmp[x][y] = 0;
                    for (auto m : dir) {
                        int dx = x + m.first;
                        int dy = y + m.second;
                        if (dx >= 0 && dx < n && dy >= 0 && dy < n) {
                            tmp[x][y] += dp[dx][dy] / 8;
                        }
                    }
                }
            }
            dp = tmp;
        }
        return dp[row][column];
    }
};

RocJeMaintiendrai commented 2 years ago

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
        int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
        double[][] cur = new double[n][n];
        cur[row][column] = 1;
        for(int step = 0; step < k; step++) {
            double[][] next = new double[n][n];
            for(int x = 0; x < n; x++) {
                for(int y = 0; y < n; y++) {
                    for(int i = 0; i < 8; i++) {
                        int newX = x + dx[i], newY = y + dy[i];
                        if(newX >= 0 && newX < n && newY >= 0 && newY < n) {
                            next[newX][newY] += cur[x][y] / 8.0;
                        }
                    }
                }
            }
            cur = next;
        }
        double res = 0.0;
        for(double[] r : cur) {
            for(double p : r) {
                res += p;
            }
        }
        return res;
    }
}

Richard-LYF commented 2 years ago

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

    cur = [[0]* n for i in range(n)]

    cur[row][column] = 1

    for i in range(k):
        nxt = [[0]*n for _ in range(n)]
        for j in range(n):
            for p in range(n):
                for x, y in ((j+2,p+1),(j+2,p-1),(j+1,p+2),(j+1,p-2),(j-1,p+2),(j-1,p-2),(j-2,p+1),(j-2,p-1)):
                    if 0<=x<n and 0<=y<n:
                        nxt[x][y] += cur[j][p] / 8
        cur = nxt
    return sum(list(map(sum,cur)))

o n2k on2

ZJP1483469269 commented 2 years ago

class Solution:

    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dx = [1,1,-1,-1,2,2,-2,-2]
        dy = [2,-2,2,-2,1,-1,1,-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 x in range(n):
                for y in range(n):
                    for l in range(8):
                        cx = x + dx[l]
                        cy = y + dy[l]
                        if cx >= 0 and cx < n and cy >= 0 and cy < n:
                            dp2[cx][cy] += dp[x][y] / 8
            dp = dp2
        ans = 0
        for i in dp:
            for j in i:
                ans += j
        return ans

1149004121 commented 2 years ago

骑士在棋盘上的概率

思路

动态规划。

代码

var knightProbability = function(n, k, row, column) {
    let dirs = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]];
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    dp[row][column] = 1;
    for(let t = 0; t < k; t++){
        let temp = new Array(n).fill(0).map(() => new Array(n).fill(0));
        for(let i = 0; i < n; i++){
            for(let j = 0; j < n; j++){
                for(let dir of dirs){
                    let lastX = i - dir[0];
                    let lastY = j - dir[1];
                    if(lastX >= 0 && lastX < n && lastY >= 0 && lastY < n){
                        temp[i][j] += dp[lastX][lastY] * 0.125;
                    }
                }
            }
        };
        dp = temp;
    };
    let p = 0;
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            p += dp[i][j];
        }
    };
    return p;
};

复杂度分析

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

callmeerika commented 2 years ago

思路

动态规划

var knightProbability = function (n, k, row, column) {
    let dp = new Array(n).fill(0).map(vv => new Array(n).fill(0));
    let xArr = [1, 2, 1, 2, -1, -2, -1, -2];
    let yArr = [2, 1, -2, -1, 2, 1, -2, -1];
    dp[row][column] = 1;
    while (k > 0) {
      let dp2 = new Array(n).fill(0).map(vv => new Array(n).fill(0));
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
          for (let l = 0; l < 8; l++) {
            let x = i - xArr[l];
            let y = j - yArr[l];
            if (x >= 0 && x < n && y >= 0 && y < n) {
              dp2[x][y] += dp[i][j] / 8;
            }
          }
        }
      }
      dp = dp2;
      k--;
    }
    let res = 0;
    for (let arr of dp) {
      arr.forEach(vv => {
        res += vv;
      });
    }
    return res;
  };

代码

复杂度

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

jiaqiliu37 commented 2 years ago

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

        for _ in range(k):
            dp_cur = [[0]*n for i in range(n)]
            for r, row_cur in enumerate(dp):
                for c, val in enumerate(row_cur):
                    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:
                            dp_cur[r + dr][c + dc] += val/8

            dp = dp_cur

        return sum(map(sum, dp))

Time complexity O(n^2k) Space complexity O(n^2)

zol013 commented 2 years ago

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        r, c = row, column
        dp = [[0] * n for _ in range(n)]
        dp[r][c] = 1

        for _ in range(k):
            dp2 = [[0] * n for _ in range(n)]
            for r, row in enumerate(dp):
                for c, val in enumerate(row):
                    if val > 0:
                        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))

watchpoints commented 2 years ago

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function(n, k, row, column) {
    function isOut(r,c) {
        return r < 0 || c < 0 || r >= n || c >= n;
    }
    // dp[r][c][steps]: 已经走了steps步，且当前位置在[r,c]的概率。
    let dp1 = new Array(n).fill(0).map(i => new Array(n).fill(0)); // steps-1
    let dp2 = new Array(n).fill(0).map(i => new Array(n).fill(0)); // steps
    dp1[row][column] = 1;
    let steps = 1;
    let next = [[2,-1], [2,1], [-2,1], [-2,-1], [1,2], [1,-2], [-1,2], [-1,-2]];
    while (steps <= k) {
        for (let r=0; r<n; r++) {
            for (let c=0; c<n; c++) {
                for (let [nx, ny] of next) {
                    let adder = isOut(r+nx, c+ny) ? 0 : dp1[r+nx][c+ny];
                    dp2[r][c] += adder / 8;
                }
            }
        }
        // 滚动数组
        let t = dp2;
        dp2 = dp1;
        dp1 = t;
        for (let r=0;r<n;r++) {
            for(let c=0; c<n; c++) {
                dp2[r][c] = 0;
            }
        }
        steps += 1;
    }
    let res = 0;
    for (let r=0;r<n;r++) {
        for(let c=0; c<n; c++) {
            res += dp1[r][c];
        }
    }
    return res;
};

alongchong commented 2 years ago

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;
    }
}

declan92 commented 2 years ago

思路
从初始点移动k步之后,可能有x个位置且每个位置的概率不同,将x个位置概率相加为结果;
每走一步,需要从原始的位置(origin)和概率扩散到新的位置(dest)和概率;
扩散有8个方向,如果目标位置dest在棋盘内,则destProbility = destProbility+originProbility/8;
java code

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        double[][] dp = new double[n][n];
        dp[row][column] = 1;
        int[][] directs = { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } };
        for (int i = 0; i < k; i++) {
            double[][] nextDp = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (dp[r][c] == 0)
                        continue;
                    for (int[] dir : directs) {
                        int newR = r + dir[0];
                        int newC = c + dir[1];
                        if (newR >= 0 && newR < n && newC >= 0 && newC < n) {
                            nextDp[newR][newC] += dp[r][c] / 8.0;
                        }
                    }
                }
            }
            dp = nextDp;
        }
        double ans = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                ans+=dp[r][c];
            }
        }
        return ans;
    }
}

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

feifan-bai commented 2 years ago

思路 1.DP

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> 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(KNN)
空间复杂度：O(N*N)

JudyZhou95 commented 2 years ago

代码

def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        ans = [[0 for _ in range(n)] for _ in range(n)]
        ans[row][column] = 1
        dic = [(-2,1), (-1,2), (1,2), (2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)]
        for i in range(k):
            ans2 = [[0 for _ in range(n)] for _ in range(n)]

            for r in range(n):
                for c in range(n):
                    for a, b in dic:
                        if r+a >= 0 and c+b >= 0 and r+a < n and c+b < n:
                            ans2[r+a][c+b] += 0.125* ans[r][c]

            ans = ans2

        a = 0

        for i in range(n):
            for j in range(n):
                 a += ans[i][j]

        return a

复杂度

TC: O(kN^2) SC: O(N^2)

honeymeng-hub commented 2 years ago

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: dp = [[[0] * n for in range(n)] for in range(k + 1)] dp[0][row][column] = 1 s = set([(row, column)]) news = [] for i in range(1, k + 1): for e in s: px, py = e[0], e[1] for dx, dy in [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]: x = px + dx y = py + dy if 0 <= x < n and 0 <= y < n: dp[i][x][y] += dp[i - 1][px][py] / 8 news.append((x, y)) s = set(news) news = [] ans = 0 for i in range(n): ans += sum(dp[k][i]) return ans

iambigchen commented 2 years ago

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function(n, k, row, column) {
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
    let dir = [[-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1]];
    dp[row][column] = 1
    for (let step = 1; step <= k; step++) {
        let dpTemp = new Array(n).fill(0).map(() => new Array(n).fill(0))
        for(let i = 0; i < n; i++) {
            for(let j = 0; j < n; j++) {
                for(let d = 0; d < dir.length; d++) {
                    let direction = dir[d]
                    let lastR = i - direction[0]
                    let lastC = j - direction[1]
                    if (lastC < n && lastC >= 0 && lastR < n && lastR >= 0) {
                        dpTemp[i][j] += dp[lastR][lastC] * 0.125;
                    }
                }
            }
        }
        dp = dpTemp
    }
    let res = 0
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            res += dp[i][j]
        }
    }
    return res
};

复杂度分析

令 n 为数组长度。

时间复杂度：$O(k*n**2)$
空间复杂度：$O(n**2)$

biscuit279 commented 2 years ago

思路：不断计算概率，累加

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
        ans = sum(map(sum, dp))
        return ans

时间复杂度：O（N^2*K）空间复杂度：O（N^2）

stackvoid commented 2 years ago

思路

DP

代码

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;
    }
}

复杂度分析

Time O(N) Space O(N)

eliassama commented 2 years ago


/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */

var knightProbability = function(n, k, row, column) {
    function isOut(r,c) {
        return r < 0 || c < 0 || r >= n || c >= n;
    }
    // dp[r][c][steps]: 已经走了steps步，且当前位置在[r,c]的概率。
    let dp1 = new Array(n).fill(0).map(i => new Array(n).fill(0)); // steps-1
    let dp2 = new Array(n).fill(0).map(i => new Array(n).fill(0)); // steps
    dp1[row][column] = 1;
    let steps = 1;
    let next = [[2,-1], [2,1], [-2,1], [-2,-1], [1,2], [1,-2], [-1,2], [-1,-2]];
    while (steps <= k) {
        for (let r=0; r<n; r++) {
            for (let c=0; c<n; c++) {
                for (let [nx, ny] of next) {
                    let adder = isOut(r+nx, c+ny) ? 0 : dp1[r+nx][c+ny];
                    dp2[r][c] += adder / 8;
                }
            }
        }
        // 滚动数组
        let t = dp2;
        dp2 = dp1;
        dp1 = t;
        for (let r=0;r<n;r++) {
            for(let c=0; c<n; c++) {
                dp2[r][c] = 0;
            }
        }
        steps += 1;
    }
    let res = 0;
    for (let r=0;r<n;r++) {
        for(let c=0; c<n; c++) {
            res += dp1[r][c];
        }
    }
    return res;
};

demo410 commented 2 years ago

public double knightProbability(int n, int k, int row, int column) {
        double[][] dp = new double[n][n];
        dp[row][column] = 1;
        int[][] directs = { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } };
        for (int i = 0; i < k; i++) {
            double[][] nextDp = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (dp[r][c] == 0)
                        continue;
                    for (int[] dir : directs) {
                        int newR = r + dir[0];
                        int newC = c + dir[1];
                        if (newR >= 0 && newR < n && newC >= 0 && newC < n) {
                            nextDp[newR][newC] += dp[r][c] / 8.0;
                        }
                    }
                }
            }
            dp = nextDp;
        }
        double ans = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                ans+=dp[r][c];
            }
        }
        return ans;
    }

kite-fly6618 commented 2 years ago

思路

dp

代码

var knightProbability = function(N, K, r, c) {
  let dir = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]
  let dp=new Array(N)
  let dp2=new Array(N)
  for (let i=0;i<N;i++){
      dp[i]=new Array(N).fill(1)
      dp2[i]=new Array(N).fill(0)
  }
  let lastTable=dp,curTable=dp2
  for (let i=1;i<=K;i++){
    for (let curR=0;curR<N;curR++){
      for (let curC=0;curC<N;curC++){
        curTable[curR][curC]=0
        for (let [dR,dC] of dir){
          if(curR+dR>=0&&curR+dR<N&&curC+dC>=0&&curC+dC<N){
            curTable[curR][curC]+=(lastTable[curR+dR][curC+dC]/8)
          }
        }
      }
    }
    let temp=lastTable
    lastTable=curTable
    curTable=temp
  }
  return lastTable[r][c]
}

复杂度

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

Hacker90 commented 2 years ago

class Solution {

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) {

    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;
}

}

junbuer commented 2 years ago

思路

动态规划

马的移动方式，$(dr,dc)$ 可以为 (2, 1),(2,1), (2, -1),(2,−1), (-2, 1),(−2,1), (-2, -1),(−2,−1), (1, 2),(1,2), (1, -2),(1,−2), (-1, 2),(−1,2), (-1, -2)(−1,−2)。

$dp[r][c][steps]$表示马在$(r, c)$位置移动$steps$步后仍然留在棋盘上的概率，则有状态转移方程如下： $dp[r][c][steps] = \sum_{dr, dc}dp[r + dr][c + dc][steps - 1]/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 xrange(n)]
dp[row][column] = 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(k*n^2)$
空间复杂度：$O(n)$

CodingProgrammer commented 2 years ago

思路

记忆化递归

代码

class Solution {
    int[][] dirs;
    double[][][] memo;
    int STEP;
    int N;
    public double knightProbability(int n, int k, int row, int column) {
        this.dirs = new int[][]{{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
        this.memo = new double[n][n][k + 1];
        this.STEP = 8;
        this.N = n;

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

    private double dfs(int n, int k, int row, int column) {
        if (row < 0 || row >= n || column < 0 || column >= n) return 0.0;
        if (k == 0) return 1.0;
        if (this.memo[row][column][k] != 0.0) return this.memo[row][column][k];

        double res = 0.0;
        for (int[] dir : dirs) {
            res += dfs(n, k - 1, row + dir[0], column + dir[1]) / 8.0;
        }
        this.memo[row][column][k] = res;
        return res;
    }
}

复杂度

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

Today-fine commented 2 years ago

学习别人的解法


class Solution 
{
public:

    double walk(int N,int k,int r,int c,int step,vector<vector<vector<double>>>& dp)
    {
        //如果越界，返回0
        if(r<0||c<0||r>=N||c>=N)
            return 0;
        //如果没有越界，且走完K步
        if(step==k)
            return 1;
        double res=0;
        if(dp[step][r][c]!=0)
            res=dp[step][r][c];//dp备忘录的用法
        else
        {
            res+=walk(N,k,r+1,c-2,step+1,dp);
            res+=walk(N,k,r+1,c+2,step+1,dp);
            res+=walk(N,k,r+2,c-1,step+1,dp);
            res+=walk(N,k,r+2,c+1,step+1,dp);
            res+=walk(N,k,r-1,c-2,step+1,dp);
            res+=walk(N,k,r-1,c+2,step+1,dp);
            res+=walk(N,k,r-2,c-1,step+1,dp);
            res+=walk(N,k,r-2,c+1,step+1,dp);
            dp[step][r][c]=res;
        }        
        return res/8.0;
    }

    double knightProbability(int N, int K, int r, int c) 
    {
        vector<vector<vector<double>>> dp(K+1,vector<vector<double>>(N,vector<double>(N,0)));
        return walk(N,K,r,c,0,dp);
    }
};

Jay214 commented 2 years ago

/**
 * @param {number} N
 * @param {number} K
 * @param {number} r
 * @param {number} c
 * @return {number}
 */
var knightProbability = function (N, K, r, c) {
    let keyValue = {};
    let getTimes = function (N, K, r, c) {
        if (r < 0 || r >= N || c < 0 || c >= N) {
            return 0;
        }
        if (K == 0)
            return 1;
        let key = K + "|" + r + "|" + c
        if (keyValue[key])
            return keyValue[key];
        //8种跳法
        let times = getTimes(N, K - 1, r + 2, c + 1)
            + getTimes(N, K - 1, r + 2, c - 1)
            + getTimes(N, K - 1, r - 2, c + 1)
            + getTimes(N, K - 1, r - 2, c - 1)
            + getTimes(N, K - 1, r + 1, c + 2)
            + getTimes(N, K - 1, r - 1, c + 2)
            + getTimes(N, K - 1, r + 1, c - 2)
            + getTimes(N, K - 1, r - 1, c - 2);
        keyValue[key] = times;
        return times;
    }
    return getTimes(N, K, r, c) / Math.pow(8, K);
};

leetcode-pp / 91alg-6-daily-check

【Day 59 】2022-02-08 - 688. “马”在棋盘上的概率 #69

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

入选理由

题目地址

前置知识

题目描述

思路

代码

Idea

Code

Complexity:

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

思路

golang代码

复杂度

思路

代码

思路

思路

代码

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

思路一

代码

复杂度分析

思路

代码

时间复杂度

思路

代码

关键点

代码

688. 骑士在棋盘上的概率

o n2k on2

思路

代码

复杂度

代码

复杂度

代码

思路：不断计算概率，累加

思路

代码

复杂度分析

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

复杂度