688. 骑士在棋盘上的概率 - Kotlin 动态规划

Problem: 688. 骑士在棋盘上的概率

思路

设为第i次移动时，棋子停留在的可能性

由于不论是否会走出棋盘，棋子向八个方向移动的概率都为0.125

对于第i次情况的每一个位置，枚举其可能移动到的位置，对于其中那些停留在棋盘上的情况，其i+1次的可能性即为

最终输出第k次情况下棋盘上所有位置的可能性之和即可

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun knightProbability(n: Int, k: Int, row: Int, column: Int): Double {
        val dp = Array(k + 1) { Array(n) { DoubleArray(n) { (0).toDouble() } } }
        dp[0][row][column] = (1).toDouble()

        for (i in 0 until k) {
            for (r in 0 until n) {
                for (c in 0 until n) {
                    if (r - 1 >= 0 && c - 2 >= 0) dp[i + 1][r - 1][c - 2] += dp[i][r][c] * 0.125
                    if (r - 2 >= 0 && c - 1 >= 0) dp[i + 1][r - 2][c - 1] += dp[i][r][c] * 0.125
                    if (r - 1 >= 0 && c + 2 < n) dp[i + 1][r - 1][c + 2] += dp[i][r][c] * 0.125
                    if (r + 2 < n && c - 1 >= 0) dp[i + 1][r + 2][c - 1] += dp[i][r][c] * 0.125
                    if (r + 1 < n && c - 2 >= 0) dp[i + 1][r + 1][c - 2] += dp[i][r][c] * 0.125
                    if (r - 2 >= 0 && c + 1 < n) dp[i + 1][r - 2][c + 1] += dp[i][r][c] * 0.125
                    if (r + 1 < n && c + 2 < n) dp[i + 1][r + 1][c + 2] += dp[i][r][c] * 0.125
                    if (r + 2 < n && c + 1 < n) dp[i + 1][r + 2][c + 1] += dp[i][r][c] * 0.125
                }
            }
        }

        var sum = (0).toDouble()
        for (r in 0 until n) {
            for (c in 0 until n) {
                sum += dp[k][r][c]
            }
        }
        return sum
    }
}