LeetCode 464. 我能赢吗 (状压DP)

tech2024-12-18  5

我能赢吗 因为要记录每个数字的使用情况,所以将数字的使用情况压缩成一个二进制数,对应的为0表示没有使用过,1表示已经用过了。

状态: d p [ S ] dp[S] dp[S]表示在状态为S的情况下当前先手的玩家的胜负情况。 注意不需要使用第二维去记录累积和,否则或爆内存。DP方程: d p [ S ]    ∣ =    ! d p [ S ∨ x ] ( x ∉ S ) dp[S] \ \ |= \ \ !dp[S\vee x ](x\notin S) dp[S]  =  !dp[Sx](x/S)注意搜索的顺序,以及及时剪枝。 class Solution { public: vector<int> dp; int m, t; bool canIWin(int M, int T){ m = M, t = T; if(t>(m+1)*m/2) return 0; dp.resize(1<<(m+1),-1); return dfs(0); } bool dfs(int s){ if(dp[s]!=-1) return dp[s]; int &res = dp[s]; res = 0; for(int i=m;i>=1;i--){ if((s>>i&1)==0){ if(get(s|(1<<i))>=t || !dfs(s|(1<<i))){ res = 1; break; } } } return res; } int get(int s){ int sum = 0; for(int i=1;i<=21;i++){ if(s>>i&1) sum += i; } return sum; } };
最新回复(0)