I came up with the following DP recurrence, and it passes systest. But now that I am thinking about why it works, I am not completely able to come up with a proof. Can someone shed some light.
class EllysCheckers {
public:
string getWinner(string b) {
vector<bool> dp(b.size(), false);
for(int i=1;i<b.size();i++)
{
int c=0;
for(int k=0;k<i;k++)
{
if(b[k]=='o')
c++;
}
if(c%2==0)
{
dp[i] = dp[i1];
}
else
{
dp[i] = !dp[i1];
}
}
return dp[b.size()1]==true?"YES" : "NO";
}
};
Whenever the count of checkers between board position 0 to i1 is even, the solution to dp[i] is dp[i1], otherwise !dp[i1]. At first I thought it was because the total checkers were evenly distributed between the two players, so that in case of odd number of them, the winning player switches, and in case of even, it doesn't. But I don't think that is right.
