Problem Statement in English

You’re given a square board of characters. You can move on the board starting at the bottom right square marked with the character ‘S’. You need to move to the top left square marked with the character ‘E’. The rest of the squares are labeled either with a numeric character 1-9 or with an obstacle ‘X’. You cannot move onto obstacles. You can only move up, left, or diagonally up and left.

Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect on your path from ‘S’ to ‘E’, and the second integer is the number of such paths that you can take to get that maximum sum. Since the answer can be large, return it modulo $10^9 + 7$.

Approach

This problem can be solved using dynamic programming. We can define a recursive function that calculates the maximum score and the number of paths to reach each cell in the board. We will use memoization to store the results of previously computed cells to avoid redundant calculations.

At each cell, we will check the three possible directions (up, left, and diagonally up-left) and compute the maximum score and the number of paths from those directions. If a cell is an obstacle or out of bounds, we will skip it.

For each cell we visit, we check if it can actually reach the end ‘E’. If it can, we update the maximum score and the number of paths accordingly. Finally, we return the maximum score and the number of paths from the starting cell ‘S’.

And we’re done!

Solution in Python


class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        M, N = len(board), len(board[0])
        MOD = 10 ** 9 + 7
        directions = [(0, -1), (-1, 0), (-1, -1)]

        @cache
        def dp(i, j):
            # Base Case: Reached the end successfully
            if board[i][j] == "E":
                return [0, 1]  # [score, paths]

            best_score = -float('inf')
            best_paths = 0

            # Check all 3 movements
            for dx, dy in directions:
                nx, ny = i + dx, j + dy
                
                # Out of bounds or obstacle
                if not (0 <= nx < M and 0 <= ny < N) or board[nx][ny] == "X":
                    continue
                
                next_score, next_paths = dp(nx, ny)
                
                # If the next square can actually reach 'E'
                if next_score != -float('inf'):
                    if next_score > best_score:
                        best_score = next_score
                        best_paths = next_paths
                    elif next_score == best_score:
                        best_paths = (best_paths + next_paths) % MOD

            # If no valid paths could reach 'E' from here
            if best_score == -float('inf'):
                return [-float('inf'), 0]

            # Add current square's value (0 for 'S')
            current_val = 0 if board[i][j] == "S" else int(board[i][j])
            
            return [best_score + current_val, best_paths]

        ans_score, ans_paths = dp(M - 1, N - 1)
        
        # If 'E' is unreachable from 'S'
        if ans_score == -float('inf'):
            return [0, 0]
            
        return [ans_score, ans_paths]

Complexity

  • Time: $O(M \times N)$
    Since we iterate over all cells in the board once.

  • Space: $O(M \times N)$
    Since we iterate over all cells in the board once.

Mistakes I Made

I overcomplicated the implementation.

And we are done.