DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: o(m*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(m*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def maxScore(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        m,n = len(grid), len(grid[0])\n\n        dp = [[-float(\'inf\')] * n for _ in range(m)]\n\n        res = -float(\'inf\')\n\n        for j in range(1, n):\n            dp[0][j] = max(dp[0][j-1] + grid[0][j] - grid[0][j-1], grid[0][j] - grid[0][j-1])\n            res = max(res, dp[0][j])\n        \n        for i in range(1, m):\n            dp[i][0] = max(grid[i][0] - grid[i-1][0] + dp[i-1][0], grid[i][0] - grid[i-1][0])\n            res = max(res, dp[i][0])\n\n        for i in range(1, m):\n            for j in range(1, n):\n                dp[i][j] = max(dp[i-1][j] + grid[i][j]-grid[i-1][j], grid[i][j]-grid[i-1][j])\n                dp[i][j] = max(dp[i][j], dp[i][j-1]+grid[i][j]-grid[i][j-1], grid[i][j]-grid[i][j-1])\n                res = max(res, dp[i][j])\n        return res if res != -float("inf") else -1\n\n```
['Python']