# 1563. Stone Game V

• Time: $O(n^3)$
• 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 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public: int stoneGameV(vector& stoneValue) { const int n = stoneValue.size(); // dp[i][j] := max score that Alice can obtain from stoneValue[i..j] dp.resize(n, vector(n, INT_MIN)); prefix.resize(n + 1); partial_sum(begin(stoneValue), end(stoneValue), begin(prefix) + 1); return stoneGameV(stoneValue, 0, n - 1); } private: vector> dp; vector prefix; int stoneGameV(const vector& stoneValue, int i, int j) { if (i == j) return 0; if (dp[i][j] > 0) return dp[i][j]; // Try all possible partitions for (int p = i; p < j; ++p) { // Sum of stoneValue[i..p] const int leftSum = prefix[p + 1] - prefix[i]; const int throwRight = leftSum + stoneGameV(stoneValue, i, p); // Sum of stoneValue[p + 1..j] const int rightSum = prefix[j + 1] - prefix[p + 1]; const int throwLeft = rightSum + stoneGameV(stoneValue, p + 1, j); if (leftSum < rightSum) // Bob throws right row dp[i][j] = max(dp[i][j], throwRight); else if (leftSum > rightSum) // Bob throws left row dp[i][j] = max(dp[i][j], throwLeft); else // Alice decide which row to throw dp[i][j] = max({dp[i][j], throwLeft, throwRight}); } return dp[i][j]; } }; 
  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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public int stoneGameV(int[] stoneValue) { final int n = stoneValue.length; // dp[i][j] := max score that Alice can obtain from stoneValue[i..j] dp = new int[n][n]; Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MIN_VALUE)); prefix = new int[n + 1]; for (int i = 0; i < n; ++i) prefix[i + 1] = stoneValue[i] + prefix[i]; return stoneGameV(stoneValue, 0, n - 1); } private int[][] dp; private int[] prefix; private int stoneGameV(int[] stoneValue, int i, int j) { if (i == j) return 0; if (dp[i][j] > 0) return dp[i][j]; // Try all possible partitions for (int p = i; p < j; ++p) { // Sum of stoneValue[i..p] final int leftSum = prefix[p + 1] - prefix[i]; final int throwRight = leftSum + stoneGameV(stoneValue, i, p); // Sum of stoneValue[p + 1..j] final int rightSum = prefix[j + 1] - prefix[p + 1]; final int throwLeft = rightSum + stoneGameV(stoneValue, p + 1, j); if (leftSum < rightSum) // Bob throws right row dp[i][j] = Math.max(dp[i][j], throwRight); else if (leftSum > rightSum) // Bob throws left row dp[i][j] = Math.max(dp[i][j], throwLeft); else // Alice decide which row to throw dp[i][j] = Math.max(dp[i][j], Math.max(throwLeft, throwRight)); } return dp[i][j]; } }