688 骑士在棋盘上的概率

· 2024-12-7   · 次阅读   · 字数统计: 497字   · 阅读时长≈ 2分钟

  · 算法题解   · LeetCode

题目链接

688. 骑士在棋盘上的概率

分析

对于原问题：马在 $(i, j)$ 处走 $step$ 步后在棋盘上的概率，是由马可以走的八个方向 $(x, y)$ 处走 $step - 1$ 步后在棋盘上的概率这个子问题计算而来

显而易见的，我们可以自顶向下的使用递归来解决该问题，并使用记忆化搜索剪枝计算

那么，更进一步的，将问题自底向上进行计算，使用动态规划解决该问题

定义数组 $f[step][i][j]$，代表从 $(i, j)$ 出发走 $step$ 步后马在棋盘上的概率

那么状态转移方程为 $f[step][i][j] = \frac{1}{8} \sum_{(x, y)} f[step - 1][x][y]$，$(x, y)$ 的取值为马可以走的八个方向

对于 $step = 0$ 时，答案均为 $1$

对于棋盘外的情况来说，答案均为 $0$ ，所以使用 $check$ 函数跳过棋盘外的情况即可

从 $step = 1$ 时开始计算即可，答案为 $f[k][row][column]$

代码实现

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<pair<int, int>> dir = {{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}};

        vector<vector<vector<double>>> f(k + 1, vector<vector<double>>(n, vector<double>(n)));

        fill(f[0].begin(), f[0].end(), vector<double>(n, 1));

        auto check = [&](int x, int y) -> bool {return x >= 0 && x < n && y >= 0 && y < n;};
  
        for(int step = 1; step <= k; ++step)
        {
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    for(auto& [dx, dy] : dir)
                        if(check(i + dx, j + dy))
                            f[step][i][j] += f[step - 1][i + dx][j + dy];
                    f[step][i][j] /= 8;
                }
            }
        }

        return f[k][row][column];
    }
};

复杂度分析

  • 时间复杂度：$O(kn^2)$
  • 空间复杂度：$O(kn^2)$，使用滚动数组可优化至 $O(n^2)$