题目链接：688. 骑士在棋盘上的概率
动态规划的偷懒做法，使用一个缓存记录已经计算出来的结果，下一次如果缓存中有结果，那就不用再算了。
class Solution:
MOVES = [
(2, 1), (-2, 1), (2, -1), (-2, -1),
(1, 2), (-1, 2), (1, -2), (-1, -2),
]
def __init__(self):
self.cache = dict()
def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
if (n, k, row, column) in self.cache:
return self.cache.get((n, k, row, column))
if not (0 <= row < n and 0 <= column < n):
res = 0
elif k == 0:
res = 1
else:
res = sum(self.knightProbability(n, k - 1, row + dx, column + dy) for dx, dy in self.MOVES) / 8
self.cache[(n, k, row, column)] = res
return res