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