1378. Can I Win (Bitmask Game DP)

Two players alternately pick an unused integer from 1 to maxChoosableInteger and add it to a shared running total. The player who first makes the total reach or exceed desiredTotal wins. Assuming both play optimally, determine whether the first player can force a win.

Input: A JSON object {"maxChoosableInteger": <largest pick>, "desiredTotal": <target>}.

Output: Return true if the first player can force a win, otherwise false.

Examples

Input: {"maxChoosableInteger":10,"desiredTotal":11}
Output: false
Explanation: Every opening move lets the opponent win -> false.

Input: {"maxChoosableInteger":10,"desiredTotal":0}
Output: true
Explanation: The target is already reached -> true.

Constraints

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

Asked by