Solve Nim Game Leetcode with Recusion(DP)-CodePudding

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];
};

CodePudding user response：

You're probably right that the problem is there. I think you need to reconsider that a bit.

To my mind, this logic is overly complex, especially the handling of myChance. You can simplify this by simply inverting the value from the cache for n - 1, n - 2, and n - 3 and orring together the results.

It might look like this:

const canWinNim = (n, memo = {}) => 
  n in memo 
    ? memo [n]
  : memo [n] = (n == 0) 
    ? false 
  : n < 4 
    ? true 
  : !canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)

const testCases = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

testCases .forEach (n => console .log (`${n} => ${canWinNim (n)}`))

.as-console-wrapper {max-height: 100% !important; top: 0}

If nested conditional operators (ternaries) offend you, you could rewrite it like this:

const canWinNim = (n, memo = {}) => { 
  if (n in memo) { 
    return memo [n]
  }
  let val
  if (n == 0) {
    val = false
  } else if (n < 4) {
    val = true
  } else {
    val = !canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)
  }
  memo [n] = val
  return val
}

You can also, if you choose, replace

!canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)

with

!(canWinNim (n - 1, memo) && canWinNim (n - 2, memo) && canWinNim (n - 3, memo))