【leetcode】2022.1.4猫和老鼠

BJFU_vth 2022-01-08 05:34:19 阅读数:144

leetcode 2022.1.4 猫和老鼠 老鼠

913. 猫和老鼠

分析

hard題,而且是個三維dp題。
所以還是看官方題解吧,我講的肯定沒有官方題解好理解。
官方題解長這樣:
在這裏插入圖片描述
在這裏插入圖片描述
在這裏插入圖片描述
在這裏插入圖片描述

動態規劃法

DRAW = 0
MOUSE_WIN = 1
CAT_WIN = 2
class Solution:
def catMouseGame(self, graph) -> int:
n = len(graph)
dp = [[[-1] * (n * 2) for _ in range(n)] for _ in range(n)]
def getResult(mouse: int, cat: int, turns: int) -> int:
# 已經跑了2輪了, 證明至少存在一個節點猫走過2次, 老鼠也走過2次
if turns == n * 2:
return DRAW
res = dp[mouse][cat][turns]
# 如果該輪次已經更新過狀態了
if res != -1:
return res
# 如果老鼠進洞了, 那老鼠贏了
if mouse == 0:
res = MOUSE_WIN
# 如果猫鼠相遇了, 那猫贏了
elif cat == mouse:
res = CAT_WIN
# 如果又沒有相遇,老鼠也沒進洞, 那就得接著跑
else:
res = getNextResult(mouse, cat, turns)
# 根據下一輪次的結果來更新本輪次的狀態, 即下一輪如果猫必勝, 那這一輪次就有猫必勝狀態, 因為是最優策略
dp[mouse][cat][turns] = res
return res
def getNextResult(mouse: int, cat: int, turns: int) -> int:
curMove = mouse if turns % 2 == 0 else cat
# 設置默認狀態, 認為自己必輸無疑
defaultRes = MOUSE_WIN if curMove != mouse else CAT_WIN
res = defaultRes
for next in graph[curMove]:
# 猫不能進老鼠洞
if curMove == cat and next == 0:
continue
# 下一步老鼠的可能值
nextMouse = next if curMove == mouse else mouse
# 下一步猫的可能值
nextCat = next if curMove == cat else cat
# 下一步可能的狀態
nextRes = getResult(nextMouse, nextCat, turns + 1)
# 如果該輪次輸不了
if nextRes != defaultRes:
res = nextRes
# 如果不是平局(即獲勝了,那麼可以return了,因為存在一個節點讓自己必勝,按照最優策略就走它)
if res != DRAW:
break
return res
return getResult(1, 2, 0)
版权声明:本文为[BJFU_vth]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080534186915.html