Q688-马在棋盘上的概率-中等-动态规划

688. “马”在棋盘上的概率

Question

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

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

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

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

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

Example 1:

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

Note:

N 的取值范围为 [1, 25]

K 的取值范围为 [0, 100]

开始时，“马” 总是位于棋盘上

Approach 1: 动态规划

令 f[r][c][steps] 代表马在位置 (r, c) 移动了 steps 次以后还留在棋盘上的概率，根据马的移动方式，我们有以下递归：

根据题目我们可以知道 (dr, dc) 的可能数据对是 (2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)。
我们将使用二维的 dp 和 dp2 来存储我们的数据，而不是使用三维数组 f。
- dp2 代表 f[][][steps]；
- dp 代表 f[][][steps-1]；

class Solution(object):
    def knightProbability(self, N, K, r, c):
        dp = [[0] * N for _ in range(N)]
        dp[r][c] = 1
        for _ in range(K): # 走k步还在棋盘内的概率
            dp2 = [[0] * N for _ in range(N)]
            for r, row in enumerate(dp):
                for c, val in enumerate(row):
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                   (1,2),(1,-2),(-1,2),(-1,-2)):
                        # 走了一步之后还在棋盘内
                        if 0 <= r + dr < N and 0 <= c + dc < N:
                            dp2[r+dr][c+dc] += val / 8.0
            dp = dp2
        # map()函数把sum依次作用在dp的每一项上，在map()外再使用sum()完成二维数组的求和
        return sum(map(sum, dp))


def main():
    N, K, r, c = 3, 2, 0, 0
    solution=Solution().solve(N, K, r, c)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：。其中 N, K 为题目中的定义。我们对元素的每一层 dp 进行 O(1) 工作，并且考虑了 K 层。
空间复杂度：，dp 和 dp2 的大小。

Approach 2: 矩阵求幂

方法 1 中表示的状态重复表达了过渡到其他的线性组合的状态。任何情况下，我们都可以将整个转换表示为这些线性组合的矩阵。然后，这个矩阵的第 n 次方代表了 n 移动的转换，因此我们可以将问题简化为矩阵求幂问题。

算法：

首先，我们可以利用棋盘上的对称性。马可能有 n^2 的状态（假设它在板上）。由于横轴、纵轴和对角线的对称性，我们可以假设骑士在棋盘的左上象限，并且列数等于或大于行数。对于任何一个位置，通过满足条件通过轴反射得到位置将是该位置的标准索引。
这将使状态数从减少到大约，这使得在这个矩阵上下求幂大约快倍。
现在，如果我们知道每一个状态在一次移动后都会变成某种状态的线性组合，那么让我们写一个过渡矩阵，其中的第 i 行代表了第 i 个状态的线性组合。然后，表示 n 次移动的转换，我们需要第 i 行的总和，其中 i 是起始位置的索引。

class Solution:
    def knightProbability2(self, N, K, sr, sc):
        def canonical(r, c):
            if 2 * r > N: r = N - 1 - r
            if 2 * c > N: c = N - 1 - c
            if r > c: r, c = c, r
            return r*N + c

        def matrix_mult(A, B):
            ZB = zip(*B)
            return [[sum(a * b for a, b in zip(row, col))
                    for col in ZB] for row in A]

        def matrix_expo(A, K):
            if K == 0:
                return [[+(i==j) for j in xrange(len(A))]
                        for i in xrange(len(A))]
            if K == 1:
                return A
            elif K % 2:
                return matrix_mult(matrix_expo(A, K-1), A)
            B = matrix_expo(A, K/2)
            return matrix_mult(B, B)

        index = [0] * (N*N)
        t = 0
        for r in xrange(N):
            for c in xrange(N):
                if r*N + c == canonical(r, c):
                    index[r*N + c] = t
                    t += 1
                else:
                    index[r*N + c] = index[canonical(r, c)]

        T = []
        for r in xrange(N):
            for c in xrange(N):
                if r*N + c == canonical(r, c):
                    row = [0] * t
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                    (1,2),(1,-2),(-1,2),(-1,-2)):
                        if 0 <= r+dr < N and 0 <= c+dc < N:
                            row[index[(r+dr)*N + c+dc]] += 0.125
                    T.append(row)

        Tk = matrix_expo(T, K)
        i = index[sr * N + sc]
        return sum(Tk[i])

复杂度分析

时间复杂度：。其中 N, K 为题目中的定义。大约有规范状态，这使得我们的矩阵乘法。为了找到这个矩阵的第 K 次幂，我们做了 matrix乘法。
空间复杂度：，矩阵有大约个元素。