2-Solutions Recursive and Top-Down DP
Intuition\nMaximization of the choices we pick and constraints were 1000 so N^2 could work\n\n# Approach\nWe have two choiches at a point :\n- Whether pick from
# Intuition\nMaximization of the choices we pick and constraints were 1000 so N^2 could work\n\n# Approach\nWe have two choiches at a point :\n- Whether pick from the start\n- Or pick from the end \n\nAnd for maintaining the profit sum we could directly subtract it from the sum that we make the call for the rest.\n\n# Complexity\n- Time complexity: O(2^N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(recursive stack)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code Recursive\n```\nclass Solution {\npublic:\n    int dfs(int i , int j , int sum , vector<int>& stones){\n        if(i >= j){\n            return 0;\n        }\n        if(sum < 0){\n            return 0;\n        }\n        int choose_front = sum - stones[i] - \n                        dfs(i + 1 , j , sum - stones[i] , stones);\n        int choose_back = sum - stones[j] - \n                        dfs(i , j - 1 , sum - stones[j] , stones);\n        int profit = max(choose_back , choose_front);\n        return profit;\n    }\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        int sum = 0 ;\n        for(auto it : stones){\n            sum += it;\n        }\n        return dfs(0 , n - 1 , sum , stones);\n    }\n};\n```\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code Top - Down DP\n```\nclass Solution {\npublic:\n    int dfs(int i , int j , int sum , vector<int>& stones ,\n            vector<vector<int>>& dp){\n        if(i >= j){\n            return 0;\n        }\n        if(sum < 0){\n            return 0;\n        }\n        if(dp[i][j] != -1){\n            return dp[i][j];\n        }\n        int choose_front = sum - stones[i] - \n                    dfs(i + 1 , j , sum - stones[i] , stones , dp);\n        int choose_back = sum - stones[j] - \n                    dfs(i , j - 1 , sum - stones[j] , stones , dp);\n        int profit = max(choose_back , choose_front);\n        return dp[i][j] = profit;\n    }\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        vector<vector<int>> dp(n + 1 , vector<int>(n + 1 , -1));\n        int sum = 0 ;\n        for(auto it : stones){\n            sum += it;\n        }\n        return dfs(0 , n - 1 , sum , stones , dp);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']