3986. Maximum Path Score in a Grid
My accepted Python solution to LeetCode problem 3986, Maximum Path Score in a Grid, running in 2640ms.
- Difficulty: Medium
- Python
- Runtime 2640ms
- Memory 42.1MB
- 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 2640ms, memory 42.1MB, accepted 2025-12-30.
class Solution:
def maxPathScore(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
# Path has m + n - 1 cells, starting cell has cost 0
# So max cost is m + n - 2
max_cost = min(k, m + n - 2)
INF = float('inf')
# dp[c] = dict mapping (i,j) -> max score to reach (i,j) with cost c
# Use different approach: for each cell, track (cost -> max_score)
dp = [[{} for _ in range(n)] for _ in range(m)]
dp[0][0][0] = 0 # start at (0,0) with cost 0, score 0
def get_score_cost(val):
if val == 0:
return (0, 0)
elif val == 1:
return (1, 1)
else:
return (2, 1)
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
score_add, cost_add = get_score_cost(grid[i][j])
new_dp = {}
# From top
if i > 0:
for prev_cost, prev_score in dp[i-1][j].items():
new_cost = prev_cost + cost_add
if new_cost <= max_cost:
new_score = prev_score + score_add
if new_cost not in new_dp or new_dp[new_cost] < new_score:
new_dp[new_cost] = new_score
# From left
if j > 0:
for prev_cost, prev_score in dp[i][j-1].items():
new_cost = prev_cost + cost_add
if new_cost <= max_cost:
new_score = prev_score + score_add
if new_cost not in new_dp or new_dp[new_cost] < new_score:
new_dp[new_cost] = new_score
dp[i][j] = new_dp
result = -1
for cost, score in dp[m-1][n-1].items():
if cost <= k:
result = max(result, score)
return result