leetcode

commit b2d95baa8a3c6d52088ff8c0c2ed810f051d01e6
parent aad28e15e172b1eb113ca671ce42a081e81ae738
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 30 Oct 2025 09:05:55 -0600

464. can i win

Diffstat:
M
can_i_win.c
 | 
42
++++++++++++++++++++++++------------------
M
can_i_win.py
 | 
35
++++++++++++++++++-----------------

2 files changed, 42 insertions(+), 35 deletions(-)
diff --git a/can_i_win.c b/can_i_win.c
@@ -12,33 +12,39 @@
  * both players play optimally.
  */
 
-static int mem[1 << 20] = {};
-
-bool dfs(int maxChoosableInteger, int desiredTotal, int k) {
-  if (mem[k])
-    return mem[k] > 0;
-  if (desiredTotal <= 0)
+bool dfs(int *vis, int state, long long sum, int maxChoosableInteger,
+         int desiredTotal) {
+  if (vis[state] == 2)
+    return true;
+  if (vis[state] == 1)
     return false;
-  for (int i = 0; i < maxChoosableInteger; ++i)
-    if (!(k & (1 << i)) &
-        !dfs(maxChoosableInteger, desiredTotal - i - 1, k | (1 << i))) {
-      mem[k] = 1;
+  for (int i = 1; i <= maxChoosableInteger; i++) {
+    if ((state >> i) & 1)
+      continue;
+    if ((sum + 1) >= desiredTotal) {
+      vis[state] = 2;
+      return true;
+    }
+    if (!dfs(vis, state + (1 << i), sum + i, maxChoosableInteger,
+             desiredTotal)) {
+      vis[state] = 2;
       return true;
     }
-  mem[k] = -1;
+  }
+  vis[state] = 1;
   return false;
 }
 
 bool canIWin(int maxChoosableInteger, int desiredTotal) {
-  int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
-  if (desiredTotal < 2)
+  if (maxChoosableInteger >= desiredTotal)
     return true;
-  else if (sum < desiredTotal)
+  if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal)
     return false;
-  else if (sum == desiredTotal)
-    return maxChoosableInteger % 2;
-  else
-    return dfs(maxChoosableInteger, desiredTotal, 0);
+  int *vis = (int *)calloc(pow(2, 21), sizeof(int)), state = 0;
+  long long sum = 0;
+  bool ans = dfs(vis, state, sum, maxChoosableInteger, desiredTotal);
+  free(vis);
+  return ans;
 }
 
 int main() {
diff --git a/can_i_win.py b/can_i_win.py
@@ -19,26 +19,27 @@ class Solution(object):
         :type desiredTotal: int
         :rtype: bool
         """
-
-        def get_sum(num):
-            i, curr = 1, 0
-            while i <= 20 and num:
-                if num & 1:
-                    curr += i
-                i += 1
-                i >>= 1
-            return curr
-
-        def dfs(pick, player):
-            curr = get_sum(pick)
-            for i in range(maxChoosableInteger):
-                if pick & (1 << i):
-                    continue
-                if curr + i + 1 >= desiredTotal or not dfs(pick | (1 << i), player ^ 1):
+        if desiredTotal <= 0:
+            return True
+        if sum(range(1, maxChoosableInteger + 1)) < desiredTotal:
+            return False
+        vis = {}
+
+        def dfs(choices, total):
+            state = tuple(choices)
+            if state in vis:
+                return vis[state]
+            if choices[-1] >= total:
+                vis[state] = True
+                return True
+            for i in range(len(choices)):
+                if not dfs(choices[:i] + choices[i + 1 :], total - choices[i]):
+                    vis[state] = True
                     return True
+            vis[state] = False
             return False
 
-        return dfs(0, 0)
+        return dfs(list(range(1, maxChoosableInteger + 1)), desiredTotal)
 
 
 if __name__ == "__main__":