leetcode 913. 猫和老鼠

博弈论dp，记忆化搜索，从最开始的状态去搜；

dp[mouse][cat][turn]表示当前mouse ,cat,turn三种状态下先手能获得的最优解，其中优先级赢>和>输；

 1 class Solution {
 2 public:
 3     
 4     int catMouseGame(vectorint>>& graph) {
 5         int n=graph.size();
 6         int dp[n][n][n*n];
 7         memset(dp,-1,sizeof(dp));
 8         function<int(int,int,int)>dfs=[&](int mouse,int cat, int turn)
 9         {
10             if(turn>=n*n)return 0;
11             else if(mouse==cat)return 2;
12             else if(mouse==0)return 1;
13             if(~dp[mouse][cat][turn])return dp[mouse][cat][turn];
14             if(turn&1)
15             {
16                 bool ok=false;
17                 for(auto &v:graph[cat])
18                 {
19                     if(v)
20                     {
21                         int res=dfs(mouse,v,turn+1);
22                         if(res==2)return dp[mouse][cat][turn]=2;
23                         else if(res==0)ok=true;
24                     }
25                 }
26                 if(ok)return dp[mouse][cat][turn]=0;
27                 else return dp[mouse][cat][turn]=1;
28             }
29            else
30            {
31                 bool ok=false;
32                 for(auto &v:graph[mouse])
33                 {
34                     int res=dfs(v,cat,turn+1);
35                     if(res==1)return dp[mouse][cat][turn]=1;
36                     else if(res==0)ok=true;
37                 }
38                 if(ok)return dp[mouse][cat][turn]=0;
39                 else return dp[mouse][cat][turn]=2;
40            }
41         };
42         return dfs(1,2,0);
43     }
44 };