记忆化搜索已改为拓扑排序的动态规划。因为记忆化搜索不能使用 $2n$，只能用 $2n^2$ 来判断平局，会 TLE

我觉得超过 2n time 就表明 draw 了可以这么证明：老鼠至多 n - 1 步就可以到达 0，我们记从 1 到 0 的这条路径为 path. 如果第 n 步老鼠没有到达 0 的话，就说明在某个时刻，老鼠偏离了原本的路径 path, 为什么会偏移呢？说明在前面的某一点 p，猫在旁边候着。猫到点 p 的距离小于等于老鼠到点 p 的距离。（注意可以有多个这样的点 p, 无论老鼠选取那条通往 0 的路径，路上都有一个这样的点，老鼠会在这个点被猫逮到）。而老鼠不经过 p 的话又不可能到达 0。

这可不叫证明

这题f[t][x][y]可不可用滚动数组对t模2？试了一下个别test case不过。请问什么地方需要注意？

滚动数组一般不能用到记忆化搜索的DP中，因为每一层的状态都需要记录，和循环实现的DP有一些区别。

是的。这个题每次递归只从t到t+1，我就试了一下。极个别情况会fail。

首先
if (t == graph.size() + 1)
这一句应该是
if (t == graph.size() * 2)
因为老鼠走n步，猫也走n步，加起来是2n步，对于你现在的程序，反例特别简单，
3-2-0-4-5-6-7-8-9-1
按照这个图，猫只能来回走，老鼠7步可以走到0，总计13步后老鼠获胜
第二，你所说的老鼠或者猫如果回到之前走过的位置就一定是平局，这个结论明显是错的，上面本身就是一个反例，而且构造一个猫和老鼠所在位置连通的反例也很容易，但奇妙的是，我构造出的所有反例，都能在2n步以内得到结果，极限步数趋向于2n，所以我现在倾向于认为这个游戏只要超过2n步就可以判定为平局，但是我证明不了。
最后@2018coder，这个问题如果用传统的dfs，存在一个结果正确的做法，但是结果正确的做法为了遍历所有的可能，在大数据里一定会栈溢出。

我感觉里面dfs的过程中循环了，本身没有其他办法退出循环，
我的例子里面就是在这个状态里面不停的循环， 把状态的第一个节点改成level了以后只是遇到level超出了以后才退出循环， 即使是2n, 我认为也是不改变逻辑，只是循环的次数变多了而已

0--(mouse, 1, 2)
1--(cat,4,2)
2--(mouse,4,9)
3--(cat,1,9)

我提出的是两个完全不同的方案。
1. 证明如果不是平局，一定能在2n步之内获得一个解，是不是循环跟我们就没有任何关系了，唯一的问题是证明比较困难。
2. 传统的dfs不停的循环并非没有解决方案，你只要对于每个状态加标记，记录以前走过的路，之后再也不走就可以了，唯一的问题是这是无向图，在n比较大的时候我们遍历所有的状态会导致栈溢出。

如果答案不是draw，dfs在n^2步内一定能找到解，因为dfs会在n^2步内枚举到所有可能的位置。
既然 n 步已经被否决了，那可以试着找下 2n 的反例。

我貌似忽略了这点，应该是2n。我先暂时把upper_bound改到2n吧，n^2会导致MLE。

你好，能不能请教一下为什么需要每个level存一个状态？ 虽然我想每个level存一个状态的好处是在一条递归路径上后面的结果不会被前面的影响， 也就是遇到重复节点的时候可以避免这个节点的结果还没有算出来就直接因为重复就判draw了，
但是我理解是
1. [turn, mousepos, catpos]就决定了这个状态节点的值，和他在哪个level没有关系，
2. 对于每个节点，只要我们遍历了所有的邻居节点以后再最后决定他的值，应该就可以得出正确的结果
但是我用下面的代码就会出错，
能指点一下嘛？
谢谢

class Solution {
   private static int DRAW = 1, MOUSE_WIN = 2, CAT_WIN = 3;
    public int catMouseGame(int[][] graph) {
        return dfs(new int[2][graph.length][graph.length], 0, graph, 1, 2)-1;
    }

    public int dfs(int[][][] alltable, int level, int[][] graph, int mousepos, int catpos) {
        if(level == graph.length + 1) {
            return DRAW;
        }

        int[][] table = alltable[level%2];

        if(table[mousepos][catpos] != 0) return table[mousepos][catpos];
        if(catpos == mousepos) {
            table[mousepos][catpos] = CAT_WIN;
            return CAT_WIN;
        }
        if(mousepos == 0) {
            table[mousepos][catpos] = MOUSE_WIN;
            return MOUSE_WIN;
        }
        if(level%2 == 0) {
            boolean hasdraw = false;
            for(int next: graph[mousepos]) {
                int oneret = dfs(alltable, level+1, graph, next, catpos);
                if(oneret == MOUSE_WIN) {
                    table[mousepos][catpos] = MOUSE_WIN;
                    return MOUSE_WIN;
                }
                else if(oneret == DRAW) {
                    hasdraw = true;
                }
            }
            int ret = hasdraw ? DRAW : CAT_WIN;
            table[mousepos][catpos] = ret;
            return ret;
        }
        else {
            boolean hasdraw = false;
            for(int next: graph[catpos]) {
                if(next == 0) continue;
                int oneret = dfs(alltable, level+1, graph, mousepos, next);
                if(oneret == CAT_WIN) {
                    table[mousepos][catpos] = CAT_WIN;
                    return CAT_WIN;
                }
                else if(oneret == DRAW) {
                    hasdraw = true;
                }
            }
            int ret = hasdraw ? DRAW: MOUSE_WIN;
            table[mousepos][catpos] = ret;
            return ret;

        }
    }
}

