JAVA - Journey from Brute Force to Most Optimized DP (✅)
Let\'s try to understand the problem first. \nI think that one statement of Bob always losing and trying to get minimum score difference might lead to confusion
Let\'s try to understand the problem first. \nI think that one statement of Bob always losing and trying to get minimum score difference might lead to confusion. But it is simple what it meant is that Bob wants to mininum his loss score i.e. `minimize(Alice\'s Winnings - Bob\'s Winnings)` while Alice wants this to maximize `maximize(Alice\'s Winnings - Bob\'s Winnings)`. After defining these 2 statements it is implicit that the way both play is same i.e. if Bob tries to score more he would be able to minimize the score difference. Similarly, if Alice tries score more he would be able to lead and increase the gap between his and Bob\'s winnings.\n\nLet\'s start our discussion from the most obvious thought looking at this problem. We need to try out all possible combinations and at each step we want to take out that element out of  leftmost and righmost elements that would lead to maximum score for him in future after the game is over. Let\'s start from the initial thought and on the way pick up all the optimizations as we can and reach the final accepted solution. \u2705\n\nBefore starting Iet\'s recall what the score at a given turn is. It is defined as the (`sum of all remaining elements in the array - score obtained by the opponent`).\n# **BruteForce (Time Limited Exceed)**\nIn this approach we try out the above thought and try to process both `leftmost` and `rightmost` node at each turn of the game.\n\n```\npublic int stoneGameVII(int[] stones) {\n        return playTurn(stones, 0, stones.length - 1);\n    }\n    \n\t/**\n\t\tThis method gives the sum of elements from the range [left, right] inclusive. \n\t*/\n    private int getScore(int[] stones, int left, int right) {\n        int sum = 0;\n        for(int i = left; i <= right; i++)\n            sum += stones[i];\n        \n        return sum;\n    }\n    \n    private int playTurn(int[] stones, int left, int right) {\n        if (left > right) return 0;\n        \n        int lScore = getScore(stones, left + 1, right) - playTurn(stones, left + 1, right); // if leftmost element is picked\n        int rScore = getScore(stones, left, right - 1) - playTurn(stones, left, right - 1); // if rightmost element is picked\n        \n        return Math.max(lScore, rScore);\n    }\n```\n\n*Time Complexity* - `O(2^n)` - As at each node we are making 2 recursive calls. We also have complexity of calculating the score within a window.\n\n# **Recursive + Memoization -- Top-Down DP (Accepted) 130ms \u2705**\n\nAs it might be evident that we are performing many computations again and again while their solution would remain the same. So, this calls for introducing a memory to store the already processed nodes and just provide a lookup of `O(1)`.\n\nAlso, their is an interesting take from the above solution. If we somehow reduce the amortized cost of finding the score that would be helpful as well as it would prevent so many repetitive additions. For this we have prefix sum as the rescue. At each node we would store the sum of elements starting from index 0 to the current element(both inclusive). So, to calculate a sum of a window we subtract cummulative sum(CS) of lower index bound from the CS of upper index bound.\n\n```\nprivate int[] preSum;\n    private Integer[][] mem;\n    \n    public int stoneGameVII(int[] stones) {\n        int size = stones.length;\n        preSum = new int[size + 1];\n        mem = new Integer[size][size];\n        \n        for(int i = 0; i < size; i++) // Calculating prefix sum\n            preSum[i + 1] = preSum[i] + stones[i];\n        \n        return playTurn(stones, 0, size - 1);\n    }\n    \n    private int getScore(int left, int right) {\n        return preSum[right + 1] - preSum[left];\n    }\n    \n    private int playTurn(int[] stones, int left, int right) {\n        if (left > right) return 0;\n        \n        if(mem[left][right] != null) return mem[left][right];\n        \n        int lScore = getScore(left + 1, right) - playTurn(stones, left + 1, right);\n        int rScore = getScore(left, right - 1) - playTurn(stones, left, right - 1);\n        \n        mem[left][right] = Math.max(lScore, rScore);\n        \n        return mem[left][right];\n    }\n```\n\n*Time Complexity* - `O(n*n)` - As we have lookup which is preventing repetitive calculations. \n\n# **Bottom Up DP - Space Optimized (Accepted) 27ms \u2705**\nLet\' try to tackle this problem from a different perspective. Let\'s try solving the problem starting with one element and slowly build up the final solution. Let\'s try to understand with an example and try to find the sub problems that can help find the overall solution.\n\n![image](https://assets.leetcode.com/users/images/16aac07e-0eba-4dcc-8875-03e8fc06f4df_1623433957.0765543.png)\n\n\nAs we can see in the above image, when we have 3 elements the solution for that involves the solution when we had 2 elements. So, if we can leverage this pattern and try to find the solutions for sub-problems by linearly increasing the length of the array we can array at the final solution. \n\nDid we observe that? ..... let\'s try to find one more thing before scrolling down ...... it\'s would be interesting to juggle our brain horses.\n\nYes!! We observe that for a given length `L` we only need to look back at the `L - 1` which would already contain solution of the internal recursive solutions of decrement in lengths. So, as solution of `Length 2` would have already have optimum score using scores of `Length 1`. In that case when we move to `Length 3` we only need to look back at `Length 2` results. \nThis means we only need a `1-D array` to store the previous solutions.\n\nLet\'s look at the code and see if we get it. Even if there is any confusion, don\'y worry we would discuss the subtle interesting points in the solution.\n\n```\nprivate int[] preSum;\n    private int[] dp;\n    \n    public int stoneGameVII(int[] stones) {\n        int size = stones.length;\n        preSum = new int[size + 1];\n        dp = new int[size + 1];\n        \n        for(int i = 0; i < size; i++)\n            preSum[i + 1] = preSum[i] + stones[i];\n        \n        for(int end = 1; end <= size; end++) {\n            for(int i = 0; i < size - end; i++) {\n                dp[i] = Math.max(\n                    getScore(i + 1, i + end) - dp[i + 1], // As if we pick i, we need to find solution of (i+1, end).\n                    getScore(i, i + end - 1) - dp[i] // As if we pick end, we need to find solution of (i, end - 1)\n                ); \n            }\n        }\n        \n        return dp[0];\n    }\n    \n    private int getScore(int left, int right) {\n        return preSum[right + 1] - preSum[left];\n    }\n```\n\nOnly thing that might have caused a confusion is the assignment of `dp[i]` which is below snippet.\n\n```\ndp[i] = Math.max(\n                    getScore(i + 1, i + end) - dp[i + 1],\n                    getScore(i, i + end - 1) - dp[i]\n                ); \n```\n\nSo, basically  `dp[i + 1]` for a given `end` and interval length `L` would mean score when `i + 1` is the start node and we have `L - 1`  elements.This is what we need to add when the `i` element is picked. Remember our thinking that we need only the `L-1` length solution.\nSimilarly, `dp[i]` at that same very `end` and length `L`  would mean that we picked `end` element and we need to find the solution for `L-1` elements where ending node was `end-1`.\n\n*Time Complexity* - `O(n*n)` - If we carefully look at the loops it would run for partial matrix and not exactly the full matrix. \n\nAlso, we improved so much on the space size from `O(n*n)` -> `O(n)`.\n\nHope that helps!! In case of any improvement or corrections please comment below. Thanks!!
['Dynamic Programming', 'Java']