3563. Select Cells in Grid With Maximum Score
My accepted Python solution to LeetCode problem 3563, Select Cells in Grid With Maximum Score, running in 344ms.
- Difficulty: Hard
- Python
- Runtime 344ms
- Memory 89.2MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 344ms, memory 89.2MB, accepted 2025-12-29.
class Solution:
def maxScore(self, grid: List[List[int]]) -> int:
from functools import lru_cache
m = len(grid)
# Map each value to the rows it appears in
value_to_rows = {}
for i in range(m):
for val in grid[i]:
if val not in value_to_rows:
value_to_rows[val] = set()
value_to_rows[val].add(i)
# Sort values in descending order for greedy processing
values = sorted(value_to_rows.keys(), reverse=True)
n = len(values)
@lru_cache(maxsize=None)
def dp(idx, used_rows):
if idx == n:
return 0
# Option 1: Don't use this value
result = dp(idx + 1, used_rows)
# Option 2: Use this value from one of available rows
val = values[idx]
for row in value_to_rows[val]:
if not (used_rows & (1 << row)):
new_used = used_rows | (1 << row)
result = max(result, val + dp(idx + 1, new_used))
return result
return dp(0, 0)