# 1140. Stone Game II¶

• 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 stoneGameII(vector& piles) { const int n = piles.size(); vector> mem(n, vector(n)); vector suffix = piles; // suffix[i] := sum(piles[i..n)) for (int i = n - 2; i >= 0; --i) suffix[i] += suffix[i + 1]; return stoneGameII(suffix, 0, 1, mem); } private: // Returns the maximum number of stones Alice can get from piles[i..n) with M. int stoneGameII(const vector& suffix, int i, int M, vector>& mem) { if (i + 2 * M >= mem.size()) return suffix[i]; if (mem[i][M] > 0) return mem[i][M]; int opponent = suffix[i]; for (int X = 1; X <= 2 * M; ++X) opponent = min(opponent, stoneGameII(suffix, i + X, max(M, X), mem)); return mem[i][M] = suffix[i] - opponent; } }; 
  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 stoneGameII(int[] piles) { final int n = piles.length; int[][] mem = new int[n][n]; int[] suffix = new int[n]; // suffix[i] := sum(piles[i..n)) Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1)); suffix[n - 1] = piles[n - 1]; for (int i = n - 2; i >= 0; --i) suffix[i] = suffix[i + 1] + piles[i]; return stoneGameII(suffix, 0, 1, mem); } // Returns the maximum number of stones Alice can get from piles[i..n) with M. private int stoneGameII(int[] suffix, int i, int M, int[][] mem) { if (i + 2 * M >= suffix.length) return suffix[i]; if (mem[i][M] != -1) return mem[i][M]; int opponent = suffix[i]; for (int X = 1; X <= 2 * M; ++X) opponent = Math.min(opponent, stoneGameII(suffix, i + X, Math.max(M, X), mem)); return mem[i][M] = suffix[i] - opponent; } }