C++| 100% | Detailed Explanation |  DP Approach
This is similar to Matrix Chain Multiplication Problem . The idea is to divide problem into subproblems and use them to constuct final solution using Dynamic Pr
This is similar to Matrix Chain Multiplication Problem . The idea is to divide problem into subproblems and use them to constuct final solution using Dynamic Programming .\n\nFor instance given input `[5,3,1,4,2]`\nUse the following `N x N` matrix to compute the result where `N is length of stones[]`\n```\n\t0 ,  1 ,  2 ,  3 ,  4  \n\t______________________\n0\t0 , -5 ,  3 , -7 ,  6 \n1\t0 ,  0 , -3 ,  1 , -7 \n2\t0 ,  0 ,  0 , -4 ,  2 \n3\t0 ,  0 ,  0 ,  0 , -4 \n4\t0 ,  0 ,  0 ,  0 ,  0 \n\n\t\n```\n\nWe construct the upper right triangle of Matrix, diagonally.\n```dP[i][j] represents score obtained if we have stones[i:j] only ```\nFor Alice\'s turn\n`dp[i][j] = max(sum[i+1:j] + dp[i+1][j] , sum[i:j-1] + dp[i][j-1] )`\nFor Bob\'s turn\n`dp[i][j] = min( -sum[i+1:j] + dp[i+1][j] , -sum[i:j-1] + dp[i][j-1] )`\n\nIn each iteration we use the results of previous iteration\n```\n\nSo first we initialise `1st Diagonal from left to right`\ndp[0][0] = 0\ndp[1][1] = 0\ndp[2][2] = 0\ndp[3][3] = 0\ndp[4][4] = 0\n\nThen in next iteration 2nd Diagonal\n\nIts Bob Turn\ndp[0][1] = min(-3+0 , -5+0) => -5       [5,3]\ndp[1][2] = min(-3+0 , -1+0) => -3       [3,1]\ndp[2][3] = min(-1+0 , -4+0) => -4       [1,4]\ndp[3][4] = min(-4+0 , -2+0) => -4       [4,2]\n\nThen in next iteration 3rd Diagonal\n\nIts Alice Turn\ndp[0][2] = max(4-3 , 8-5) => 3       [5,3,1]\ndp[1][3] = max(5-4 , 4-3) => 1       [3,1,4]\ndp[2][4] = max(5-4 , 6-4) => 2       [1,4,2]\n\nThen in next iteration 4th Diagonal\n\nIts Bob Turn  \ndp[0][3] = min(-8+1 , -9+3) => -7       [5,3,1,4]\ndp[1][4] = min(-7+2 , -8+1) => -7       [3,1,4,2]\n\nThen in next iteration 5th Diagonal\n\nIts Alice Turn \ndp[0][4] = max(10-7 , 13-7) => 6   ANS       [5,3,1,4,2]\n```\n\nWe have got the answer\n\n\n```\nclass Solution {\npublic:\n    int stoneGameVII(vector<int>& stones) {\n        ios::sync_with_stdio(false);\n        cin.tie(NULL);\n        int len = stones.size();\n        \n        int dp[1001][1001] = {0};\n        \n        /*Prefix Sum array for O(1) Sum calculation | sum (i to j inclusive) =  pf[j+1] - pf[i] */\n        int pf[1001+1] = {0};\n        for(int i = 0;i < len; i++)\n            pf[i+1] = pf[i] + stones[i];\n        \n        //last turn will be (Alice\'s[0]) or (Bob\'s[1])\n        int turn = len%2 == 1;\n        \n        for(int k = 1;k < len;k++){\n            int i = 0,j = k;\n            while(i < len && j < len){\n                if(turn%2 == 0){\n                    //alice\n                    dp[i][j] = max(dp[i][j-1] + (pf[j]-pf[i]) ,\n                                   dp[i+1][j] + (pf[j+1]-pf[i+1]));\n                }    \n                else{\n                    //bob\n                    //ij\n                    dp[i][j] = min(dp[i][j-1] - (pf[j]-pf[i]) ,\n                                   dp[i+1][j] - (pf[j+1]-pf[i+1]));\n                }\n                i++;\n                j++;\n            }\n            turn = turn^1;\n        }\n        return dp[0][len-1];\n    }\n};\n```
[]