688. 马在棋盘上的概率（Python）

题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

示例：

输入: 3, 2, 0, 0
输出: 0.0625
解释:
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。

注意：

N 的取值范围为 [1, 25]
K 的取值范围为 [0, 100]
开始时，“马” 总是位于棋盘上

解答

方法1：动态规划

【矩阵定义】：定义一个K+1xNxN维度的三维矩阵dp，其中任意一点(k_, r_, c_)表示马走k_步后落在点(r_, c_)处的概率。这里在K维度上增加一维用来表示初始状态也就是马走零步的状态。

【初始状态】
由于马的最初位置是(r,c)，因此马走零步落在点(r,c)的概率为1，因此填充dp[0][r][c] = 1，其他位置填充零。

【递推公式】
对于当前位置(r_, c_)，马可以由八个方向跳过来：directions= [(2, 1), (2, -1), (1, 2), (1, -2), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]，对于每一个位置，马也可以等概率的跳到以上八个方向中任意一个。每一步的概率取决于上一步，每一个点的概率取决于八个特定方向临近点，因此，递推公式为：

dp[k_][r_][c_] = sum([dp[k_-1][r_+dr][c_+dc]/8 for dr, dc in directions])

这里需要注意判断求解概率的点不要越过棋盘边界。

【最终结果】

最后，我们选择最后一步的概率网格，求取网格所有点的和，即为K步后马还在棋盘中的概率。

class Solution:
    def knightProbability(self, N, K, r, c):
        dp = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(K+1)]
        dp[0][r][c] = 1
        directions = [(2, 1), (2, -1), (1, 2), (1, -2),
                      (-2, 1), (-2, -1), (-1, 2), (-1, -2)
                      ]

        for k_ in range(1, K+1):
            print(dp[k_])
            for r_ in range(N):
                for c_ in range(N):
                    for dr, dc in directions:
                        if 0 <= r_+dr < N and 0 <= c_+dc < N:
                            dp[k_][r_][c_] += dp[k_-1][r_+dr][c_+dc] / 8
        return sum([prob for row in dp[-1] for prob in row])

方法2：记忆化深度优先搜索

为了简化计算，我们使用字典记录已经出现过的概率值，即将上述的三维网格按照位置-概率进行对应，通过及时的查找避免重复的计算。

这里用深度优先搜索方式代替动态规划，其一般规则是：首先判断特殊情况，例如越界或记录已经存在于字典中。注意这里dfs函数的返回值代表的是以从点(r,c)出发，K步后马还在棋盘上的概率，而非落在(r,c)点的概率。

class Solution:
    def knightProbability(self, N, K, r, c):

        memory = dict()
        directions = ((-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (2, 1), (1, 2))

        def dfs(K, r, c):
            if not (0 <= r < N and 0 <= c < N):
                return 0
            if K == 0:
                return 1
            if (K, r, c) in memory:
                return memory[(K, r, c)]
            p = sum([dfs(K - 1, r + dr, c + dc) / 8.0 for dr, dc in directions])
            memory.update({(K, r, c): p})
            return p
        return dfs(K, r, c)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析