【Day 59 】2023-04-13 - 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 次或跳到了棋盘外面。

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

[Zoeyzyzyzy]

package DP;

class Solution {
    // 记忆化搜索：向6个方向中每个方向前进的概率为1/8，只要没有走出去都可以增加1/8的概率，路径的1/8概率相乘为这条路径的概率，
    // 然后再继续前进，求出所有可能路径的概率和
    private static final int[][] directions = { { -2, 1 }, { -2, -1 }, { 2, 1 }, { 2, -1 }, { -1, 2 }, { -1, -2 },
            { 1, 2 }, { 1, -2 } };
    double[][][] memo;

    public double knightProbability(int n, int k, int row, int column) {
        this.memo = new double[n][n][k + 1];
        return dfs(n, k, row, column);
    }

    private double dfs(int n, int k, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        if (memo[i][j][k] != 0) {
            return memo[i][j][k];
        }

        double ans = 0;
        for (int[] direction : directions) {
            ans += dfs(n, k - 1, i + direction[0], j + direction[1]) / 8;
        }
        memo[i][j][k] = ans;
        return ans;
    }

    // dp: 通过观察记忆化搜索，可知在dfs中有3个参数在变化，参考有:
    // dp[i][j][k]表示第k步在（i,j)处的概率为dp[i][j][k].
    // 当 k = k(输入的参数时)，可知其存在的(i,j)为最后路径存在的(i,j)将他们相加则得到最后总概率。
    // 转移方程：dp[i][j][k] = 累加(从1到8) dp[i][j][k - 1]/8;要走到[i,j]的位置，必须要先走了k-1 步，到[i,j]8个方向的一个位置。
    // private static final int[][] directions = { { -2, 1 }, { -2, -1 }, { 2, 1 }, { 2, -1 }, { -1, 2 }, { -1, -2 },
    //         { 1, 2 }, { 1, -2 } };

    public double knightProbability1(int n, int k, int row, int column) {
        double[][][] dp = new double[n][n][k + 1];
        for (int kk = 0; kk <= k; kk++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (kk == 0) {
                        dp[i][j][kk] = 1;
                    } else {
                        for (int[] direction : directions) {
                            int x = i + direction[0];
                            int y = j + direction[1];
                            if (x >= 0 && y >= 0 && x < n && y < n) {
                                dp[i][j][kk] += dp[x][y][kk - 1] / 8.0;
                            }
                        }
                    }
                }
            }
        }
        return dp[row][column][k];
    }
}

[lp1506947671]

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)]
        for step in range(k + 1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8
        return dp[k][row][column]

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

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

[kofzhang]

思路

多层动态规划，当前位置当前步骤的下一步概率为上一步周边八个位置概率和的八分之一。

复杂度

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

代码

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

[LIMBO42]

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, 0)));
        dp[0][row][column] = 1;
        vector<pair<int, int>> dir = {{-2, 1}, {2, 1}, {-2, -1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
        for(int p = 1; p <= k; ++p) {
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    for(int x = 0; x < 8; ++x) {
                        int r = i + dir[x].first;
                        int c = j + dir[x].second;
                        if(r >= 0 && r < n && c >= 0 && c < n) {
                            dp[p][i][j] += dp[p-1][r][c] / 8.0;
                        }
                    }
                }
            }
        }
        double ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                ans += dp[k][i][j];
            }
        }
        return ans;
    }
};

[huizsh]

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

[Abby-xu]

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

        @lru_cache(None)
        def sol(i, j, k):
            if k == 0:
                return 1
            curr = 0
            for di, dj in dirs:
                i2, j2 = i + di, j + dj
                if 0 <= i2 < n and 0 <= j2 < n:
                    curr += 0.125 * sol(i2, j2, k - 1)
            return curr

        return sol(row, column, k)

[Meisgithub]

class Solution {
public:
    int neighbors[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n, 0.0)));
        dp[0][row][column] = 1;
        for (int l= 1; l <= k; ++l)
        {
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    for (auto &neighbor : neighbors)
                    {
                        int newI = i + neighbor[0];
                        int newJ = j + neighbor[1];
                        if (newI >= 0 && newI < n && newJ >= 0 && newJ < n)
                        {
                            dp[l][i][j] += dp[l - 1][newI][newJ] * 0.125;
                        }
                    }
                }
            }
        }
        double ans = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                ans += dp[k][i][j];
            }
        }
        return ans;
    }
};

[RestlessBreeze]

code

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

        vector<vector<int>> dic = {{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}};

        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
        dp[0][column][row] = 1;
        for (int step = 1; step < k + 1; step++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    for (int m = 0; m < 8; m++)
                    {
                        int lasti = i - dic[m][0];
                        int lastj = j - dic[m][1];
                        if (lasti >= 0 && lasti < n && lastj >= 0 && lastj < n)
                            dp[step][i][j] += dp[step - 1][lasti][lastj] * 1 / 8;
                    }
                }
            }
        }

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

