Ming
0%

LeetCode-1025

Posted on Edited on In

LeetCode-1025 除数博弈

题目

结果

DP的结果

代码

公式法

1
2
3
4
5
class Solution {
    public boolean divisorGame(int N) {
        return N % 2 == 0;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean divisorGame(int N) {
        // Alice先手情况下的获胜方，true代表Alice，false代表Bob
        Boolean[] dp = N >= 4 ? new Boolean[N + 1] : new Boolean[4];
        for (int i = 1; i <= N; i++) {
            dp[i] = choose(dp, i);
        }
        return dp[N];
    }

    public boolean choose(Boolean[] dp, int index) {
        // 如果选择之后存在一种情况Alice必败，那么Alice必胜
        for (int i = 1; i < index; i++) {
            if (index % i == 0 && !dp[index - i]) {
                return true;
            }
        }
        return false;
    }
}

复杂度

公式法

  • 时间复杂度O（1）
  • 空间复杂度O（1）

DP

  • 时间复杂度：O（n²）

  • 空间复杂度：O（n）