1301. Number of Paths with Max Score

Array
Dynamic Programming
Matrix

TIME

O(n^2)

SPACE

O(n^2)

Intuition

Moves are up / left / up-left, so travelling from S (bottom-right) to E (top-left) always decreases a coordinate. That makes it a clean grid DP: a cell (i, j) can only be entered from (i+1, j), (i, j+1), or (i+1, j+1) the three cells "below/right" of it. We want both the maximum collectable sum and how many distinct paths hit that maximum.

Approach

Two grids, filled with i and j decreasing (so predecessors are computed first):

best[i][j] max sum to reach (i, j) from S (−∞ if unreachable).
cnt[i][j] number of paths achieving best[i][j], modulo 1e9 + 7.

Base: best[S] = 0, cnt[S] = 1.

For every other non-X cell, look at the three predecessors, take the maximum reachable best, and:

best[i][j] = maxPred + value(i, j) (value is 0 for E, digit otherwise),
cnt[i][j] = sum of cnt over predecessors that attain that maximum.

If no predecessor is reachable (and the cell isn't S), the cell stays unreachable.

Answer: [best[0][0], cnt[0][0]] if E is reachable, else [0, 0].

Complexity

Time: O(n²)
Space: O(n²), the two DP grids

Edge Cases

E unreachable (walled off by X) → [0, 0]
S or E cells count as value 0 (don't add to the sum)
Multiple predecessors tie on max sum → counts add (mod)
Diagonal move allowed only onto a non-obstacle cell (handled by skipping X)
Even the sum must be taken from a real path, an unreachable E returns [0,0], not [0, 1]

Code

from typing import List


class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        """
        1301. Number of Paths with Max Score
        Time: O(n^2)
        Space: O(n^2)
        """
        MOD = 10**9 + 7
        n = len(board)
        NEG = float("-inf")

        best = [[NEG] * n for _ in range(n)]
        cnt = [[0] * n for _ in range(n)]
        best[n - 1][n - 1] = 0  # start at 'S'
        cnt[n - 1][n - 1] = 1

        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                ch = board[i][j]
                if ch == "X" or (i == n - 1 and j == n - 1):
                    continue
                if ch == "S":
                    continue
                # gather best over the three predecessors
                bmax = NEG
                for pi, pj in ((i + 1, j), (i, j + 1), (i + 1, j + 1)):
                    if pi < n and pj < n and best[pi][pj] > bmax:
                        bmax = best[pi][pj]
                if bmax == NEG:
                    continue  # unreachable
                ways = 0
                for pi, pj in ((i + 1, j), (i, j + 1), (i + 1, j + 1)):
                    if pi < n and pj < n and best[pi][pj] == bmax:
                        ways = (ways + cnt[pi][pj]) % MOD
                val = 0 if ch == "E" else int(ch)
                best[i][j] = bmax + val
                cnt[i][j] = ways

        if best[0][0] == NEG:
            return [0, 0]
        return [best[0][0], cnt[0][0] % MOD]

import java.util.List;

/**
 * 1301. Number of Paths with Max Score
 * Time: O(n^2)
 * Space: O(n^2)
 */
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int NEG = Integer.MIN_VALUE;

    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        int[][] best = new int[n][n];
        long[][] cnt = new long[n][n];
        for (int[] row : best) {
            java.util.Arrays.fill(row, NEG);
        }
        best[n - 1][n - 1] = 0; // start at 'S'
        cnt[n - 1][n - 1] = 1;

        int[][] preds = {{1, 0}, {0, 1}, {1, 1}};
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                char ch = board.get(i).charAt(j);
                if (ch == 'X' || (i == n - 1 && j == n - 1) || ch == 'S') {
                    continue;
                }
                int bmax = NEG;
                for (int[] d : preds) {
                    int pi = i + d[0], pj = j + d[1];
                    if (pi < n && pj < n && best[pi][pj] > bmax) {
                        bmax = best[pi][pj];
                    }
                }
                if (bmax == NEG) {
                    continue; // unreachable
                }
                long ways = 0;
                for (int[] d : preds) {
                    int pi = i + d[0], pj = j + d[1];
                    if (pi < n && pj < n && best[pi][pj] == bmax) {
                        ways = (ways + cnt[pi][pj]) % MOD;
                    }
                }
                int val = (ch == 'E') ? 0 : ch - '0';
                best[i][j] = bmax + val;
                cnt[i][j] = ways;
            }
        }

        if (best[0][0] == NEG) {
            return new int[]{0, 0};
        }
        return new int[]{best[0][0], (int) (cnt[0][0] % MOD)};
    }
}