大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

有个N * N的棋盘，上面有个马，马走日字象走田嘛，找出这个马走了K步之后依然在这个棋盘上的概率。

解题方法

动态规划

第一感觉是 dfs，但是 n 和 k 都太大，如果 dfs 的话一定会超时的，所以还是得用 dp 来解。

定义的 **dp[i][j]** 数组代表到了某一轮，马能到 **[i, j]** 这个位置所有可能的次数。

计算思路是：马每次有 8 个移动方向，我们计算这 8 次中里面有多少种可能会落在棋盘上。

dp 更新的策略是，我们遍历棋盘的每个位置，当前的数值是能走到这个位置的在上一轮 dp 的数值 + 1。

循环 K 次以后，把马仍在棋盘上的次数相加（表示马留在棋盘上的所有可能次数之和），除以 $8^K$（马每次有 8 种移动方向）， 表示马仍在棋盘上的概率。
image.png

注意，python2里面的/默认的是地板除，需要用float再除得到概率。
点击查看【bilibili】

Python 代码如下：

  1. class Solution(object):
  2.     def knightProbability(self, N, K, r, c):
  3.         """
  4.         :type N: int
  5.         :type K: int
  6.         :type r: int
  7.         :type c: int
  8.         :rtype: float
  9.         """
  10.         dp = [[0 for i in range(N)] for j in range(N)]
  11.         dp[r][c] = 1
  12.         directions = [(1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
  13.         for k in range(K):
  14.             new_dp = [[0 for i in range(N)] for j in range(N)]
  15.             for i in range(N):
  16.                 for j in range(N):
  17.                     for d in directions:
  18.                         x, y = i + d[0], j + d[1]
  19.                         if x < 0 or x >= N or y < 0 or y >= N:
  20.                             continue
  21.                         new_dp[i][j] += dp[x][y]
  22.             dp = new_dp
  23.         return sum(map(sum, dp)) / float(8 ** K)

参考资料：

https://www.youtube.com/watch?v=MyJvMydR2G4

  • 时间复杂度：$O(K * N ^ 2)$
  • 空间复杂度：$O(N ^ 2)$

总结

  1. 这个题想清楚动态规划的转移方程之后，不难。
  2. 只用考虑马有多少中可能留在棋盘上就可以。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。