我尝试了只用这样的状态，会出错。我感觉原因在于这样的状态表示，DP会出现环；但这里出现环并不一定就是draw，可能环里有其他的出口能到达一个确定的状态。

谢谢， 对，dp出现环确实是不同的地方，但是困惑的是感觉下面这两步逻辑并没有问题
1. [turn, mousepos, catpos]就决定了这个状态节点的值，和他在哪个level没有关系，
2. 对于每个节点，只要我们遍历了所有的邻居节点以后再最后决定他的值，应该就可以得出正确的结果。 这里就算出现了环（访问到dfs前面已经访问的结果，但是这部分子树还没有搜索完）， 但是对于任何一个节点，仍然只会在所有邻居节点全部都尝试了以后才会设置值，不知道那里错了。。。

Check this case:
[[6],[4],[9],[5],[1,5],[3,4,6],[0,5,10],[8,9,10],[7],[2,7],[6,7]]

用自底向上从两个出口往回递推应该是没有问题的，但用记忆化搜索就会出问题，因为记忆化搜索遇到环且不规定环的出口会死循环，但递推总会从出口往回找，遇到环可以直接宣布平局。

谢谢！

我又debug了一下这组数据， 大概明白了为什么我改的代码是错的，原因是部分递归过程， dp表格出现了环， 不停的在环里面循环， 直到深度超出了，然后判和退出。 递归过程如下， 这里level=12的两个步骤，都是因为深度超出了，才导致判和。虽然在这个过程中，对于level在11遇到的(cat,1,9)这个状态节点，所有子节点都尝试了，但是因为尝试的过程受到前面在环里面不停循环的影响，导致深度超过了， 所以每个节点的判断都是不准确的，因为对于一个环上的节点，由于循环的存在，[turn,mousepos,catpos]本身的值已经不再能通过深度超出来判和了，相当于前面的循环导致后续判断其他节点的值不准确了。

我有一个问题，感觉你的代码用[level,mousepos,catpos]做状态似乎也没有解决环的问题，只是减少了错误的可能性，因为[level,mousepos,catpos]被错误利用的可能性大大减小了，至少在一次递归的过程中是不会被错误利用的，而在其他情况下正好遇上那个错误的[level,mousepos,catpos]的可能性小了很多，但是还是有可能会存在同样的错误值。
虽然我构造不出来一组数据可以验证这个，你决定这个猜想成立嘛？ 是不是这个问题其实dfs无法解决重复环的问题？

0--(mouse, 1, 2)
1--(cat,4,2)
2--(mouse,4,9)
3--(cat,1,9)
4--(mouse,1,2)
5--(cat,4,2)
6--(mouse,4,9)
7--(cat,1,9)
8--(mouse,1,2)
9--(cat,4,2)
10--(mouse,4,9)
11--(cat,1,9) -->DRAW
   12--(mouse,1,2)--> DRAW
   12--(mouse,1,7)--> DRAW 

最保守的 level 是取 $n^2$，因为最多只有 $n^2$ 的状态可以到达，如果都尝试了就只能平局。但这里我取的 $n$ 实际上是基于一个贪心，如果老鼠或者猫走的路径出现的重复结点，说明已经在向对方妥协了。

其实我的问题倒不是level高度不够，而是[level,mousepos,catpos]在递归过程中也会得到错误的值，并且可能被错误利用？ 只是这个被错误利用的概率比[turn,mousepos,catpos]的概率小很多很多。
本质上在同样的dfs代码下，[level,mousepos,catpos]和[turn,mousepos,catpos]导致错误的原因是一样的，都是因为环导致错误的状态被存在这个表里面，只是[level,mousepos,catpos]被撞上的概率很小

[level,mousepos,catpos]在递归过程中应该不会得到错误的值，层数够深有环就是draw了

{{6},{4},{9},{5},{1,5},{3,4,6},{0,5,10},{8,9,10},{7},{2,7},{6,7}}

比如针对上面的case， 下面是我debug的递归过程，最后那几行看到的状态都是不对的

0--(mouse, 1, 2)
1--(cat,4,2)
2--(mouse,4,9)
3--(cat,1,9)
4--(mouse,1,2)
5--(cat,4,2)
6--(mouse,4,9)
7--(cat,1,9)
8--(mouse,1,2)
9--(cat,4,2)
10--(mouse,4,9)
11--(cat,1,9)  --> DRAW
   12--(mouse,1,2)--> DRAW
   12--(mouse,1,7)--> DRAW 

这只是递归的一条分支，但老鼠在某一层有其他的走法，这样能到达终点，所以就能正确更新

主要的问题在于， 其他走法被level超出影响了， 然后直接判draw了， 没有继续往后面走

我感觉，f 的初始化长度可以是n，不用n+1。if (t == graph.size() + 1)return 0;这里不用加1

是的