Easy Code Explantion in Java. From- Recursion, Memoization, 2D(n*n) DP to 1D(n) DP
Anybody who have chance can pick from the starting or the ending. So, the maximum differentce Alice can achieve is by picking the 1st stone or last stone. We ne
Anybody who have chance can pick from the starting or the ending. So, the maximum differentce Alice can achieve is by picking the 1st stone or last stone. We need to consider both of the cases and we\'ll choose the maximum difference that Alice can get from the two choices.\nWe\'ll be adding current sum of the array (sum) - the element which is discarded(start or end) from consideration as the current score of the player.\nAnd then using the remaining array as the new array to further problems\n\n--RECURSION--\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int n = stones.length;\n        int sum = 0;\n        for (int i=0; i<n; i++)\n            sum += stones[i];\n        return helper(stones, 0, n-1, sum);\n    }\n    public int helper(int[] stones, int start, int end, int sum) {\n        if(start>=end)\n            return 0;\n        int a = sum - stones[end];\n        int b = sum - stones[start];\n        return Math.max(a-helper(stones, start, end-1, a),\n                        b-helper(stones, start+1, end, b));\n    }\n}\n```\n--MEMOIZATION--\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int n = stones.length;\n        int[][] dp = new int[n][n];\n        for(int[] row: dp)\n            Arrays.fill(row, -1);\n        int sum = 0;\n        for (int i=0; i<n; i++)\n            sum += stones[i];\n        return helper(stones, 0, n-1, dp, sum);\n    }\n    public int helper(int[] stones, int start, int end, int[][] dp, int sum) {\n        if(start>=end)\n            return 0;\n        if(dp[start][end]!=-1)\n            return dp[start][end];\n        int a = sum - stones[end];\n        int b = sum - stones[start];\n        return dp[start][end] = Math.max(a-helper(stones, start, end-1, dp, a),\n                                         b-helper(stones, start+1, end, dp, b));\n    }\n}\n```\n\n--DYNAMIC PROGRAMMING USING 2D--\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int n = stones.length;\n        int[][] dp = new int[n][n];\n        for(int i = n-1; i>=0; i--) {\n            int sum = stones[i];\n            for(int j = i; j<n; j++) {\n                if(i==j)\n                    dp[i][j] = 0;\n                else{\n                    sum += stones[j];\n                    int a = sum - stones[j];\n                    int b = sum - stones[i];\n                    dp[i][j] = Math.max(a-dp[i][j-1], b-dp[i+1][j]);\n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n}\n```\n\n--DYNAMIC PROGRAMMING USING 1D DP--\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int n = stones.length;\n        int[] dp = new int[n];\n        for(int i = n-1; i>=0; i--) {\n            int prev = 0;\n            int sum = stones[i];\n            for (int j=i; j<n; j++) {\n                if(i==j)\n                    dp[j] = 0;\n                else {\n                    sum += stones[j];\n                    int a = sum - stones[j];\n                    int b = sum - stones[i];\n                    dp[j] = Math.max(a-prev, b-dp[j]);\n                }\n                prev = dp[j];\n            } \n        }\n        return dp[n-1];\n    }\n}\n```\n
[]