Recursion | Memoization | Tabulation ✅
_____\n\nUp Vote if Helps\n\n_____\n\n# Recursion: 1 TLE \n\nclass Solution { \n    public int stoneGameVII(int[] stones) {\n        int totalSum=0;\n        fo
______________________________________\n\n**Up Vote if Helps**![image.png](https://assets.leetcode.com/users/images/23d8443e-ac59-49d5-99f0-9273a2147be2_1687635435.0337658.png)\n\n______________________________________\n\n# Recursion: 1 *TLE* \n```\nclass Solution { \n    public int stoneGameVII(int[] stones) {\n        int totalSum=0;\n        for(int i=0; i<stones.length ; i++){\n            totalSum+=stones[i];\n        }\n        return stoneGameVII(stones,totalSum,0,stones.length-1,1);\n    }\n    public int stoneGameVII(int[] stones, int totalSum, int si, int ei, int isAlice) {\n        if(si>ei){\n            return 0;\n        }\n        if(isAlice==1){\n            int a = totalSum-stones[si] + stoneGameVII(stones,totalSum-stones[si],si+1,ei,0);\n            int b = totalSum-stones[ei] + stoneGameVII(stones,totalSum-stones[ei],si,ei-1,0);\n           return Math.max(a,b);\n        }else{        \n            int a = stoneGameVII(stones,totalSum-stones[si],si+1,ei,1) - (totalSum-stones[si]);                     \n            int b = stoneGameVII(stones,totalSum-stones[ei],si,ei-1,1) - (totalSum-stones[ei]);\n            return Math.min(a,b);\n        }\n    }    \n}\n```\n\n_________________________\n\n\n# Recursion : 2 *TLE* \n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int totalSum=0;\n        for(int i=0; i<stones.length ; i++){\n            totalSum+=stones[i];\n        }\n        return stoneGameVII(stones,totalSum,0,stones.length-1);\n    }\n    public int stoneGameVII(int[] stones, int totalSum, int si, int ei) {\n        if(si>ei || totalSum<=0){\n            return 0;\n        }\n        int a = (totalSum-stones[si])-stoneGameVII(stones,totalSum-stones[si],si+1,ei);\n        int b = (totalSum-stones[ei])-stoneGameVII(stones,totalSum-stones[ei],si,ei-1);\n        return Math.max(a,b);\n    }    \n}\n```\n\n_________________________\n\n\n\n# Memoization\n```\nclass Solution {\n    Integer[][] memo;\n    public int stoneGameVII(int[] stones) {\n        int totalSum=0;\n        for(int i=0; i<stones.length ; i++){\n            totalSum+=stones[i];\n        }\n        memo=new Integer[stones.length][stones.length];\n        return stoneGameVII(stones,totalSum,0,stones.length-1);\n    }\n    public int stoneGameVII(int[] stones, int totalSum, int si, int ei) {\n        if(si>ei || totalSum<=0){\n            return 0;\n        }\n        if(memo[si][ei]!=null){\n            return memo[si][ei];\n        }\n        int a = (totalSum-stones[si])-stoneGameVII(stones,totalSum-stones[si],si+1,ei);\n        int b = (totalSum-stones[ei])-stoneGameVII(stones,totalSum-stones[ei],si,ei-1);\n        return memo[si][ei] = Math.max(a,b);\n    }    \n}\n```\n\n_________________________\n\n# Tabulation\n```\nclass Solution {\n    public int stoneGameVII(int[] stones) {\n        int[] preSum=new int[stones.length];\n        preSum[0]=stones[0];\n        for(int i=1; i<stones.length ; i++){\n            preSum[i]=preSum[i-1]+stones[i];\n        }\n        int[][] dp=new int[stones.length][stones.length];     \n        for(int i=dp.length-1 ; i>=0 ; i--){\n            for(int j=0; j<dp[0].length ; j++){\n                if(i>=j){\n                    dp[i][j]=0;\n                }else if(i+1==j){\n                    dp[i][j]=Math.max(stones[i],stones[j]);\n                }else{\n                    int a =(preSum[j]-preSum[i])-dp[i+1][j];\n                    int b = (preSum[j-1]-(i==0 ? 0 : preSum[i-1]))-dp[i][j-1];\n                    dp[i][j] = Math.max(a,b);\n                }\n            }\n        }\n        return dp[0][dp.length-1];\n    }    \n}\n```\n\n______________________________________\n\n**Up Vote if Helps**![image.png](https://assets.leetcode.com/users/images/23d8443e-ac59-49d5-99f0-9273a2147be2_1687635435.0337658.png)\n\n______________________________________
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']