[csthaha]

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function(n, k, row, column) {
    // 可移动的方向
    const direction = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];
    // 初始化状态
    const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));
    // 当前位置走到下个位置的概率为 1/8: dp[step][i][j] += dp[step - 1][ni][nj] / 8
    for(let step = 0; step <= k; step++) {
        for(let i = 0; i < n; i++) {
            for(let j = 0; j < n; j++) {
                if(step === 0) {
                    dp[step][i][j] = 1;
                } else {
                    for(const [row, col] of direction) {
                        const ni = i + row;
                        const nj = j + col;
                        if(ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            dp[step][i][j] += dp[step - 1][ni][nj] / 8
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column]
};

[chanceyliu]

代码

const dirs = [
  [-2, -1],
  [-2, 1],
  [2, -1],
  [2, 1],
  [-1, -2],
  [-1, 2],
  [1, -2],
  [1, 2],
];

function knightProbability(
  n: number,
  k: number,
  row: number,
  column: number
): number {
  const dp = new Array(k + 1)
    .fill(0)
    .map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));
  for (let step = 0; step <= k; step++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (step === 0) {
          dp[step][i][j] = 1;
        } else {
          for (const dir of dirs) {
            const ni = i + dir[0],
              nj = j + dir[1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
              dp[step][i][j] += dp[step - 1][ni][nj] / 8;
            }
          }
        }
      }
    }
  }
  return dp[k][row][column];
}

[FireHaoSky]

思路：动态规划，只考虑当前步数，由前面的累计，dp[k][i][j] = 累加dp[k-1][ni][nj]

代码：pthon

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)]
        for step in range(k+1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2,1),(-2,-1),(2,1),(2,-1),(1,2),(1,-2),(-1,2),(-1,-2)):
                            ni,nj = i+di,j+dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step-1][ni][nj]/8
        return dp[k][row][column]

复杂度分析：

"""
时间复杂度：O(knn)
空间复杂度：O(knn)
"""

[Diana21170648]

思路

动态规划+三维数组

class Slution:
    def knightprobability(self,n:int,k:int,row:int,column:int)->float:
        delta=[(-2,1),(-2,-1),(-1,2),(-1,-2),(1,2),(1,-2),(2,-1),(2,1)]
        dp=[[[0]*(k+1)for _ in  range(n)] for _ in  range(n)]
        for i in range(n):
            for j in range(n):
                dp[i][j][0] = 1
                for step in range(1,K+1):
                    for i in range(n):
                        for j in range(n):
                            if step==0:
                                dp[i][j][0]=1
                            else:
                                for dx,dy in delta:
                                    x,y=i+dx,j+dy
                                    if n>x>=0 and n>y>=0:
                                        dp[i][j][step]+=dp[i][j][step-1]*0.125
                                        return dp[row][column][k]

**复杂度分析**
- 时间复杂度：O(kN^2)，其中 N为棋盘的大小。
- 空间复杂度：O(kN^2)

