n the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.
Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.
like min-max search? yes, let me try it. Each actor will return false if one of the choice can win in force. Let me do the brute-force first. If we want to do the min max, we have to know which is min and which is max. I guess, if current + target cannot > target, we only need to choose the minimum? Nah, it's incorrect. We still have to the all search?
oh, maybe memory search? But we have store the choosen. We have to hash a choosen array => 20 bits integer.
yes it's correct, but TLE. Let me do some analysis. yes, I use a hash here to use bits number and cureent sum value to store the state. But still TLE. Let me see the std.
oh, fuck, if we know which number has been chosen, we will know the sum right? Therefore, we only need to store the number we used before. I think...basically, we have the same idea.
But I failed. My code writing stlye is really poor. Also, we only need to store the integer we have used into the hashmap. I add a sum as a hashmap key.
oh, after deleteing this key in my code, ac!