骑士在棋盘上的概率

题目描述：

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

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

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

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

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

思路:

用动态规划做最省力了，dp[i][j][p] += dp[i-1][x][y]/8，这个位置的概率等于周围8个的概率分别处以8再相加。

代码:

var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}

func knightProbability(n int, k int, row int, column int) float64 {
    if k == 0{
        return 1
    }
    dp := make([][][]float64, k+1)
    for i:=0;i<=k;i++{
        dp[i] = make([][]float64, n)
        for j:=0; j<n;j++{
            dp[i][j] = make([]float64, n)
            for p:=0; p<n; p++{
                if i == 0{
                    dp[i][j][p] = 1
                }else{
                    for _,v := range dirs{
                        x := j+v.i
                        y := p+v.j
                        if x>=0 && x<n && y>=0 &&y <n{
                            dp[i][j][p] += dp[i-1][x][y]/8
                        }
                    }
                }
            }
        }
    }
    return dp[k][row][column]
}

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了77.42%的用户
内存消耗：3.6 MB, 在所有 Go 提交中击败了70.97%的用户