Simple || DP || Tabulation 🔥🔥
Intuition\nThis is the first ever DP problem i could solved in live contest so i feel i should share to everyone\n\nIntuition was so simple we want to start fro
# Intuition\nThis is the first ever DP problem i could solved in live contest so i feel i should share to everyone\n\nIntuition was so simple we want to start from cell from where we can maximise output. after starting from one cell , we only have three choice either right or down or none of them.\n\nSo i found that storing the maximum value from bottom right corner to top left corner will be helpful to find maximum value.\n\nat each cell ,value of current cell in dp depends of max(dp[right],dp[left]) as well as difference between current cell value and either (right or bottom ) cell value.\n\noutput will be the max value of DP array.\n\n# Approach\n1. Initialization:\n\n- The dp array is initialized to store the maximum score that can be achieved starting from each cell in the grid.\n- Each cell of dp represents the maximum score achievable from that cell to the bottom-right corner of the grid.\n\n2. Traversal from Bottom-right to Top-left:\n\n- We traverse the grid in reverse order, starting from the bottom-right corner (n-1, m-1) and moving towards the top-left corner (0, 0).\n- This traversal direction allows us to compute the maximum score from each cell by considering the scores of the cells below and to the right of the current cell.\n\n3. Score Calculation:\n\n- For each cell (i, j), we calculate the potential scores of moving down (a) and moving right (b).\n- We also calculate the difference in values between the current cell and the adjacent cells (c and d), as they contribute to the score of the current move.\n- The score of moving from (i, j) to (i+1, j) is grid[i+1][j] - grid[i][j] + dp[i+1][j].\n- The score of moving from (i, j) to (i, j+1) is grid[i][j+1] - grid[i][j] + dp[i][j+1].\n- We take the maximum of these potential scores (a and b) along with the maximum difference in cell values (c and d) and assign it to dp[i][j]. This ensures that we consider the maximum score achievable from the current cell.\n\n4. Updating Maximum Score:\n\n- We update the maximum score ans by taking the maximum of the current dp[i][j] value and the existing ans.\n\n5. Return Maximum Score:\n\n- Finally, we return the maximum score ans, which represents the maximum total score achievable starting from any cell in the grid.\n\n# Complexity\n- Time complexity:\nO( N * M ) | N = number of row | M = number of column\n\n- Space complexity:\nO( N * M ) | N = number of row | M = number of column\n\n```python []\nclass Solution(object):\n    def maxScore(self, grid):\n        n = len(grid)\n        m = len(grid[0])\n        dp = []\n\n        for k in range(n+1):\n            dp.append([0 for l in range(m+1)])\n\n        ans = float(\'-inf\')\n        for i in range(n-1,-1,-1):\n            for j in range(m-1,-1,-1):\n                a, b , c , d = float(\'-inf\'), float(\'-inf\') , float(\'-inf\') ,float(\'-inf\')\n                if i+1<n:\n                    a = (grid[i+1][j]-grid[i][j]+dp[i+1][j])\n                    c = grid[i+1][j]-grid[i][j]\n                if j+1<m:\n                    b = (grid[i][j+1]-grid[i][j]+dp[i][j+1])\n                    d = grid[i][j+1]-grid[i][j]\n                \n\n                dp[i][j] = max(a,b,max(c,d))\n                ans = max(ans,dp[i][j])\n                \n        return ans\n        \n\n            \n```\n```java []\nclass Solution {\n    public int maxScore(List<List<Integer>> grid) {\n        int n = grid.size();\n        int m = grid.get(0).size();\n        int[][] dp = new int[n][m];\n        int ans = Integer.MIN_VALUE;\n        for (int i = n - 1; i >= 0; i--) {\n            for (int j = m - 1; j >= 0; j--) {\n                if (i == n - 1 && j == m - 1)\n                    continue;\n                int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE, c = Integer.MIN_VALUE, d = Integer.MIN_VALUE;\n                if (i + 1 < n) {\n                    a = (grid.get(i + 1).get(j) - grid.get(i).get(j)) + dp[i + 1][j];\n                    b = grid.get(i + 1).get(j) - grid.get(i).get(j);\n                }\n                if (j + 1 < m) {\n                    c = (grid.get(i).get(j + 1) - grid.get(i).get(j)) + dp[i][j + 1];\n                    d = grid.get(i).get(j + 1) - grid.get(i).get(j);\n                }\n                dp[i][j] = Math.max(Math.max(a, b), Math.max(c, d));\n                ans = Math.max(ans, dp[i][j]);\n            }\n\n        }\n        return ans;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        vector<vector<int>> dp(n, vector<int>(m));\n        int ans = INT_MIN;\n        for (int i = n - 1; i >= 0; i--) {\n            for (int j = m - 1; j >= 0; j--) {\n                if (i == n - 1 && j == m - 1)\n                    continue;\n                int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;\n                if (i + 1 < n) {\n                    a = (grid[i + 1][j] - grid[i][j]) + dp[i + 1][j];\n                    b = grid[i + 1][j] - grid[i][j];\n                }\n                if (j + 1 < m) {\n                    c = (grid[i][j + 1] - grid[i][j]) + dp[i][j + 1];\n                    d = grid[i][j + 1] - grid[i][j];\n                }\n                dp[i][j] = max(max(a, b), max(c, d));\n                ans = max(ans, dp[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n```\n\nhelper blog : https://leetcode.com/discuss/study-guide/1965086/How-to-practice-for-2200%2B-rating-in-LC\n\n\n\n![image.png](https://assets.leetcode.com/users/images/6fa49db8-dd0b-474f-bb47-ff447f288e21_1715493642.6429238.png)\n
['Dynamic Programming', 'Python', 'C++', 'Java']