Leetcode688: 骑士在棋盘上的概率(medium)
目录
1. 题目描述
在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。
行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
(注，类似于中国象棋中的‘马走日’，只不过中国象棋的棋子在格点上，国际象棋的棋子是在格子内)
每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
骑士继续移动，直到它走了 k 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
示例 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 <= 25
0 <= k <= 100
0 <= row, column <= n
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard
2. 解题分析
第一感是用动态规划方法来解决。
记当前cell为cur=(row,col)，记cur经过一步后可以到达的cells为next[k],k=0,...,7. 从cur经过n步后留在棋盘内的概率记为p(cur,n)，则可以得到如下递归关系式：
基线(baseline)条件:
（1）n=0
（2）cell坐标超出边界
从(row,col)出发可以到的8个位置坐标为：
- (row+1,col+2)
- (row+2,col+1)
- (row+2,col-1)
- (row+1,col-2)
- (row-1,col-2)
- (row-2,col-1)
- (row-2,col+1)
- (row-2,col+2)
这个可以预计算出，超出棋盘范围的坐标记为-1。
3. 代码实现：
from collections import defaultdict
import time
class Solution:
def knightProbability(self, n: int, k: int, row: int, col: int) -> float:
# Add memoization technique.
nextcell = defaultdict(list)
for r in range(n):
for c in range(n):
r_tmp,c_tmp = r+1,c+2
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r+2,c+1
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r+2,c-1
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r+1,c-2
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r-1,c-2
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r-2,c-1
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r-2,c+1
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
r_tmp,c_tmp = r-1,c+2
nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))
memo = dict()
def dp(row,col,k):
if (row,col,k) in memo:
return memo[(row,col,k)]
if k == 0:
return 1 if row >= 0 and row < n and col >= 0 and col < n else 0
if row < 0 or col < 0 or row >= n or col >= n:
return 0
nxt = nextcell[(row,col)]
p = 0
# print(nxt)
for m in range(8):
# print(m)
if m >= len(nxt):
print(row,col,k,m,nxt)
cellnext = nxt[m]
p = p + dp(cellnext[0],cellnext[1],k-1)/8
# print('dp({0},{1},{2} = {3})'.format(row,col,k,p))
memo[(row,col,k)] = p
return p
return dp(row,col,k)if __name__ == '__main__':
sln = Solution()
n,k,row,col = 3, 2, 0, 0
print(sln.knightProbability(n, k, row, col))
n,k,row,col = 1, 0, 0, 0
print(sln.knightProbability(n, k, row, col))
# n,k,row,col = 8, 30, 6, 4
n,k,row,col = 10, 13, 5, 3
tStart = time.time()
p = sln.knightProbability(n, k, row, col)
tCost = time.time() - tStart
print('knightProbability({0},{1},{2},{3}) = {4}, tCost = {5}(sec)'.format(n,k,row,col,p,tCost))运行结果：
动态规划方法通常都要求采用memoization技巧，否则的话，运行时间将会难以接受。本题第一次提交没有采用memoization技巧，提交后被超时判负。
将以上代码中memo相关行注释掉，对比一下就可以看到memoization技巧的效果。不过，不能用太大的参数（n,k），否则你在运行no-memoization版本很可能不得不强制退出^-^.
本题的另一种解法（基于概率转移矩阵的幂运算） 参见：Leetcode688: 基于概率转移矩阵的解法
https://chenxiaoyuan.blog.csdn.net/article/details/123000362