LeetCode 688. 骑士在棋盘上的概率

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 688. 骑士在棋盘上的概率

思路分析

解法一：动态规划（推荐）

核心思路：

设 dp[step][i][j] 表示走了 step 步后位于 (i,j) 的概率。

step=0 时起点概率为 1，其余为 0。

每一步把概率向 8 个骑士方向平均分配。

只用两层滚动数组即可。

复杂度分析：

时间复杂度：O(k * n^2)，其中 n 表示棋盘大小，k 表示步数。

空间复杂度：O(n^2)。

class Solution {
    private static final int[][] DIRS = {
            {1, 2}, {2, 1}, {-1, 2}, {-2, 1},
            {1, -2}, {2, -1}, {-1, -2}, {-2, -1}
    };

    public double knightProbability(int n, int k, int row, int column) {
        double[][] dp = new double[n][n];
        dp[row][column] = 1.0;

        for (int step = 1; step <= k; step++) {
            double[][] next = new double[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] == 0) {
                        continue;
                    }

                    for (int[] d : DIRS) {
                        int ni = i + d[0];
                        int nj = j + d[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                            next[ni][nj] += dp[i][j] / 8.0;
                        }
                    }
                }
            }
            dp = next;
        }

        double total = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                total += dp[i][j];
            }
        }

        return total;
    }
}

func knightProbability(n int, k int, row int, column int) float64 {
	dirs := [][2]int{{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}}
	dp := make([][]float64, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]float64, n)
	}
	dp[row][column] = 1.0

	for step := 1; step <= k; step++ {
		next := make([][]float64, n)
		for i := 0; i < n; i++ {
			next[i] = make([]float64, n)
		}

		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dp[i][j] == 0 {
					continue
				}
				for _, d := range dirs {
					ni := i + d[0]
					nj := j + d[1]
					if ni >= 0 && ni < n && nj >= 0 && nj < n {
						next[ni][nj] += dp[i][j] / 8.0
					}
				}
			}
		}
		dp = next
	}

	total := 0.0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			total += dp[i][j]
		}
	}

	return total
}

相似题目

题目	难度	考察点
935. 骑士拨号器	中等	DP
576. 出界的路径数	中等	DP
494. 目标和	中等	DP
62. 不同路径	中等	DP
413. 等差数列划分	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/60062286