[JasonQiu]

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
        directions = [(1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
        for step in range(k):
            dp_k = [[0 for _ in range(n)] for _ 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 0 <= x < n and 0 <= y < n:
                            dp_k[x][y] += dp[i][j]
            dp = dp_k
        return sum(map(sum, dp)) / float(8 ** k)

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

[NorthSeacoder]

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function (n, k, r, c) {
    //在棋盘上
    const isOnBoard = (row, col) => row < n && row >= 0 && col < n && col >= 0;

    //移动后在棋盘上的位置
    const move = (row, col, res) => {
        const steps = [[-1, -2], [-1, 2], [-2, -1], [-2, 1], [1, 2], [1, -2], [2, 1], [2, -1]]
        for (const step of steps) {
            const oriRow = row - step[0];
            const oriCol = col - step[1];

            if (isOnBoard(oriRow, oriCol)) {
                res[row][col] += dp[oriRow][oriCol] * 0.125
            }
        }
    }

    //dp[i][j]跳到点(i,j)仍留在棋盘上的概率
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    dp[r][c] = 1;
    for (let i = 0; i < k; i++) {
        const res = new Array(n).fill(0).map(() => new Array(n).fill(0));

        for (let row = 0; row < n; row++) {
            for (let col = 0; col < n; col++) {
                move(row, col, res)
            }
        }
        dp = res
    };
    // console.log(dp)
    return dp.reduce((sum, arr) => sum += arr.reduce((s, c) => s += c, 0), 0)

[chocolate-emperor]

class Solution {
public:

// row column, k, 
// 00 n-1,n-1
// 求k次move后留在棋盘上的方案集合的数量  dp[i][] a/b = prob
// 
// 划分标准:最后一次move的起始位置,dp[i][x][y] i次move到达棋盘x，y的方案数量
// 我为人人， dp[i][x][y] 去更新dp[i+1][nex][ney]的数量
// res = dp[k][0...n-1][0..n-1]
    double dp[104][25][25];
    double knightProbability(int n, int k, int row, int column) {
        memset(dp, 0, sizeof(dp));
        dp[0][row][column] = 1;
        int dx[] = {2,2,1,-1,-2,-2,-1,1};
        int dy[] = {1,-1,2,2,1,-1,-2,-2};

        for(int i = 0; i<=k; i++){ 
            for(int x = 0; x<n; x++){
                for(int y = 0; y<n; y++){
                    if(i!=0)  dp[i][x][y] = dp[i][x][y]/8;

                    for(int j= 0; j<8; j++){
                        int ne_x = x+dx[j], ne_y = y+dy[j];
                        if(ne_x<0 || ne_x >=n || ne_y<0 || ne_y >=n)    continue;
                        dp[i+1][ne_x][ne_y] += dp[i][x][y];
                    }
                }
            }

        }
        double res = 0;
        for(int x = 0; x<n;x++){
            for(int y = 0; y<n;y++){
                res += dp[k][x][y];
                //cout<<res<<" "<<dp[k][x][y]<<endl;
            }
        }
        return res;
    }
};

[harperz24]

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)]
        for step in range(k + 1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8
        return dp[k][row][column]

# dp 3d
# time: O(k × n**2)
# space: O(k × n**2)

[wangzh0114]

class Solution {
public:
    vector<vector<int>> dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (auto & dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
};

[Size-of]

/**

• @param {number} n
• @param {number} k
• @param {number} row
• @param {number} column

• @return {number} */ 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]]

  let dp = Array.from({length: n }).map(() => Array.from({length: n }).fill(0)) dp[row][column] = 1

  for(let step = 1; step <= k; step++){ const tempDP = Array.from({length: n }).map(() => Array.from({length: n }).fill(0)) for(let i = 0; i < n; i++){ for(let j = 0; j < n; j++){ for(const m of MOVE){ const lastR = i - m[0] const lastC = j - m[1] if (lastR >= 0 && lastR < n && lastC >= 0 && lastC < n){ tempDP[i][j] += dp[lastR][lastC] * 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 };

[Hughlin07]

class Solution {

int[] dir1= {-2,-1,1,2,2,1,-1,-2};
int[] dir2= {1,2,2,1,-1,-2,-2,-1};

public double knightProbability(int n, int k, int row, int col) {
    if(k==0){
        return 1.0;
    }
    double[][][] dp= new double[30][30][101];

    for(int i=0; i<30; i++){
        for(int j=0; j<30; j++){
            for(int l=0; l<101; l++){
                dp[i][j][l]= 0.0;
            }
        }
    }

    return solve(n,k,row,col,dp);
}

public boolean isValid(int i, int j, int n){
    if(i<0 || j<0 || i>=n || j>=n){
        return false;
    }

    return true;
}

public double solve(int n, int k, int i, int j, double[][][] dp){
    if(k<=0){
        return 1;
    }

    if(i<0 || j<0 || i>=n || j>=n){
        return 0.0;
    }

    if(dp[i][j][k]!= 0.0){
        return dp[i][j][k];
    }

    double res=0.0;
    double num= 1.0;
    double denom= 8.0;
    for(int l=0; l<8; l++){
        int x= i+dir1[l];
        int y= j+dir2[l];
        if(isValid(x,y,n)){
            res+= solve(n,k-1,x,y,dp)*(num/denom);
        }
    }

    return dp[i][j][k]= res;
}

}

[bookyue]

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

    private static final int[][] DIRS = new int[][]{{-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {-2, 1}, {-2, -1}, {2, 1}, {2, -1}};

    public double knightProbability(int n, int k, int row, int column) {
        return dfs(n, row, column, k, new double[n][n][k + 1]);
    }

    private double dfs(int n, int x, int y, int k, double[][][] memo) {
        if (x < 0 || x >= n || y < 0 || y >= n) return 0D;

        if (k == 0) return 1D;

        if (memo[x][y][k] != 0) return memo[x][y][k];

        double ans = 0D;

        for (int[] dir : DIRS) {
            ans += dfs(n, x + dir[0], y + dir[1], k - 1, memo) / 8D;
        }

        memo[x][y][k] = ans;
        return ans;
    }

[aoxiangw]

class Solution:
  def knightProbability(self, n: int, K: int, r: int, c: int) -> float:
    dirs = [(1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

    dp = [[0] * n for _ in range(n)]
    dp[r][c] = 1

    for _ in range(K):
      newDp = [[0] * n for _ in range(n)]
      for i in range(n):
        for j in range(n):
          for dx, dy in dirs:
            x = i + dx
            y = j + dy
            if 0 <= x < n and 0 <= y < n:
              newDp[i][j] += dp[x][y]
      dp = newDp

    return sum(map(sum, dp)) / 8**K

time, space: O(kn^2), O(n^2)

[yingchehu]

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
        directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]]

        for _ in range(k):
            temp_dp = [[0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    for d in directions:
                        x, y = i - d[0], j - d[1]
                        if 0 <= x < n and 0 <= y < n:
                            temp_dp[i][j] += dp[x][y] * 0.125
            dp = temp_dp

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

[kangliqi1]

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

}

[Lydia61]

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

思路

马尔科夫链，动态规划

代码

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)]
        for step in range(k + 1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j] = 1
                    else:
                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < n and 0 <= nj < n:
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8
        return dp[k][row][column]

复杂度分析

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

[joemonkeylee]

思路

dp

代码

      public class Solution {
        static int[][] dirs = {new int[]{-2, -1}, new int[]{-2, 1}, new int[]{2, -1}, new int[]{2, 1}, new int[]{-1, -2}, new int[]{-1, 2}, new int[]{1, -2}, new int[]{1, 2}};

        public double KnightProbability(int n, int k, int row, int column) {
            double[,,] dp = new double[k + 1, n, n];
            for (int step = 0; step <= k; step++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (step == 0) {
                            dp[step, i, j] = 1;
                        } else {
                            foreach (int[] dir in dirs) {
                                int ni = i + dir[0], nj = j + dir[1];
                                if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                    dp[step, i, j] += dp[step - 1, ni, nj] / 8;
                                }
                            }
                        }
                    }
                }
            }
            return dp[k, row, column];
        }
    }

复杂度分析

• 时间复杂度：O(k*n2)
• 空间复杂度：O(k*n2)

[jmaStella]

思路

dp

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dir = 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[][] tempDp = new double[n][n];
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    for(int[] d: dir){
                        int x = i - d[0];
                        int y = j - d[1];
                        if(x>=0 && x<n && y>=0 && y<n){
                            tempDp[i][j] += dp[x][y]*0.125;
                        }
                    }
                }
            }
            dp = tempDp;
        }

        double result = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                result+=dp[i][j];
            }
        }
        return result;

    }
}

