Easy to Unuderstand || Top Down Solution || Game Theory
Intuition\nThe problem at hand involves finding the maximum score difference between two players, Alice and Bob, in a game where they take turns selecting stone
# Intuition\nThe problem at hand involves finding the maximum score difference between two players, Alice and Bob, in a game where they take turns selecting stones from either end of a row. The score for each player is determined by the sum of the stones they select. To solve this, we can use dynamic programming to compute the maximum score difference efficiently.\n\n# Approach\n1. **Dynamic Programming**: Utilize a 2D `dp` array where `dp[st][end]` represents the maximum score difference between two players when the array is restricted to the segment from index `st` to index `end`.\n2. **Recursive Function**: Define a recursive function `f` to compute the maximum score difference for a given segment. The function will:\n   - Calculate the score difference between selecting the first or last stone and the remaining segment, recursively calling itself on the updated segment.\n   - Use memoization to avoid redundant calculations and improve performance.\n\n# Complexity\n- **Time complexity**: The time complexity is $$O(n^2)$$ because for each pair `(st, end)` we might iterate through all possible split points.\n- **Space complexity**: The space complexity is $$O(n^2)$$ for storing the `dp` array.\n\n# Beats\n![Screenshot 2024-05-30 104718 - Copy.png](https://assets.leetcode.com/users/images/cfde1325-8a97-4e04-a041-439a9337b603_1717398651.8720968.png)\n\n\n# Code\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> dp ;\n     int f(vector<int> &v, int st, int end,int sum) {\n        if (st >= end || sum <= 0) return 0; // If there is only one stone, the score difference is 0.\n        if (dp[st][end] != -1) return dp[st][end];  \n        int front_score , end_score ;\n\n        front_score = sum - v[st] - f(v , st+1 , end , sum-v[st]) ;\n        end_score = sum - v[end] - f(v , st , end-1 , sum-v[end]) ;\n        return dp[st][end] = max(front_score , end_score);\n    }\n    int stoneGameVII(vector<int>& v) {\n        int n = v.size() , sum = 0 ;\n        for(auto a : v) sum += a ;\n        dp.clear() ;\n        dp.resize(n + 1, vector<int>(n + 1, -1));\n        return  f(v , 0 , n-1,sum)  ;\n    }\n};\n```\n# Note\nThis solution effectively utilizes dynamic programming to calculate the maximum score difference between two players, ensuring optimal performance for larger inputs.
['Array', 'Math', 'Dynamic Programming', 'Game Theory', 'C++']