[Python] Simple DP without math, O(MN)
Key Ideas\n- Fill DP array up from bottom right to top left.\n- When we iterate over cell (i, j), we compute the highest scoring path starting from (i, j) with 
### Key Ideas\n- Fill DP array up from bottom right to top left.\n- When we iterate over cell `(i, j)`, we compute the highest scoring path starting from `(i, j)` with **at least 1 move**.\n- The requirement of paths being at least 1 move long make this problem tricky.\n\nIgnoring any bounds checks, the recurrence + calculation of the answer looks like this:\n\nAt this step,\n\n`dp[i][j] = maximum score starting from cell (i, j)`\n\n`dp[i][j] = max(dp[i][j + 1], dp[i + 1][j]) - grid[i][j]`\n\nThe term "`max(dp[i][j + 1], dp[i + 1][j])`" represents the maximum score in the black rectangle. We can compute that maximum using the scores from the blue and red rectangles. Since we are building the DP array from bottom right to top left, when we compute `dp[i][j]`, we will already know `dp[i + 1][j]` (red) and `dp[i][j + 1]` (blue). \n<img src="https://assets.leetcode.com/users/images/8bb6a9ba-26a7-4654-818d-c59a9e795526_1715530756.027575.png" width="500"/>\n\nNow, we can update our answer: `answer = max(dp[i][j], answer)`.\n\nCurrently, `dp[i][j]` is the max score for all paths starting from cell `(i, j)` and making at least 1 more move. In the future, when we reuse this result when computing the answer for another starting cell, we might not consider paths that end with cell `(i, j)`. \n\nThat\'s why we need this line:\n\n`dp[i][j] = max(dp[i][j], 0) + grid[i][j]`\n\nThe trick here is interspersing updating `answer` with computing `dp[i][j]` so we consider all paths with at least 1 move.\n\n```\ndef maxScore(self, grid: List[List[int]]) -> int:        \n        N, M = len(grid), len(grid[0])\n        dp = [[-10**9] * M for _ in range(N)]\n        answer = -10**9\n        for i in range(N - 1, -1, -1):\n            for j in range(M - 1, -1, -1):\n                if j + 1 < M:\n                    dp[i][j] = max(dp[i][j], dp[i][j + 1] - grid[i][j])\n                    \n                if i + 1 < N:\n                    dp[i][j] = max(dp[i][j], dp[i + 1][j] - grid[i][j])\n                    \n                answer = max(dp[i][j], answer)\n                dp[i][j] = max(dp[i][j], 0) + grid[i][j]\n        \n        return answer\n```
['Python']