Grid DP🎯 | Top Down➡️Bottom Up | ✔️Multi Tabulation✔️ | 🔥Unique DP Approach | Clean Code🔥
\uD83D\uDE0A ~ \uD835\uDE52\uD835\uDE5E\uD835\uDE69\uD835\uDE5D \u2764\uFE0F \uD835\uDE57\uD835\uDE6E \uD835\uDE43\uD835\uDE5E\uD835\uDE67\uD835\uDE5A\uD835\uDE
\uD83D\uDE0A ~ \uD835\uDE52\uD835\uDE5E\uD835\uDE69\uD835\uDE5D \u2764\uFE0F \uD835\uDE57\uD835\uDE6E \uD835\uDE43\uD835\uDE5E\uD835\uDE67\uD835\uDE5A\uD835\uDE63\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n***Hello there! Take a look at the code and comments within it you\'ll get it.\nStill have doubts? Feel free to comment, I\'ll definitely reply!***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n***All Approach :-\n: Using Top Down (Memoization + 2D Tabulation) - TLE\n: Using Bottom Up (2D Multi Tabulation) - Accepted***\n\n# Complexity\n- ***Time complexity: Mentioned with the code***\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity: Mentioned with the code***\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n**Approach 1 : Using Top Down (Memoization + 2D Tabulation) - TLE**\n```\nclass TopDown {\n    int N, M;\n\n    // O(M*N*M + N*N*M) & O(N*M + N+M)\n    int getMaxPositiveScore(vector<vector<int>>& dp, vector<vector<int>>& grid, int startR, int startC) {\n        // Memoization table: If the current state is already computed then return the comptuted value\n        if(dp[startR][startC] != -1)\n            return dp[startR][startC];\n\n        // There are always two possibilities to perform at each cell\n        int moveRight = 0; // Is to move to any right cell \n        int moveDown  = 0; // Is to move to any bottom cell\n\n        // Explore each right cell and get the score you can get from all the possibility and then update the result by the maximum value\n        for(int C = startC+1; C < M; ++C) \n            moveRight = max(moveRight, grid[startR][C] - grid[startR][startC] + getMaxPositiveScore(dp, grid, startR, C));\n        \n        // Explore each bottom cell and get the score you can get from all the possibility and then update the result by the maximum value\n        for(int R = startR+1; R < N; ++R) \n            moveDown = max(moveDown, grid[R][startC] - grid[startR][startC] + getMaxPositiveScore(dp, grid, R, startC));\n\n        // Store the result value to the memoization table and then return it\n        return dp[startR][startC] = max(moveRight, moveDown);\n    }\n    // Note: Without memoization the time complexity of this function will be O(M^(N*M) + N^(N*M)) and the auxiliary space will be O(N+M)\n\n    // O(3*N*M) & O(2*N*M)\n    int getMaxNegativeScore(vector<vector<int>>& grid) {\n        // 2D tabulation tables\n        vector<vector<int>> maxElementRight(N, vector<int>(M, INT_MIN));\n        vector<vector<int>> maxElementDown(N, vector<int>(M, INT_MIN));\n\n        // Find the maximum element lying at the right side of each cell\n        for(int R = 0; R < N; ++R) {\n            maxElementRight[R][M-1] = grid[R][M-1];\n            for(int C = M-2; C >= 0; --C) {\n                maxElementRight[R][C] = max(grid[R][C], maxElementRight[R][C+1]);\n            }\n        }\n\n        // Find the maximum element lying at the bottom side of each cell\n        for(int C = 0; C < M; ++C) {\n            maxElementDown[N-1][C] = grid[N-1][C];\n            for(int R = N-2; R >= 0; --R) {\n                maxElementDown[R][C] = max(grid[R][C], maxElementDown[R+1][C]);\n            }\n        }\n        \n        int maxNegScore = INT_MIN;\n\n        // Move to each cell and update the maximum negative score\n        for(int R = 0; R < N; ++R) {\n            for(int C = 0; C < M; ++C) {\n                int scoreRight = (C + 1 < M) ? maxElementRight[R][C + 1] : INT_MIN;\n                int scoreDown  = (R + 1 < N) ? maxElementDown[R + 1][C] : INT_MIN;\n                if(scoreRight != INT_MIN) maxNegScore = max(maxNegScore, scoreRight - grid[R][C]);\n                if(scoreDown  != INT_MIN) maxNegScore = max(maxNegScore, scoreDown - grid[R][C]);\n            }\n        }\n        \n        return maxNegScore;\n    }\n\npublic:\n    // Method to find the maximum score you can achieve, using recursion with memoization and 2D tabulation - O(N*M*(M+N)) & O(N*M)\n    int maxScore(vector<vector<int>>& grid) {\n        N = grid.size(), M = grid[0].size();\n\n        int maxPosScore = 0;\n\n        // 2D memoization table\n        vector<vector<int>> dp(N, vector<int>(M, -1));\n\n        // Consider each cell as an unique start point and find the maximum positive score you can get from it and then update the result by the maximum value\n        for(int R = 0; R < N; ++R)\n            for(int C = 0; C < M; ++C)\n                maxPosScore = max(maxPosScore, getMaxPositiveScore(dp, grid, R, C));\n        \n        // If the maximum positive score is 0 then there is a chance that the result could be a maximum negative value hence find the maximum negative score and then return it\n        return (maxPosScore == 0) ? getMaxNegativeScore(grid) : maxPosScore;\n    }\n};\n// Note: This solution will lead to time-limit-exceed\n```\n**Approach 2 : Using Bottom Up (2D Multi Tabulation) - Accepted**\n```\nclass BottomUp {\n    int N, M;\n\n    // O(3*N*M) & O(2*N*M)\n    int getMaxNegativeScore(vector<vector<int>>& grid) {\n        // 2D tabulation tables\n        vector<vector<int>> maxElementRight(N, vector<int>(M, INT_MIN));\n        vector<vector<int>> maxElementDown(N, vector<int>(M, INT_MIN));\n\n        // Find the maximum element lying at the right side of each cell\n        for(int R = 0; R < N; ++R) {\n            maxElementRight[R][M-1] = grid[R][M-1];\n            for(int C = M-2; C >= 0; --C) {\n                maxElementRight[R][C] = max(grid[R][C], maxElementRight[R][C+1]);\n            }\n        }\n\n        // Find the maximum element lying at the bottom side of each cell\n        for(int C = 0; C < M; ++C) {\n            maxElementDown[N-1][C] = grid[N-1][C];\n            for(int R = N-2; R >= 0; --R) {\n                maxElementDown[R][C] = max(grid[R][C], maxElementDown[R+1][C]);\n            }\n        }\n        \n        int maxNegScore = INT_MIN;\n\n        // Move to each cell and update the maximum negative score\n        for(int R = 0; R < N; ++R) {\n            for(int C = 0; C < M; ++C) {\n                int scoreRight = (C+1 < M) ? maxElementRight[R][C+1] : INT_MIN;\n                int scoreDown  = (R+1 < N) ? maxElementDown[R+1][C] : INT_MIN;\n                if(scoreRight != INT_MIN) maxNegScore = max(maxNegScore, scoreRight - grid[R][C]);\n                if(scoreDown  != INT_MIN) maxNegScore = max(maxNegScore, scoreDown - grid[R][C]);\n            }\n        }\n\n        return maxNegScore;\n    }\n\npublic:\n    // Method to find the maximum score you can achieve, using 2D multi tabulation - O(N*M*(M+N)) & O(N*M)\n    int maxScore(vector<vector<int>>& grid) {\n        N = grid.size(), M = grid[0].size();\n\n        int maxPosScore = 0;\n\n        // 2D tabulation table\n        vector<vector<int>> dp(N, vector<int>(M, 0));\n\n        // Fill the table and find the maximum positive score you can get\n        for(int startR = N-1; startR >= 0; --startR) {\n            for(int startC = M-1; startC >= 0; --startC) {\n                int moveRight = 0;\n                int moveDown  = 0;\n\n                for(int C = startC+1; C < M; ++C) \n                    moveRight = max(moveRight, grid[startR][C] - grid[startR][startC] + dp[startR][C]);        \n                for(int R = startR+1; R < N; ++R) \n                    moveDown = max(moveDown, grid[R][startC] - grid[startR][startC] + dp[R][startC]);\n                \n                dp[startR][startC] = max(moveRight, moveDown);\n                maxPosScore = max(maxPosScore, dp[startR][startC]);\n            }\n        }\n\n        // If the maximum positive score is 0 then there is a chance that the result could be a maximum negative value hence find the maximum negative score and then return it\n        return (maxPosScore == 0) ? getMaxNegativeScore(grid) : maxPosScore;\n    }\n};\n```\n\uD835\uDDE8\uD835\uDDE3\uD835\uDDE9\uD835\uDDE2\uD835\uDDE7\uD835\uDDD8 \uD835\uDDDC\uD835\uDDD9 \uD835\uDDEC\uD835\uDDE2\uD835\uDDE8 \uD835\uDDDF\uD835\uDDDC\uD835\uDDDE\uD835\uDDD8 \uD835\uDDE7\uD835\uDDDB\uD835\uDDD8 \uD835\uDDE6\uD835\uDDE2\uD835\uDDDF\uD835\uDDE8\uD835\uDDE7\uD835\uDDDC\uD835\uDDE2\uD835\uDDE1 \uD83D\uDC4D
['Array', 'Dynamic Programming', 'Matrix', 'C++']