The score Alice can bank from any stretch of stones depends only on that stretch, so I memoize on intervals: `dp[i][j]` is the most she can score starting from stones `i..j`. Each turn she picks a cut, Bob throws away the heavier side, and she keeps playing on whatever survives — and the survivor is always contiguous, which is exactly what lets memoization work. The naive instinct is to simulate the game tree: try every cut, recurse on the kept side, branch again. That is exponential, because the same sub-row gets re-solved from countless different paths. Since a kept side is pinned down entirely by its two endpoints, I collapse all those paths into one `dp[i][j]`. For a cut at `k`, `left = sum(i..k)` and `right = sum(k+1..j)`. If `left < right`, Bob tosses the right side and Alice banks `left + dp[i][k]`; if `left > right`, she banks `right + dp[k+1][j]`; on a tie she chooses, so it is the max of the two. Prefix sums make each `sum` an O(1) lookup, so the whole thing is a bottom-up interval DP by length. ### Worked example Take `[6, 2, 3]`. Alice cuts after the first stone: `left = 6`, `right = 5`. Bob discards the heavier side (the `6`), she banks `5` and keeps `[2, 3]`. Now she cuts between them: `left = 2`, `right = 3`, Bob discards the `3`, she banks `2` and is left with a single stone, so the game stops. Total `5 + 2 = 7`, which is what `dp[0][2]` reports. ### Complexity - Time O(n^3) — there are O(n^2) intervals and each scans O(n) cut points; with n up to 500 that is about 1.2e8 operations, fine in C++. - Space O(n^2) — the `dp` table over every interval, plus an O(n) prefix-sum array. ### Code (C++) ```cpp class Solution { public: int stoneGameV(vector& stoneValue) { int n = stoneValue.size(); vector pre(n + 1, 0); for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stoneValue[i]; auto sum = [&](int i, int j) { return pre[j + 1] - pre[i]; }; vector> dp(n, vector(n, 0)); for (int len = 2; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; int best = 0; for (int k = i; k < j; k++) { int left = sum(i, k), right = sum(k + 1, j); if (left < right) best = max(best, left + dp[i][k]); else if (left > right) best = max(best, right + dp[k + 1][j]); else best = max(best, max(left + dp[i][k], right + dp[k + 1][j])); } dp[i][j] = best; } } return dp[0][n - 1]; } }; ``` ### One note The equal-sum cut is the only place Alice has agency beyond choosing where to cut, and it is where a rushed solution breaks. When `left == right`, Bob lets her decide which half to discard, so she keeps the side with the better continuation — `max(left + dp[i][k], right + dp[k+1][j])` — not a fixed one. Default to either branch and you silently forfeit points on any symmetric split. Whenever a rule hands the choice back to your player on a tie, make the tie its own branch rather than folding it into one of the inequalities.