利用数学原理巧解运筹问题。

初版代码:

class Solution {
public:
  bool rec(map<int, bool> &cache, int n) {
    if (n < 1) {
      return false;
    }
    if (n <= 3) {
      return true;
    }
    
    auto itr = cache.find(n % 3);
    if (itr != cache.end()) {
      return itr->second;
    }
    
    auto ret = !rec(cache, n - 1) || !rec(cache, n - 2) || !rec(cache, n - 3);
    cache[n % 3] = ret;
    return ret;
  }
  bool canWinNim(int n) {
    map<int, bool> cache;
    return rec(cache, n);
  }
};

结果:栈溢出。

好吧,我们写成非递归的 DP:

class Solution {
public:
  bool canWinNim(int n) {
    if (n <= 3) {
      return true;
    }
    vector<int> dp(n + 1);
    for (int i = 1; i <= 3; i++)
    {
        dp[i] = 1;
    }
    
    for (int i = 4; i <= n; i++) {
      dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];      
    }
    return dp[n];
  }
};

结果:超出时间限制

难道是数学题?

dp[4] = 0
dp[5] = 1
dp[6] = 1
dp[7] = 1
dp[8] = 0
dp[9] = 1
dp[10] = 1
dp[11] = 1
dp[12] = 0
dp[13] = 1
dp[14] = 1
dp[15] = 1
dp[16] = 0
dp[17] = 1
dp[18] = 1
dp[19] = 1
dp[20] = 0
dp[21] = 1
dp[22] = 1
dp[23] = 1
dp[24] = 0
dp[25] = 1
dp[26] = 1
dp[27] = 1
dp[28] = 0
dp[29] = 1
dp[30] = 1
dp[31] = 1
dp[32] = 0
dp[33] = 1
dp[34] = 1
dp[35] = 1
dp[36] = 0
dp[37] = 1
dp[38] = 1
dp[39] = 1
dp[40] = 0
dp[41] = 1
dp[42] = 1
dp[43] = 1
dp[44] = 0
dp[45] = 1
dp[46] = 1
dp[47] = 1
dp[48] = 0
dp[49] = 1
dp[50] = 1
dp[51] = 1
dp[52] = 0
dp[53] = 1
dp[54] = 1
dp[55] = 1
dp[56] = 0
dp[57] = 1
dp[58] = 1
dp[59] = 1
dp[60] = 0
dp[61] = 1
dp[62] = 1
dp[63] = 1
dp[64] = 0
dp[65] = 1
dp[66] = 1
dp[67] = 1
dp[68] = 0
dp[69] = 1
dp[70] = 1
dp[71] = 1
dp[72] = 0
dp[73] = 1
dp[74] = 1
dp[75] = 1
dp[76] = 0
dp[77] = 1
dp[78] = 1
dp[79] = 1
dp[80] = 0
dp[81] = 1
dp[82] = 1
dp[83] = 1
dp[84] = 0
dp[85] = 1
dp[86] = 1
dp[87] = 1
dp[88] = 0
dp[89] = 1
dp[90] = 1
dp[91] = 1
dp[92] = 0
dp[93] = 1
dp[94] = 1
dp[95] = 1
dp[96] = 0
dp[97] = 1
dp[98] = 1
dp[99] = 1

显然,mod 4 == 0 则返回 0

最终代码:

class Solution {
public:
  bool canWinNim(int n) { return n % 4 != 0; }
};