[Java] DP with a bit of explanation, O(n^2) time, O(n) space
First a bit of analysis:\n\n\n\n\n\nFrom the table we can find the state transfer function:\n\nresult(stones[0 .. n]) = max(\n\tsum(stones[1 .. n]) - result(sto
First a bit of analysis:\n\n![image](https://assets.leetcode.com/users/images/ad65926b-0d16-4c1a-891f-ce6fe171519d_1607832274.9623156.png)\n\n\n\nFrom the table we can find the state transfer function:\n```\nresult(stones[0 .. n]) = max(\n\tsum(stones[1 .. n]) - result(stones[1 .. n]),\n\tsum(stones[0 .. n - 1]) - result(stones[0 .. n - 1])\n)\n```\n\nNotice this function holds for `n >= 3`, so we need special consideration for the case where `n == 2`, where the result calculation is reduced to max(A, B).\n\nOptimisation 1: since the results of stones of length `l` is only related to that with length `l - 1`, we only need to maintain a 1-D array.\n\nOptimisation 2: a quick way to calculate `sum(stones[i .. j])` is to first calculate the prefix sum of stones, such that `prefix[i] = sum(stones[0 .. i])`, then we can easily find `sum(stones[i .. j]) == prefix[j] - prefix[i - 1]`\n\nThus the full solution:\n\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int n = stones.length, prefix[] = new int[n], dp[] = new int[n];\n\n        for (var i = 0; i < n; i ++) {\n            prefix[i] = stones[i] + (i > 0 ? prefix[i - 1] : 0);\n        }\n\n        for (var i = 0; i < n - 1; i ++) {\n            dp[i]= Math.max(stones[i], stones[i + 1]);\n        }\n        \n        for (var l = 2; l < n; l ++) {\n            // length of current stone array = l + 1\n            for (var i = 0; i < n - l; i ++) {\n                dp[i] = Math.max(\n                    prefix[i + l - 1] - (i > 0 ? prefix[i - 1] : 0) - dp[i],      // sum(i, i + l - 1)\n                    prefix[i + l] - prefix[i] - dp[i + 1]\n                );\n            }\n        }\n        \n        return dp[0];\n    }\n}\n```
[]