https://leetcode.com/problems/can-i-win/
Solution:
One of the important constrains is that each element can only be used once. Therefore, if we use dp strategy, we have to take it into account since it will change the "status" of the sub-questions.
We can use binary representation for the status of the element usage. For each element, if it is not used yet, its status is 1; once used, become 0. So there will be 2^n status in total, where n is the total number of elements.
In order to increase efficiency, we need memorization of the results for the status visited previously, which is a very common trick to short the running time. Since we have already calculated it, there's no need for re-calculation. For this question, we will use a hashmap for implementation.
Another parameter for each sub-status is the target value, and it will also changes (becomes smaller) as some elements is chosen. So here we will use a vector<unordered_map<int, bool> > structure to store the status information, to memorize both the target value and status information. The index of the vector will be used for the target value.
The two players in this game will always play optimally, so once there is one way that the second player cannot win, the first will win. If for all the possible ways, the second player can always win, then the first player have to lose. At this point, we will use dsf strategy for searching.
Code:
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int m = maxChoosableInteger, d = desiredTotal;
if(m>=d) return true;
if(m*(m+1)<d*2) return false;
vector<unordered_map<int, bool>> dp(d);
int t = (1<<m) - 1;
return canWin(m, d, dp, t);
}
private:
bool canWin(int m, int d, vector<unordered_map<int, bool>> &dp, int sta){
if(dp[d-1].count(sta)) return dp[d-1][sta];
for(int i=0; i<m; ++i){
if((1<<i)&sta){// i element is not used.
if(i+1>=d || !canWin(m, d-i-1, dp, sta^(1<<i))){
dp[d-1][sta] = true;
return true;
}
}
}
dp[d-1][sta] = false;//the second player always win.
return false;
}
};
After finishing this, also noticed that there are some other way for implementation,
and here is one example with discussion:
https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation
"After solving several "Game Playing" questions in leetcode, I find
them to be pretty similar. Most of them can be solved using the
top-down DP approach, which "brute-forcely" simulates every possible state of the game.
The key part for the top-down dp strategy is that we need to
avoid repeatedly solving sub-problems. Instead, we should use some strategy to "remember" the outcome of sub-problems."
"For this question, the key part is:
what is the state of the game? Intuitively, to uniquely determine the result of any state, we need to know:
- The unchosen numbers
- The remaining desiredTotal to reach
A second thought reveals that
1) and
2) are actually related because we can always get the
2) by deducting the sum of chosen numbers from original desiredTotal.
Then the problem becomes how to describe the state using
1)."
(one of the equivalent ways to understand this is that if we know condition 1 (the unchosen numbers) only, then we can determine the state completely, since that every element can be only used once.)
So only one hashmap is enough to memorize the sub-status for choosing elements.
Code:
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int m = maxChoosableInteger, d = desiredTotal;
if(m>=d) return true;
if(m*(m+1)<d*2) return false;
unordered_map<int, bool> dp;
return canWin(m, d, dp, 0);
}
private:
bool canWin(int m, int d, unordered_map<int, bool> &dp, int sta){
if(dp.count(sta)) return dp[sta];
for(int i=0; i<m; ++i){
if(((1<<i)&sta)==0){
if(i+1>=d || !canWin(m, d-i-1, dp, sta|(1<<i))){
dp[sta] = true;
return true;
}
}
}
dp[sta] = false;
return false;
}
};
