The "Number of Paths with Max Score" problem gives you a square board represented as a list of strings, where each cell is one of the following:
You can only move up, left, or up-left diagonally at each step. Your goal is to find:
Return an array [maxScore, numPaths], where maxScore is the largest possible sum, and numPaths is the number of such paths modulo 109+7. If there is no valid path, return [0, 0].
You must not step on obstacles, and you cannot revisit cells.
Constraints:
1 <= n <= 100To solve this problem, let's start by thinking about brute force: we could try every possible path from 'S' to 'E', summing scores and counting the max. But with up to 100x100 cells, the number of paths grows exponentially—making brute-force infeasible.
Instead, we notice that this problem fits the pattern of dynamic programming. At each cell, the best score and number of ways to get there depends only on the best results from the three possible previous cells (down, right, or down-right from the perspective of the board, since we are moving up, left, or up-left). This means we can build up a solution by filling in a DP table, reusing results for efficiency.
The main challenge is to keep track of both the maximum score and the number of ways to achieve it at each cell. At obstacles, we store zeroes. For other cells, we look at the three possible moves and combine their results, always taking care to handle ties in max score.
We'll use a 2D dynamic programming table, where each cell dp[i][j] stores a pair: (maxScore, numWays) to reach that cell from the start.
(-1, 0) everywhere, except for the starting cell 'S' (bottom-right), which is (0, 1) because you start with score 0 and 1 way.dp[0][0] (top-left, 'E'). If no path exists, return [0, 0].
We use modulo 10^9 + 7 for the path count to avoid overflow.
Let's consider this board:
["E23",
"2X2",
"12S"]
So the output is [7, 1].
The "Number of Paths with Max Score" problem is a classic dynamic programming challenge. By breaking the problem into subproblems—tracking the max score and number of ways at each cell—we avoid redundant calculations and efficiently find the result. The solution elegantly combines path counting and score maximization by leveraging a 2D DP table and careful state updates.
class Solution:
def pathsWithMaxScore(self, board):
n = len(board)
MOD = 10**9 + 7
dp = [[(-1, 0) for _ in range(n)] for _ in range(n)]
dp[n-1][n-1] = (0, 1)
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if board[i][j] == 'X' or (i == n-1 and j == n-1):
continue
maxScore = -1
ways = 0
for dx, dy in [(1,0), (0,1), (1,1)]:
ni, nj = i+dx, j+dy
if 0 <= ni < n and 0 <= nj < n:
prevScore, prevWays = dp[ni][nj]
if prevWays == 0:
continue
val = 0 if board[i][j] in 'SE' else int(board[i][j])
currScore = prevScore + val
if currScore > maxScore:
maxScore = currScore
ways = prevWays
elif currScore == maxScore:
ways = (ways + prevWays) % MOD
if maxScore != -1:
dp[i][j] = (maxScore, ways % MOD)
result = dp[0][0]
return [result[0], result[1]] if result[1] != 0 else [0,0]
class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size(), MOD = 1e9+7;
vector<vector<pair<int,int>>> dp(n, vector<pair<int,int>>(n, {-1, 0}));
dp[n-1][n-1] = {0, 1};
for (int i = n-1; i >= 0; --i) {
for (int j = n-1; j >= 0; --j) {
if (board[i][j] == 'X' || (i == n-1 && j == n-1)) continue;
int maxScore = -1, ways = 0;
for (auto d : vector<pair<int,int>>{{1,0},{0,1},{1,1}}) {
int ni = i + d.first, nj = j + d.second;
if (ni < n && nj < n && dp[ni][nj].second > 0) {
int val = (board[i][j] == 'S' || board[i][j] == 'E') ? 0 : board[i][j] - '0';
int currScore = dp[ni][nj].first + val;
if (currScore > maxScore) {
maxScore = currScore;
ways = dp[ni][nj].second;
} else if (currScore == maxScore) {
ways = (ways + dp[ni][nj].second) % MOD;
}
}
}
if (maxScore != -1)
dp[i][j] = {maxScore, ways};
}
}
auto res = dp[0][0];
if (res.second == 0) return {0,0};
return {res.first, res.second};
}
};
class Solution {
public int[] pathsWithMaxScore(List<String> board) {
int n = board.size(), MOD = 1000000007;
int[][][] dp = new int[n][n][2];
for (int[][] arr : dp) for (int[] a : arr) java.util.Arrays.fill(a, -1);
dp[n-1][n-1][0] = 0;
dp[n-1][n-1][1] = 1;
for (int i = n-1; i >= 0; --i) {
for (int j = n-1; j >= 0; --j) {
if (board.get(i).charAt(j) == 'X' || (i == n-1 && j == n-1)) continue;
int maxScore = -1, ways = 0;
int[][] dirs = {{1,0},{0,1},{1,1}};
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni < n && nj < n && dp[ni][nj][1] > 0) {
int val = (board.get(i).charAt(j) == 'S' || board.get(i).charAt(j) == 'E') ? 0 : board.get(i).charAt(j) - '0';
int currScore = dp[ni][nj][0] + val;
if (currScore > maxScore) {
maxScore = currScore;
ways = dp[ni][nj][1];
} else if (currScore == maxScore) {
ways = (ways + dp[ni][nj][1]) % MOD;
}
}
}
if (maxScore != -1) {
dp[i][j][0] = maxScore;
dp[i][j][1] = ways;
}
}
}
if (dp[0][0][1] == 0) return new int[]{0,0};
return new int[]{dp[0][0][0], dp[0][0][1]};
}
}
var pathsWithMaxScore = function(board) {
const n = board.length, MOD = 1e9+7;
const dp = Array.from({length: n}, () => Array.from({length: n}, () => [-1, 0]));
dp[n-1][n-1] = [0, 1];
for (let i = n-1; i >= 0; --i) {
for (let j = n-1; j >= 0; --j) {
if (board[i][j] === 'X' || (i === n-1 && j === n-1)) continue;
let maxScore = -1, ways = 0;
for (const [dx, dy] of [[1,0],[0,1],[1,1]]) {
const ni = i + dx, nj = j + dy;
if (ni < n && nj < n && dp[ni][nj][1] > 0) {
const val = (board[i][j] === 'S' || board[i][j] === 'E') ? 0 : Number(board[i][j]);
const currScore = dp[ni][nj][0] + val;
if (currScore > maxScore) {
maxScore = currScore;
ways = dp[ni][nj][1];
} else if (currScore === maxScore) {
ways = (ways + dp[ni][nj][1]) % MOD;
}
}
}
if (maxScore !== -1)
dp[i][j] = [maxScore, ways];
}
}
const [maxScore, ways] = dp[0][0];
return ways === 0 ? [0,0] : [maxScore, ways];
};