Java DP matrix
Intuition\nThe approach is to utilize dynamic programming to compute the maximum score that can be achieved by reaching each cell of the grid.\n# Approach\nInit
# Intuition\nThe approach is to utilize dynamic programming to compute the maximum score that can be achieved by reaching each cell of the grid.\n# Approach\nInitialize a 2D array dp to store the maximum score that can be achieved at each cell.\nStart from the bottom-right corner of the grid and iteratively fill the dp array by considering the maximum score achievable by moving either downward or rightward from the current cell, or by choosing the current cell itself.\nAfter filling the dp array, iterate through each cell again to find the maximum difference between the current cell\'s value and the maximum score achievable from adjacent cells. This represents the maximum score that can be gained by choosing the current cell and then moving forward.\nReturn the maximum score found.\n# Complexity\n- Time complexity:\nO(m * n)\n- Space complexity:\nO(m * n)\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    public int maxScore(List<List<Integer>> grid) {\n        int m = grid.size();\n        int n = grid.get(0).size();\n        \n        int[][] dp = new int[m][n];\n        for (int[] row : dp) {\n            Arrays.fill(row, Integer.MIN_VALUE);\n        }\n        \n        dp[m - 1][n - 1] = grid.get(m - 1).get(n - 1);\n        \n        for (int i = m - 1; i >= 0; --i) {\n            for (int j = n - 1; j >= 0; --j) {\n                if (i < m - 1)\n                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j]);\n                if (j < n - 1)\n                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1]);\n                dp[i][j] = Math.max(dp[i][j], grid.get(i).get(j));\n            }\n        }\n        \n        int Max = Integer.MIN_VALUE;\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i < m - 1)\n                    Max = Math.max(Max, dp[i + 1][j] - grid.get(i).get(j));\n                if (j < n - 1)\n                    Max = Math.max(Max, dp[i][j + 1] - grid.get(i).get(j));\n                \n            }\n        }\n        return Max;\n    }\n}\n\n```
['Java']