1
class Solution {
2
  public int stoneGameII(int[] piles) {
3
    Map<String, Integer> memo = new HashMap<>();
4
    int diff = stoneGame(piles, 1, 0, 0, memo);
5
    int totalSum = 0;
6
    for (int ele : piles) totalSum += ele;
7
    return (diff + totalSum) / 2;
8
  }
9

10
  public int stoneGame(int[] piles, int M, int index, int turn, Map<String, Integer> memo) {
11
    if (index >= piles.length) return 0;
12
    if (memo.containsKey(index + "-" + M + "-" + turn))
13
      return memo.get(index + "-" + M + "-" + turn);
14
    int score = 0, maxScore = Integer.MIN_VALUE;
15
    // Alice's turn
16
    if (turn == 0) {
17
      for (int X = 1; X <= 2 * M && index + X - 1 < piles.length; X++) {
18
        score += piles[index + X - 1];
19
        maxScore = Math.max(maxScore, stoneGame(piles, Math.max(X, M), index + X, 1, memo) + score);
20
      }
21
      memo.put(index + "-" + M + "-" + turn, maxScore);
22
      return maxScore;
23
    }
24
    // Bob's turn
25
    int minScore = Integer.MAX_VALUE;
26
    for (int X = 1; X <= 2 * M && index + X - 1 < piles.length; X++) {
27
      score += piles[index + X - 1];
28
      minScore = Math.min(minScore, stoneGame(piles, Math.max(X, M), index + X, 0, memo) - score);
29
    }
30
    memo.put(index + "-" + M + "-" + turn, minScore);
31
    return minScore;
32
  }
33
}