区间dp算法

Posted on Edited on Views:

688. 骑士在棋盘上的概率

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution{
    //一个骑士有 8 种可能的走法，骑士会从中以等概率随机选择一种。部分走法可能会让骑士离开棋盘，
    // 另外的走法则会让骑士移动到棋盘的其他位置，并且剩余的移动次数会减少 1。
    //
    //定义 dp[step][i][j] 表示骑士从棋盘上的点 (i, j)(i,j) 出发，走了 step 步时仍然留在棋盘上的概率。
    // 特别地，当点 (i,j) 不在棋盘上时，dp[step][i][j] = 0 ；
    // 当点 (i,j) 在棋盘上且 step=0 时，dp[step][i][j]=1。
    // 对于其他情况，对坐标的偏移量，具体为 (-2, -1),(-2,1),(2,-1),(2,1),(-1,-2),(-1,2),(1,-2),(1,2)(−2,−1),(−2,1),(2,−1),(2,1),(−1,−2),(−1,2),(1,−2),(1,2) 共 88 种。

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