TopCoder SRM575: TheNumberGameDivTwo

DP[n] = 「初期値が n のとき先手必勝」とすると
DP[n] =　n - 「nの1とn以外の約数」のときについて、先手必勝ではないものあれば、True。

あとはこの漸化式を計算する。

public class TheNumberGameDivTwo {
    public string find(int n) {
        var dp = new bool[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int x = 2; x < i; x++) {
                if (i % x == 0) {
                    if (!dp[i - x]) dp[i] = true;
                }
            }
        }
        return dp[n] ? "John" : "Brus";
    }
}