【筆記】Nim

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

//【範例】LeetCode 292. Nim Game
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1000;
int dp[maxn+5];

int solve(int x){
    // 定義遞迴終點
    if (x < 0) return 0;
    if (dp[x] != 0) return dp[x];
    // 枚舉所有移動
    int mn = 0;
    mn = min(mn, solve(x-1)); //先手拿1顆石頭
    mn = min(mn, solve(x-2)); //先手拿2顆石頭
    mn = min(mn, solve(x-3)); //先手拿3顆石頭
    if (mn == -1) return dp[x] = 1; //只要有一步能讓後手輸
    else return dp[x] = -1; //後手不管怎樣都贏
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        //dp: -1 (輸), 0 (未定), 1 (贏)
        memset(dp, 0, sizeof(dp));
        solve(n); //先手一開始看到n顆石頭
        cout << (dp[n] == 1) << endl; 
    }
}