<p>You are given an <code>m x n</code> matrix <code>grid</code> consisting of <strong>positive</strong> integers. You can move from a cell in the matrix to <strong>any</strong> other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with the value <code>c1</code> to a cell with the value <code>c2</code> is <code>c2 - c1</code>.<!-- notionvc: 8819ca04-8606-4ecf-815b-fb77bc63b851 --></p>

<p>You can start at <strong>any</strong> cell, and you have to make <strong>at least</strong> one move.</p>

<p>Return the <strong>maximum</strong> total score you can achieve.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/14/grid1.png" style="width: 240px; height: 240px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">9</span></p>

<p><strong>Explanation:</strong> We start at the cell <code>(0, 1)</code>, and we perform the following moves:<br />
- Move from the cell <code>(0, 1)</code> to <code>(2, 1)</code> with a score of <code>7 - 5 = 2</code>.<br />
- Move from the cell <code>(2, 1)</code> to <code>(2, 2)</code> with a score of <code>14 - 7 = 7</code>.<br />
The total score is <code>2 + 7 = 9</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/04/08/moregridsdrawio-1.png" style="width: 180px; height: 116px;" /></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[4,3,2],[3,2,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong> We start at the cell <code>(0, 0)</code>, and we perform one move: <code>(0, 0)</code> to <code>(0, 1)</code>. The score is <code>3 - 4 = -1</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

import math
# 参考https://leetcode.cn/problems/maximum-difference-score-in-a-grid/solutions/2774823/nao-jin-ji-zhuan-wan-dppythonjavacgo-by-swux7/?envType=daily-question&envId=2024-08-15
# 这题本质就是找左上角元素中的最小值，然后算一个当前值与最小值的差；dp[i][j]表示grid[:i+1][:j+1]范围内的最小值
# 这题唯一的难点在于"至少移动一次"；因此需要先获得一次除去当前grid[i][j]的左上角范围最小值计算一下差值。
class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[math.inf] * (n+1) for _ in range(m+1)]
        ret = -math.inf
        for i in range(m):
            for j in range(n):
                t = min(dp[i-1][j], dp[i][j-1])
                ret = max(ret, grid[i][j] - t)
                dp[i][j] = min(grid[i][j], t)
        return ret

# # 这题想了挺久的；dp[i][j]记录grid[i][j]能获得的最大得分。本质上就是dp中的是否“另立山头”的问题。即当前位置是接上前面的队列还是自己作为新的队列的开头。这题来源为左侧和上方，因此总共分为四种情况：
# # 1、2:来源是上方，是接上上面还是以上面为起点另立山头；max(dp[i-1][j] + diff, diff)
# # 3、4:来源是左侧，是接上左侧韩式以左侧为起点另立山头；max(dp[i][j-1] + diff, diff)
# class Solution:
#     def maxScore(self, grid: List[List[int]]) -> int:
#         m, n = len(grid), len(grid[0])
#         dp = [[0] * n for _ in range(m)]
#         ret = -math.inf
#         for i in range(m):
#             for j in range(n):
#                 if i == j == 0:
#                     continue
#                 # dp只需要关注左侧和上方的值；以及考虑是否“另立山头”
#                 t = -math.inf
#                 if i > 0:
#                     diff = grid[i][j] - grid[i-1][j]
#                     t = max(t, dp[i-1][j] + diff, diff)
#                 if j > 0:
#                     diff = grid[i][j] - grid[i][j-1]
#                     t = max(t, dp[i][j-1] + diff, diff)
#                 dp[i][j] = t
#                 ret = max(ret, t)
#         return ret
995