688.骑士在棋盘上的概率
688.骑士在棋盘上的概率
题解
两种解法，dp和dfs+memory，一样的思路
dp[step][i][j]即当前步数的概率，当前步数是由上一步的概率叠加来的，当前的位置=上一步的8个位置，理解这句话问题就迎刃而解了
代码
package main func knightProbabilityDP(n int, k int, row int, column int) float64 { var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}} dp := make([][][]float64, k+1) for step := range dp { dp[step] = make([][]float64, n) for i := 0; i < n; i++ { dp[step][i] = make([]float64, n) for j := 0; j < n; j++ { if step == 0 { dp[step][i][j] = 1 } else { for _, d := range dirs { prevX, pervY := i+d.i, j+d.j if prevX >= 0 && prevX < n && pervY >= 0 && pervY < n { dp[step][i][j] += dp[step-1][prevX][pervY] / 8 } } } } } } return dp[k][row][column] } func knightProbabilityDfsAndMemory(n int, k int, row int, column int) float64 { var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}} memory := make([][][]float64, k+1) for i := range memory { memory[i] = make([][]float64, n) for j := range memory[i] { memory[i][j] = make([]float64, n) } } var dfs func(n int, k int, row int, column int) float64 dfs = func(n int, k int, row int, column int) float64 { if k == 0 { return 1 } if memory[k][row][column] != 0 { return memory[k][row][column] } for _, d := range dirs { prevX, prevY := row+d.i, column+d.j if prevX >= 0 && prevX < n && prevY >= 0 && prevY < n { memory[k][row][column] += dfs(n, k-1, prevX, prevY) / 8 } } return memory[k][row][column] } return dfs(n, k, row, column) }
