Interval dynamic programming solution with tracing bottom-up approach
IntuitionThis problem falls under Interval DP problem, where we progressively break down a larger interval into smaller intervals. The idea is to compute the op
# Intuition
This problem falls under [Interval DP problem](https://algo.monster/problems/dp_interval_intro), where we progressively break down a larger interval into smaller intervals. The idea is to compute the optimal strategy for Alice and Bob as they remove stones from either end.
# Approach

1. Compute the prefix sum to efficiently calculate the sum of any subarray in $$O(1)$$.
1. Start processing subarrays of length 2 (the smallest playable intervals) and progressively increase the interval size.
1. Iterate over all possible subarrays:
1 - length 2 : [0,1] , [1,2] , [2,3] , [3,4]
2 - length 3 : [0,2], [1,3] , [2,4]
3 - length 4 : [0,3], [1,4]
4 - length 5 : [0,4]

Let’s assume Alice starts first with the entire array [0,4]. She can choose either the leftmost or rightmost stone, increasing her score by the remaining sum. Then, Bob plays optimally, removing another stone and maximizing his score.

Since both players are playing optimally, we need to compute their score difference recursively.

To solve this efficiently, we use dynamic programming:

# **Transition**:
- Option 1: Remove the leftmost stone → The score gained is sum of remaining elements, minus the best Bob can achieve.
- Option 2: Remove the rightmost stone → The score gained is sum of remaining elements, minus the best Bob can achieve.
- Take the maximum of the two options to get the optimal strategy.

# Complexity
- Time complexity:
$$O(n^2)$$
- Space complexity:
- $$O(n^2)$$ + $$O(n)$$ for the prefix sum.
```java []
class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int [] prefix = new int[n + 1];
        prefix[0] = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + stones[i - 1];
        }
        int [][] dp = new int[n][n];
        for(int IntervalSteps = 2; IntervalSteps <= n; IntervalSteps++){
            for(int LeftPointer = 0; LeftPointer  <= n - IntervalSteps; LeftPointer++){
                int RightPointer = LeftPointer + IntervalSteps - 1;
                    int removeMostLeftItem = prefix[RightPointer + 1] - prefix[LeftPointer + 1] - dp[LeftPointer + 1][RightPointer];
                    int removeMostRightItem = prefix[RightPointer] - prefix[LeftPointer] - dp[LeftPointer][RightPointer - 1 ];
                    dp[LeftPointer][RightPointer] = Math.max(removeMostLeftItem , removeMostRightItem);
            }
        }
        return dp[0][n - 1];
    }
}
```
['Dynamic Programming', 'Java']