#1937
Maximum Number of Points with Cost
specialist · 985 · lc medium +32 · verified · 41.8% accepted · 3,258 likes · top 22%
Description
You are given a 0-indexed m x n integer matrix points. Gain points by choosing one cell per row. Picking cell (r, c) earns points[r][c], but transitioning from column c1 in row r to column c2 in row r + 1 deducts abs(c1 - c2) points.
Return the maximum total score achievable.
Example 1:
Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.
Example 2:
Input: points = [[1,5],[2,3],[4,2]]
Output: 11
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.
Code
1
2
3