I am trying to solve the following leetcode problem of Nim Game.
https://leetcode.com/problems/nim-game/
One simple solution in O(1) is:
var canWinNim = function(n) {
return n%4 !== 0;
};
But I am also trying to solve it using DP. Below is my code which is incorrect. I believe there is some issue in the else block at the end. Please help.
var canWinNim = function(n, myChance=true, memo={}) {
if(n in memo) return memo[n];
if(myChance){
if(n<=3) return true;
if(n===4) return false;
} else {
if(n<=3) return false;
if(n===4) return true;
}
let a = canWinNim(n-1, !myChance, memo);
let b = canWinNim(n-2, !myChance, memo);
let c = canWinNim(n-3, !myChance, memo);
if(myChance){
memo[n] = a||b||c;
return memo[n];
}
memo[n] = !(a||b||c);
return memo[n];
};