HardNo. 1301
Number of Paths with Max Score — LeetCode 1301 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Array, Dynamic Programming, Matrix
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.
Example
- Input
- board = ["E23","2X2","12S"]
- Output
- [7,1]
Python solution
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
def update(i, j, x, y):
if x >= n or y >= n or f[x][y] == -1 or board[i][j] in "XS":
return
if f[x][y] > f[i][j]:
f[i][j] = f[x][y]
g[i][j] = g[x][y]
elif f[x][y] == f[i][j]:
g[i][j] += g[x][y]
n = len(board)
f = [[-1] * n for _ in range(n)]
g = [[0] * n for _ in range(n)]
f[-1][-1], g[-1][-1] = 0, 1
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
update(i, j, i + 1, j)
update(i, j, i, j + 1)
update(i, j, i + 1, j + 1)
if f[i][j] != -1 and board[i][j].isdigit():
f[i][j] += int(board[i][j])
mod = 10**9 + 7
return [0, 0] if f[0][0] == -1 else [f[0][0], g[0][0] % mod]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1301. Number of Paths with Max Score is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
| 0085 | Maximal Rectangle | Hard |
| 0174 | Dungeon Game | Hard |
| 0221 | Maximal Square | Medium |
| 0329 | Longest Increasing Path in a Matrix | Hard |
Frequently asked questions
- How hard is LeetCode 1301. Number of Paths with Max Score?
LeetCode 1301. Number of Paths with Max Score is rated Hard on LeetCode.
- What topics does LeetCode 1301. Number of Paths with Max Score cover?
LeetCode 1301. Number of Paths with Max Score is tagged Array, Dynamic Programming and Matrix on LeetCode.