Easy to understand | dp solution | O(n^2) |CPP
let me firstly explain the logic involved:\nbasically we have to find the minimum difference bw Alice and Bobs overall score.\n\nlet us consider the scenario fo
let me firstly explain the logic involved:\nbasically we have to find the minimum difference bw Alice and Bobs overall score.\n\nlet us consider the scenario for one move of alice:\nShe will have and array of stones from 0....n indices let it be A.Now she has 2 options:\n1) She takes the first element .Impact on her score would be as follows\n\t`score += (sum of array - A[0])`\n\tthis score would be further subtracted by the maximum possible difference bw score of alice and bob had the array been from 1...n\n\t\n\t\n\tOverall we might say that score_diff = **(sum of array - A[0]) - max. diff for A[1....n]** \n\t\n\t\n2) She takes the last element .Impact on her score would be as follows\n\t`score += (sum of array - A[n])`\nthis score would be further subtracted by the maxium possible difference bw score of alice and bob had the array been from 0...n-1\n\n\t\nOverall we might say that score_diff = **(sum of array - A[n]) - max. diff for A[0....n-1]** \n\nNow since we want to consider maximum option for our player, hence we consider the maximum so we consider the max of the above 2 options.\n\t\n\t\n\t\n```\n int stoneGameVII(vector<int>& stones) {\n        \n        vector<int> sums(stones.size()+1);\n        \n        for(int i=0;i<stones.size();i++){\n            sums[i+1] = sums[i]+stones[i];\n        }\n        vector<vector<int>> dp(stones.size(),vector<int> (stones.size()));\n        \n        for(int len=2;len<=stones.size();len++){\n            for(int i=0;i<=stones.size()-len;i++){\n                \n                int j = i+len-1;\n                \n                dp[i][j] = max(sums[j+1]-sums[i+1] -dp[i+1][j],sums[j]-sums[i]-dp[i][j-1] );\n                \n            }\n            \n        }\n        \n        \n        return dp[0][stones.size()-1];\n       \n    \n    }\n```\nLet dp[i][j] be the maximum difference the first player can get if the players play on A[i..j].\n\nIn the above code a prefix array has been used in order to find sum of the array efficiently.\n\nWe consider all the possible array with length ranging from 2 to N.\n```\ndp[i][j] = max(sums[j+1]-sums[i+1] -dp[i+1][j],sums[j]-sums[i]-dp[i][j-1] );\n```\nis the crux of the solution,\nhere ```sums[j+1]-sums[i+1]``` represents (sum of array - A[0]) and dp[i+1][j] represents the residual max difference bw scores.\n```sums[j]-sums[i]``` represents (sum of array - A[N]) and dp[i][j-1] represents the residual max difference bw scores.\n\nsince we are given an array of n elements dp[0][n-1] represents our answer.\n\n\n\n\n\n\t
['Dynamic Programming', 'C++']