likes
comments
collection
share

【月度刷题计划同款】简单线性 DP 运用题

作者站长头像
站长
· 阅读数 44

题目描述

这是 LeetCode 上的 688. 骑士在棋盘上的概率 ，难度为 中等。

Tag : 「线性 DP」

在一个 n×nn \times nn×n 的国际象棋棋盘上，一个骑士从单元格 (row,column)(row, column)(row,column) 开始，并尝试进行 kkk 次移动。行和列是 从 000 开始 的，所以左上单元格是 (0,0)(0,0)(0,0) ，右下单元格是 (n−1,n−1)(n - 1, n - 1)(n−1,n−1) 。

象棋骑士有 888 种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

【月度刷题计划同款】简单线性 DP 运用题

每次骑士要移动时，它都会随机从 888 种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 kkk 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

示例 1：

输入: n = 3, k = 2, row = 0, column = 0

输出: 0.0625

解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：

输入: n = 1, k = 0, row = 0, column = 0

输出: 1.00000

提示:

  • 1<=n<=251 <= n <= 251<=n<=25
  • 0<=k<=1000 <= k <= 1000<=k<=100
  • 0<=row,column<=n0 <= row, column <= n0<=row,column<=n

线性 DP

定义 f[i][j][p]f[i][j][p]f[i][j][p] 为从位置 (i,j)(i, j)(i,j) 出发，使用步数不超过 ppp 步，最后仍在棋盘内的概率。

不失一般性考虑 f[i][j][p]f[i][j][p]f[i][j][p] 该如何转移，根据题意，移动规则为「八连通」，对下一步的落点 (nx,ny)(nx, ny)(nx,ny) 进行分情况讨论即可：

  • 由于计算的是仍在棋盘内的概率，因此对于 (nx,ny)(nx, ny)(nx,ny) 在棋盘外的情况，无须考虑；
  • 若下一步的落点 (nx,ny)(nx, ny)(nx,ny) 在棋盘内，其剩余可用步数为 p−1p - 1p−1，则最后仍在棋盘的概率为 f[nx][ny][p−1]f[nx][ny][p - 1]f[nx][ny][p−1]，则落点 (nx,ny)(nx, ny)(nx,ny) 对 f[i][j][p]f[i][j][p]f[i][j][p] 的贡献为 f[nx][ny][p−1]×18f[nx][ny][p - 1] \times \frac{1}{8}f[nx][ny][p−1]×81​，其中 18\frac{1}{8}81​ 为事件「从 (i,j)(i, j)(i,j) 走到 (nx,ny)(nx, ny)(nx,ny)」的概率（八连通移动等概率发生），该事件与「到达 (nx,ny)(nx, ny)(nx,ny) 后进行后续移动并留在棋盘」为相互独立事件。

最终的 f[i][j][p]f[i][j][p]f[i][j][p] 为「八连通」落点的概率之和，即有：

f[i][j][p]=∑f[nx][ny][p−1]×18f[i][j][p] = \sum {f[nx][ny][p - 1] \times \frac{1}{8}}f[i][j][p]=∑f[nx][ny][p−1]×81​

代码：

class Solution {
    int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
    public double knightProbability(int n, int k, int row, int column) {
        double[][][] f = new double[n][n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j][0] = 1;
            }
        }
        for (int p = 1; p <= k; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] d : dirs) {
                        int nx = i + d[0], ny = j + d[1];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                        f[i][j][p] += f[nx][ny][p - 1] / 8;
                    }
                }
            }
        }
        return f[row][column][k];
    }
}
  • 时间复杂度：令某个位置可联通的格子数量 C=8C = 8C=8，复杂度为 O(n2×k×C)O(n^2 \times k \times C)O(n2×k×C)
  • 空间复杂度：O(n2×k)O(n^2 \times k)O(n2×k)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.688 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

转载自:https://juejin.cn/post/7249320656576135223
评论
请登录