leetcode: cat and mouse

狀態表示

考慮狀態state[step][mouse][cat]={0, 1, 2}，表示第step步后，老鼠在mouse位置，貓在cat位置，此時貓和老鼠在最佳狀態下的游戲結局。

初始化

根據游戲規則，我們可以直接推理出

老鼠必勝： state[step][0][cat] = 1

貓必勝：state[step][i][i] = 2

根據抽屜原理，當只能走t個點時，第t+1步必然與前面的某一步重復，根據題意貓只能走n-1個點，老鼠可以走n個點，那么當貓走了n-1步，老鼠走了n步后，貓的下一步必然會落在貓之前走過的點上，可以得到state[2*n][i][j] = 0

狀態轉移

輪到老鼠走時，target表示老鼠可以走到的下個節點

當存在state[step+1][target][cat]=1時，當前狀態下老鼠必勝

否則，當存在state[step+1][target][cat]=0時，老鼠必然選擇和棋策略

否則，老鼠必輸

輪到貓走時，和老鼠的狀態是一樣的，但需要注意對于貓target!=0

時間復雜度計算

step, mouse, cat取值都是O(n)，在記憶化搜索的情況下，總體搜索的復雜度為O(n^3)

總結

以上是生活随笔為你收集整理的猫和老鼠：博弈论——记忆化搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。