Skip to content

1690. Stone Game VII 👍

Approach 1: Top-down

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int stoneGameVII(vector<int>& stones) {
    const int n = stones.size();
    vector<vector<int>> mem(n, vector<int>(n));
    vector<int> prefix(n + 1);
    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
    return stoneGameVII(stones, 0, n - 1, prefix, mem);
  }

 private:
  // Returns the maximum score you can get more than your opponent in
  // stones[i..j].
  int stoneGameVII(const vector<int>& stones, int i, int j,
                   const vector<int>& prefix, vector<vector<int>>& mem) {
    if (i == j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];
    // Remove stones[i] to get sum(stones[i + 1..j]).
    const int removeLeft = prefix[j + 1] - prefix[i + 1] -
                           stoneGameVII(stones, i + 1, j, prefix, mem);
    // Remove stones[j] to get sum(stones[i..j - 1]).
    const int removeRight = prefix[j] - prefix[i] -  //
                            stoneGameVII(stones, i, j - 1, prefix, mem);
    return mem[i][j] = max(removeLeft, removeRight);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int stoneGameVII(int[] stones) {
    final int n = stones.length;
    Integer[][] mem = new Integer[n][n];
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; ++i)
      prefix[i + 1] = prefix[i] + stones[i];
    return stoneGameVII(stones, 0, n - 1, prefix, mem);
  }

  // Returns the maximum score you can get more than your opponent in
  // stones[i..j].
  private int stoneGameVII(int[] stones, int i, int j, int[] prefix, Integer[][] mem) {
    if (i == j)
      return 0;
    if (mem[i][j] != null)
      return mem[i][j];
    // Remove stones[i] to get sum(stones[i + 1..j]).
    final int removeLeft = prefix[j + 1] - prefix[i + 1] - //
                           stoneGameVII(stones, i + 1, j, prefix, mem);

    // Remove stones[j] to get sum(stones[i..j - 1]).
    final int removeRight = prefix[j] - prefix[i] - //
                            stoneGameVII(stones, i, j - 1, prefix, mem);
    return mem[i][j] = Math.max(removeLeft, removeRight);
  }
}

Approach 2: Bottom-up

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int stoneGameVII(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := the maximum score you can get more than your opponent in
    // stones[i..j]
    vector<vector<int>> dp(n, vector<int>(n));
    vector<int> prefix(n + 1);

    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        dp[i][j] = max(prefix[j + 1] - prefix[i + 1] - dp[i + 1][j],
                       prefix[j] - prefix[i] - dp[i][j - 1]);
      }

    return dp[0][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int stoneGameVII(int[] stones) {
    final int n = stones.length;
    // dp[i][j] := the maximum score you can get more than your opponent in stones[i..j]
    int[][] dp = new int[n][n];
    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; ++i)
      prefix[i + 1] = stones[i] + prefix[i];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        dp[i][j] = Math.max(prefix[j + 1] - prefix[i + 1] - dp[i + 1][j],
                            prefix[j] - prefix[i] - dp[i][j - 1]);
      }

    return dp[0][n - 1];
  }
}