Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 464 Can I Win - Problem Statement

LeetCode 464

Two players pick numbers from 11 to nn (each number used at most once). The first player to reach a running total \geq target wins. Can the first player guarantee a win? Example: n=10n = 10, target =11= 11. Player 1 picks 1010. Player 2 picks any number. If Player 2 picks 11, total is 1111 and Player 2 wins.

So Player 1 should pick differently... can they force a win? Here's where Bitmask DP meets Game Theory. The set of used numbers is a subset, perfect for bitmask. The game state is which numbers remain.