Given a grid of points, choose one cell from each row to maximize the total score. Moving from column c1 in one row to column c2 in the next row incurs a penalty of abs(c1 - c2). Pattern focus: Grid Min Max Path DP. The best transition comes from maintaining the strongest values while accounting for movement cost.
points is a non-empty grid of scores
maximum total points
Example 1:
Input:
points = [[1,2,3],[1,5,1],[3,1,1]]
Output:
9
Explanation:
The maximum points collectible are 9.
Example 2:
Input:
points = [[2,2],[3,3],[1,5]]
Output:
10
Explanation:
The best score is 10.
Example 3:
Input:
points = [[1]]
Output:
1
Explanation:
A single row-and-column grid returns 1.