Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 464 Can I Win - State Design

Dp[mask]

dp[mask]dp[\text{mask}] = true if the current player can win given that numbers indicated by mask are already used. We also track the current total.

But total is determined by which numbers are used, so we can compute it from the mask (or pass it as a parameter for efficiency). Base case: if any available number makes total \geq target, current player wins. Otherwise, try each available number and check if opponent loses from the resulting state.