On an n x n chessboard, there is a knight. Given the starting coordinates, find the probability that the knight remains on the board after k moves.

Imagine the knight jumping in a "cube" of height k+1. The knight starts at the k-th layer, and each jump moves it down one layer until it exhausts its moves. The process ends at layer 0. Initially, the knight is guaranteed to be within the board.

Work backward layer by layer to calculate the probability that the knight, starting from the origin, remains on the board after k moves.

You can first use DFS to identify the position dependencies and then convert it into a DP solution.

DFS

Deep search with a 3D array for caching. Base case: if the number of jumps is 0, return 1. Also, do not proceed with recursion if the knight moves out of bounds.

Update coordinates with offsets, decrement the jump count, and pass to the next layer of recursion.

The accumulated result should be divided by 8, as there is only a 1/8 probability of jumping in any given direction.

go

func knightProbability(n int, k int, row int, column int) float64 {
	visited := make([][][]float64, n)
	for i := range visited {
		visited[i] = make([][]float64, n)
		for j := range visited[i] {
			visited[i][j] = make([]float64, k+1)
		}
	}
	return DFS(n, k, row, column, visited)
}
func DFS(n, k, i, j int, visited [][][]float64) float64 {
	dirs := [8][2]int{{-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, -1}, {2, 1}}
	if k == 0 {
		return 1
	}
	if visited[i][j][k] > 0 {
		return visited[i][j][k]
	}
	res := 0.0
	for _, dir := range dirs {
		x := i + dir[0]
		y := j + dir[1]
		if x > n-1 || y > n-1 || x < 0 || y < 0 {
			continue
		}
		res += DFS(n, k-1, x, y, visited) / 8
	}
	visited[i][j][k] = res
	return res
}

DP

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

2D DP

Space compression is also applicable here. Start DP from the 1st layer, keeping only the data from the previous layer.

go

func knightProbability(n int, k int, row int, column int) float64 {
	dirs := [8][2]int{{-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, -1}, {2, 1}}
	dp := [2][][]float64{}
	for i := range dp {
		dp[i] = make([][]float64, n)
		for j := range dp[i] {
			dp[i][j] = make([]float64, n)
		}
	}
	fill(dp[0], 1)
	for l := 1; l < k+1; l++ {
		fill(dp[l&1], 0)
		for i := range dp[0] {
			for j := range dp[0][0] {
				for _, dir := range dirs {
					x := i + dir[0]
					y := j + dir[1]
					if x < n && x >= 0 && y < n && y >= 0 {
						dp[l&1][i][j] += dp[(l-1)&1][x][y] / 8
					}
				}
			}
		}
	}
	return dp[k&1][row][column]
}
func fill(curr [][]float64, val float64) {
	for i := range curr[0] {
		for j := range curr[0] {
			curr[i][j] = val
		}
	}
}

java

public class Solution {
    public double knightProbability(int n, int k, int r, int c) {
        int[][] dirs = new int[][]{{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
        float[][][] dp = new float[2][n][n];
        fill(dp[0], 1);
        for (int l = 1; l < k + 1; l++) {
            fill(dp[l & 1], 0);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= n || x < 0 || y >= n || y < 0) continue;
                        dp[l & 1][i][j] += dp[l - 1 & 1][x][y] / 8;
                    }
                }
            }
        }
        return dp[k & 1][r][c];
    }

    void fill(float[][] curr, float val) {
        for (float[] floats : curr) {
            Arrays.fill(floats, val);
        }
    }
}