使用 Recusion(DP) 解决 Nim 游戏 Leetcode

Question

我正在尝试解决以下 Nim Game 的 leetcode 问题。 https://leetcode.com/problems/nim-game/

O(1) 中的一个简单解决方案是：

var canWinNim = function(n) {    
   return n%4 !== 0;
};

不过我也在尝试用DP来解决。下面是我的代码是不正确的。我相信最后的 else 块中存在一些问题。请帮忙。

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

Answer 1

您可能是对的，问题就在那里。我认为你需要重新考虑一下。

在我看来，这个逻辑过于复杂，尤其是 myChance 的处理。您可以通过简单地反转缓存中 n - 1、n - 2 和 n - 3 的值和 or 将结果组合在一起来简化此操作。

它可能看起来像这样：

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}

如果嵌套条件运算符（三元组）冒犯了您，您可以这样重写它：

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
}

如果您愿意，您也可以替换

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

和

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

使用 Recusion(DP) 解决 Nim 游戏 Leetcode

Solve Nim Game Leetcode with Recusion(DP)

javascript

recursion

dynamic-programming