复杂度

时间 O(kN^2) 空间 O(kN^2)

[Jetery]

const int dirs[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {1, 2}, {2, 1}};
class Solution {
public:
    int n;
    double knightProbability(int n, int k, int row, int col) {
        this->n = n;
        vector<vector<vector<double>>> vis(n, vector<vector<double>>(n, vector<double>(k + 1)));
        return dfs(row, col, k, vis);
    }

    double dfs(int x, int y, int k, vector<vector<vector<double>>> &vis) {
        if (x < 0 || y < 0 || x >= n || y >= n) return 0;
        if (k == 0) return 1;
        if (vis[x][y][k]) return vis[x][y][k];  // 剪枝
        double ret = 0;
        for (auto dir : dirs) {
            int i = x + dir[0];
            int j = y + dir[1];
            ret += dfs(i, j, k - 1, vis) / 8.0;
        }
        vis[x][y][k] = ret;
        return ret;
    }

};

[X1AOX1A]

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

[Fuku-L]

代码

class Solution {
    static int[][] dirs = {{-2,-1}, {-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k+1][n][n];
        for(int step = 0; step <= k; step++){
            for(int i = 0; i<n; i++){
                for(int j = 0; j<n; j++){
                    if(step == 0){
                        dp[step][i][j] = 1;
                    } else {
                        for(int[] dir:dirs){
                            int ni = i+dir[0], nj = j + dir[1];
                            if(ni >= 0 && ni < n && nj >=0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }

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

复杂度分析

• 时间复杂度：O(k*N^2)，其中 N 为数组长度。
• 空间复杂度：O(k*N^2)

[snmyj]

class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dp = [[0 for i in range(N)] for j in range(N)]
        dp[r][c] = 1
        directions = [(1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
        for k in range(K):
            new_dp = [[0 for i in range(N)] for j in range(N)]
            for i in range(N):
                for j in range(N):
                    for d in directions:
                        x, y = i + d[0], j + d[1]
                        if x < 0 or x >= N or y < 0 or y >= N:
                            continue
                        new_dp[i][j] += dp[x][y]
            dp = new_dp
        return sum(map(sum, dp)) / float(8 ** K)

[yingchehu]

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False

        @lru_cache(None)
        def dp(picked, acc):
            if acc >= desiredTotal:
                return False
            if picked == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if picked & 1 << n == 0:
                    if not dp(picked | 1 << n, acc + n):
                        return True
            return False

        return dp(0, 0)