Estoy tratando de resolver el siguiente problema de leetcode de Nim Game. https://leetcode.com/problems/nim-game/
Una solución simple en O(1) es:
var canWinNim = function(n) { return n%4 !== 0; };Pero también estoy tratando de resolverlo usando DP. A continuación se muestra mi código que es incorrecto. Creo que hay algún problema en el bloque else al final. Por favor ayuda.
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]; };Probablemente tengas razón en que el problema está ahí. Creo que deberías reconsiderarlo un poco.
En mi opinión, esta lógica es demasiado compleja, especialmente el manejo de myChance . Puede simplificar esto simplemente invirtiendo el valor de la memoria caché para n - 1 , n - 2 y n - 3 or combinar los resultados.
Podría verse así:
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}Si los operadores condicionales anidados (ternarios) lo ofenden, puede reescribirlo así:
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 }También puede, si lo desea, reemplazar
!canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)con
!(canWinNim (n - 1, memo) && canWinNim (n - 2, memo) && canWinNim (n - 3, memo))