[Java] <O(n^2), O(n)> DP with clean code beats 100%
Even though Bob always loses the game, his goal to minimize the final score difference can be seen as trying to maximize the score difference in his turns i.e. 
Even though Bob always loses the game, his goal to minimize the final score difference can be seen as trying to maximize the score difference in his turns i.e. score(B) - score(A). Alice\'s goal is also the same, maximize score difference in his turns i.e. score(A) - score(B).\n\nLet ```dp[i][j] = maximum value of score(current player) - score(other player) using stones[i..j]```.\n\n- If current player removes ```stones[i]```:\n\t- ```score(current player)``` increases by ```sum of stones[i+1..j]``` thereby also increasing the score difference by same amount.\n\t- game continues on ```stones[i+1..j]``` where other player becomes the current player so ```dp[i+1][j]``` represents the score difference from other player\'s point of view so to use it in our recurrence relation, we need to negate it.\n- Similar reasoning applies to removing ```stones[j]```\n\nSo, ```dp[i][j] = max(sum of stones[i+1..j] - dp[i+1][j], sum of stones[i..j-1] - dp[i][j-1])```\n\nSums of stones in a range can be computed faster using prefix sums or on the fly if you\'re clever ;)\n\nSo, ```dp[i][j] = max(sum[i][j] - stones[i] - dp[i+1][j], sum[i][j] - stones[j] - dp[i][j-1])```\n\n```\n// 35 ms. 96.66%\npublic int stoneGameVII(int[] stones) {\n    int n = stones.length;\n    int[][] dp = new int[n][n];\n    for(int i = n - 1; i >= 0; i--) {\n        for(int j = i + 1, sum = stones[i]; j < n; j++) {\n            sum += stones[j];\n            dp[i][j] = Math.max(sum - stones[i] - dp[i + 1][j], sum - stones[j] - dp[i][j - 1]);\n        }\n    }\n    return dp[0][n - 1];\n}\n```\n\nTime complexity: O(n^2)\nSpace complexity: O(n^2)\n\nSince answer for R range dp values (R = j - i + 1) depends only on R-1 range dp values, we can reduce space complexity by only keeping last range values.\n\n```\n// 16 ms. 100%\npublic int stoneGameVII(int[] stones) {\n    int n = stones.length;\n    int[] dp = new int[n];\n    for(int i = n - 1; i >= 0; i--) {\n        for(int j = i + 1, sum = stones[i]; j < n; j++) {\n            sum += stones[j];\n            dp[j] = Math.max(sum - stones[i] - dp[j], sum - stones[j] - dp[j - 1]);\n        }\n    }\n    return dp[n - 1];\n}\n```\n\nTime complexity: O(n^2)\nSpace complexity: O(n)
['Java']