✅✅Faster || Easy To Understand || C++ Code
Recursion && Memoization\n\n Time Complexity :- O(N * N)\n\n Space Complexity :- O(N * N)\n\n\nclass Solution {\npublic:\n    \n    // declare a prefix array\n 
* ***Recursion && Memoization***\n\n* ***Time Complexity :- O(N * N)***\n\n* ***Space Complexity :- O(N * N)***\n\n```\nclass Solution {\npublic:\n    \n    // declare a prefix array\n    \n    vector<int> prefix_sum;\n    \n    // declare a dp\n    \n    vector<vector<int>> dp;\n    \n    int helper(vector<int>& stones, int start, int end)\n    {\n        // base case\n        \n        if(start >= end)\n        {\n            return 0;\n        }\n        \n        // if already calculated\n        \n        if(dp[start][end] != -1)\n        {\n            return dp[start][end];\n        }\n        \n        // remove from start\n        \n        int start_score = prefix_sum[end] - prefix_sum[start] - helper(stones, start + 1, end);\n        \n        // remove from end\n        \n        int end_score = 0;\n        \n        if(end - 1 >= 0)\n        {\n            end_score += prefix_sum[end - 1];\n        }\n        \n        if(start - 1 >= 0)\n        {\n            end_score -= prefix_sum[start - 1];\n        }\n        \n        end_score -= helper(stones, start, end - 1);\n        \n        // take the maximum from both start_score and end_score\n        \n        return dp[start][end] = max(start_score, end_score);\n    }\n    \n    int stoneGameVII(vector<int>& stones) {\n        \n        int n = stones.size();\n        \n        // fill prefix_sum array\n        \n        prefix_sum.resize(n, 0);\n        \n        prefix_sum[0] = stones[0];\n        \n        for(int i = 1; i < n; i++)\n        {\n            prefix_sum[i] = prefix_sum[i - 1] + stones[i];\n        }\n        \n        // resize dp\n        \n        dp.resize(n + 1);\n        \n        // initialize dp with -1\n        \n        dp.assign(n + 1, vector<int> (n + 1, -1));\n        \n        return helper(stones, 0, n - 1);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']