题目描述
这是 LeetCode 上的 913. 猫和老鼠 ，难度为 困难。
Tag : 「动态规划」、「记忆化搜索」
两位玩家分别扮演猫和老鼠，在一张无向图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。
例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。 如果老鼠到达洞中，老鼠获胜。 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。 给你一张图 graph，并假设两位玩家都都以最佳状态参与游戏：
- 如果老鼠获胜，则返回
1； - 如果猫获胜，则返回
2； - 如果平局，则返回
0。
示例 1：
输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] 输出：0 复制代码
示例 2：
输入：graph = [[1,3],[0],[3],[0,2]] 输出：1 复制代码
提示：
- 3 <= graph.length <= 50
- 1 <= graph[i].length < graph.length
- 0 <= graph[i][j] < graph.length
- graph[i][j] != i
- graph[i] 互不相同
- 猫和老鼠在游戏中总是移动
动态规划
数据范围只有 5050，使得本题的难度大大降低。
定义 f[k][i][j]f[k][i][j] 为当前进行了 kk 步，老鼠所在位置为 ii，猫所在的位置为 jj 时，最终的获胜情况（00 为平局，11 和 22 分别代表老鼠和猫获胜），起始我们让所有的 f[i][j][k] = -1f[i][j][k]=−1（为无效值），最终答案为 f[0][1][2]f[0][1][2]。
不失一般性的考虑 f[i][j][k]f[i][j][k] 该如何转移，根据题意，将当前所在位置 ii 和 jj 结合「游戏结束，判定游戏」的规则来分情况讨论：
- 若 i = 0i=0，说明老鼠位于洞中，老鼠获胜，此时有 f[k][i][j] = 1f[k][i][j]=1；
- 若 i = ji=j，说明两者为与同一位置，猫获胜，此时有 f[k][i][j] = 2f[k][i][j]=2；
- 考虑如何定义平局，即 f[k][i][j] = 0f[k][i][j]=0 的情况？
我们最多有 nn 个位置，因此 (i, j)(i,j) 位置对组合数最多为 n^2n2 种，然后 kk 其实代表的是老鼠先手还是猫先手，共有 22 种可能，因此状态数量数据有明确上界为 2 * n^22∗n2。
所以我们可以设定 kk 的上界为 2 * n^22∗n2（抽屉原理，走超过 2 * n^22∗n2 步，必然会有相同的局面出现过至少两次），但是这样的计算量为 2 * 50^2 * 50 * 50 = 1.25 * 10^72∗502∗50∗50=1.25∗107，有 TLE 风险，转移过程增加剪枝，可以过。
而更小的 kk 值需要证明：在最优策略中，相同局面（状态）成环的最大长度的最小值为 kk。
题目规定轮流移动，且只能按照 graphgraph 中存在的边进行移动。
- 如果当前 kk 为偶数（该回合老鼠移动），此时所能转移所有点为 f[k + 1][ne][j]f[k+1][ne][j]，其中 nene 为 ii 所能到达的点。由于采用的是最优移动策略，因此 f[k][i][j]f[k][i][j] 会优先往 f[k + 1][ne][j] = 1f[k+1][ne][j]=1 的点移动（自身获胜），否则往 f[k + 1][ne][j] = 0f[k+1][ne][j]=0 的点移动（平局），再否则才是往 f[k + 1][ne][j] = 2f[k+1][ne][j]=2 的点移动（对方获胜）；
- 同理，如果当前 kk 为奇数（该回合猫移动），此时所能转移所有点为 f[k + 1][i][ne]f[k+1][i][ne]，其中 nene 为 jj 所能到达的点。由于采用的是最优移动策略，因此 f[k][i][j]f[k][i][j] 会优先往 f[k + 1][i][ne] = 2f[k+1][i][ne]=2 的点移动（自身获胜），否则往 f[k + 1][i][ne] = 0f[k+1][i][ne]=0 的点移动（平局），再否则才是往 f[k + 1][i][ne] = 1f[k+1][i][ne]=1 的点移动（对方获胜）。
使用该转移优先级进行递推即可，为了方便我们使用「记忆化搜索」的方式来实现动态规划。
注意，该优先级转移其实存在「贪心」决策，但证明这样的决策会使得「最坏情况最好」是相对容易的，而证明存在更小的 kk 值才是本题难点。
一些细节：由于本身就要对动规数组进行无效值的初始化，为避免每个样例都
new大数组，我们使用static来修饰大数组，可以有效减少一点时间（不使用static的话，N只能取到 5151）。
代码：
class Solution { static int N = 55; static int[][][] f = new int[2 * N * N][N][N]; int[][] g; int n; public int catMouseGame(int[][] graph) { g = graph; n = g.length; for (int k = 0; k < 2 * n * n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { f[k][i][j] = -1; } } } return dfs(0, 1, 2); } // 0:draw / 1:mouse / 2:cat int dfs(int k, int a, int b) { int ans = f[k][a][b]; if (a == 0) ans = 1; else if (a == b) ans = 2; else if (k >= 2 * n * n) ans = 0; else if (ans == -1) { if (k % 2 == 0) { // mouse boolean win = false, draw = false; for (int ne : g[a]) { int t = dfs(k + 1, ne, b); if (t == 1) win = true; else if (t == 0) draw = true; if (win) break; } if (win) ans = 1; else if (draw) ans = 0; else ans = 2; } else { // cat boolean win = false, draw = false; for (int ne : g[b]) { if (ne == 0) continue; int t = dfs(k + 1, a, ne); if (t == 2) win = true; else if (t == 0) draw = true; if (win) break; } if (win) ans = 2; else if (draw) ans = 0; else ans = 1; } } f[k][a][b] = ans; return ans; } } 复制代码
- 时间复杂度：状态的数量级为 n^4n4，可以确保每个状态只会被计算一次。复杂度为 O(n^4)O(n4)
- 空间复杂度：O(n^4)O(n4)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.913 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
