2029首先是寻找必败态最直接的就是只剩一个石子然后已取任意价值的石子两个状态剩余石子的数量以及已取石子的价值由最基础的必败态向上延申只剩一个石子是必败态剩两个石子且剩下的两个石子加上后都是3的倍数时也为必败态其余均为必胜如何描述状态转移这个状态性必须要知道已经取了那些石头那些还没取DFS先是DFS吧维护已取数组每层传入的信息是这次取的石头已积累的价值以及剩余石头的数量或许取的石头价值可以不用传递那么每层就是DFS循环遍历还没被取的尝试加到积累价值如果是3的倍数就continue否则就标记数组然后dfs回溯flagtrue检测flag如果为false说明这个状态为必败返回false否则true然后可以加上记忆化不过还有一个问题这个是忽略掉了双方的轮次是只看当前状态能否获胜的这个能否获胜是要看下个轮次能否使对手导向必败态所以dfs返回的应该是能否将对手导向必败态而不是自己这轮能否存活而当前这个flag就只是反映自己能否存货如果当前的dfs是必败态那么上一层的dfs也就是对手的应该就是必胜态所以该取反此外规则1的优先级大于规则2所以该先结算规则1但是规则一和二都指定了赢家但DFS当中并没有包含这个信息即不知道当前到底是A该取还是B该取所以底层结算时难以说明true or false但总数一定可以靠奇偶性来确定最后到底谁在取如果是奇数最后是A在取那么A只可能输而不可能赢所以该返回false如果是偶数那就是B在取,那么A必赢所以A会赢该返回true不是当到最后一个取了只能是B获胜A无法赢A唯一赢的方式就是B最后取而且最后是3的倍数即总数为偶数且为3的倍数如果这样的话应该以奇偶性来隐形地描述当前dfs到底是谁在执行了那么DFS含义就不是当前这层的人能否获胜而是当前这层的人执行完后A能否有必胜态class Solution { public: bool stoneGameIX(vectorint stones) { vectorboolvis(stones.size(),false); int sum0; for(int num:stones){ sumnum; } bool res((sum%3)0);//true的话说明最后一个人要输 functionbool(int,int)dfs[](int acc,int num)-bool{ if(numstones.size()-1){return (stones.size()%20);} bool flagfalse; for(int i0;istones.size();i){ if(!vis[i]((accstones[i])%3!0)){ //flagtrue; vis[i]true; flag|(!dfs(accstones[i],num1)); vis[i]false; } } return flag; }; return dfs(0,0); } };class Solution { public: bool stoneGameIX(vectorint stones) { vectorboolvis(stones.size(),false); int sum0; for(int num:stones){ sumnum; } //bool res((sum%3)0);//true的话说明最后一个人要输 functionbool(int,int)dfs-bool{ if(numstones.size()-1){ //couttouchendl; if((stones.size()%20)(sum%30)){ return true; } //return (stones.size()%20); else{ return false; } } bool flagfalse; for(int i0;istones.size();i){ if(!vis[i]((accstones[i])%3!0)){ //flagtrue; vis[i]true; //flag|(!dfs(accstones[i],num1)); flag|dfs(accstones[i],num1); vis[i]false; } } return flag; }; return dfs(0,0); } };那在之前的基础上能否继续解决B的次序对于A的归并即只有B接下来的所有选择都会使A获胜才返回true那貌似DFS里就必须显示地引入当前次序了对于A就是只要有就可以但对于B就是下个DFS全为true才可以否则会false那规定true时为A的回合false时为B的回合class Solution { public: bool stoneGameIX(vectorint stones) { vectorboolvis(stones.size(),false); int sum0; for(int num:stones){ sumnum; } functionbool(int,int,bool)dfs[](int acc,int num,bool cur)-bool{ if(numstones.size()-1){ if(cur){return false;} else{return (sum%30);} } bool flagfalse; for(int i0;istones.size();i){ if(!vis[i]((accstones[i])%3!0)){ vis[i]true; bool resdfs(accstones[i],num1,!cur); vis[i]false; if(cur){ flag|res; }else{ flagres; } } } return flag; }; return dfs(0,0,true); } };class Solution { public: bool stoneGameIX(vectorint stones) { vectorboolvis(stones.size(),false); int sum0; for(int num:stones){ sumnum; } functionbool(int,int,bool)dfs[](int acc,int num,bool cur)-bool{ if(numstones.size()-1){ if(cur){return false;} else{return (sum%30);} } bool flagcur?false:true; for(int i0;istones.size();i){ if(!vis[i]((accstones[i])%3!0)){ //vtrue; vis[i]true; bool resdfs(accstones[i],num1,!cur); vis[i]false; if(cur){ flag|res; }else{ flagres; } } }//如果都不可选都不合法的话那么当前人该输如果是A的回合就输否则A赢 return flag; }; return dfs(0,0,true); } };这样才是正确的即flag也要因当前轮次的人而变化对于A如果不可取那就会输所以起始就是false然后在可取当中寻求胜态对于B不可取则A会赢然后DFS返回的是A的状态所以起始为true一点问题都没有然后不断地去做与操作只要有一种方式让A输那就会false记忆化与DFS的优化DFS写出来后一般都可以记忆化搜索但这个的空间很大三个状态acc,num和Bool对于acc可以达到10e9然后Num是10e5bool再有个2空间上完全无法接受这里可以提前判断flag来提前结束位运算操作