# Number of Paths with Max Score **Difficulty:** HARD [External](https://leetcode.com/problems/number-of-paths-with-max-score) Canonical: https://scaleengineer.com/dsa/problems/number-of-paths-with-max-score **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** Array, Matrix **Companies:** [Samsung](https://scaleengineer.com/companies/samsung) --- ## 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'`. You need to reach the top left square marked with the character `'E'`. The rest of the squares are labeled either with a numeric character `1, 2, ..., 9` or with an obstacle `'X'`. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there. Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, **taken modulo `10^9 + 7`**. In case there is no path, return `[0, 0]`. **Example 1:** **Input:** board = ["E23","2X2","12S"] **Output:** [7,1] **Example 2:** **Input:** board = ["E12","1X1","21S"] **Output:** [4,2] **Example 3:** **Input:** board = ["E11","XXX","11S"] **Output:** [0,0] **Constraints:** * `2 <= board.length == board[i].length <= 100` # Approaches ## Brute-Force Recursion (DFS) This approach uses a simple recursive function to explore all possible paths from the starting square 'S' to the ending square 'E'. For each path, it calculates the sum of collected numbers. It then finds the maximum sum among all valid paths and counts how many paths achieve this maximum sum. **Time:** O(3^(N^2)). In the worst-case scenario without obstacles, each cell exploration branches into three recursive calls, leading to an exponential number of path explorations. · **Space:** O(N^2), where N is the dimension of the board. This is due to the maximum depth of the recursion stack. **Pros:** Conceptually simple and a direct translation of the problem statement. **Cons:** Extremely inefficient due to a massive number of redundant computations for the same cells.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints. ### Explanation We define a recursive function, say `dfs(row, col)`, which represents the problem of finding the max score and path count starting from cell `(row, col)` to the destination 'E' at `(0, 0)`. The base case for the recursion is when we reach the destination 'E'. In the recursive step, from the current cell `(row, col)`, we can move up, left, or diagonally up-left. We make recursive calls for these three neighbors. We then compare the maximum scores returned by these three recursive calls. The best score from the current cell will be the maximum of these scores plus the value of the current cell. The number of paths for the current cell is the sum of the path counts from the neighbors that yield the maximum score. The initial call would be `dfs(n-1, n-1)`. This approach is inefficient because it recomputes the results for the same cells multiple times, leading to an exponential number of calls. ### Algorithm - Define a recursive function `dfs(row, col)` that returns `[max_score, path_count]` for paths from `(row, col)` to `E(0, 0)`. - **Base Case 1 (Invalid Path):** If `(row, col)` is out of bounds or an obstacle 'X', return `[-1, 0]` to signify an impossible path. - **Base Case 2 (Destination):** If `(row, col)` is `(0, 0)` (the 'E' square), return `[0, 1]`. The score collected at 'E' is 0, and we've found one path. - **Recursive Step:** From the current cell `(row, col)`, make recursive calls for the three possible moves towards 'E': `up = dfs(row-1, col)`, `left = dfs(row, col-1)`, and `diag = dfs(row-1, col-1)`. - **Combine Results:** - Find the maximum score (`max_next_score`) among the results from the three recursive calls. - If `max_next_score` is -1, it means 'E' is unreachable from this cell, so return `[-1, 0]`. - Calculate the total score from the current cell: `(value of board[row][col]) + max_next_score`. The value is 0 for 'S' and 'E'. - Sum the path counts from all neighbors that contributed to `max_next_score`. Apply modulo arithmetic to the sum. - **Initial Call:** Start the process by calling `dfs(n-1, n-1)`. ## Recursion with Memoization (Top-Down DP) This approach improves upon the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use a cache (e.g., a 2D array) to store the results of `dfs(row, col)` once they are computed, effectively trading space for a significant improvement in time. **Time:** O(N^2). Each state `(row, col)` is computed exactly once. The work for each state is constant. · **Space:** O(N^2), for the memoization table and the recursion stack. **Pros:** Drastically more efficient than brute-force, with a polynomial time complexity.; Maintains the recursive structure which can be intuitive to some. **Cons:** Uses O(N^2) space for both the memoization table and the recursion stack.; May cause a stack overflow for very large N, though unlikely with the given constraints. ### Explanation The core logic is the same as the brute-force recursive approach, but we introduce a memoization table, `memo[N][N]`, where `memo[row][col]` will store the pair `[max_score, path_count]` for the subproblem starting at `(row, col)`. Before computing the result for `dfs(row, col)`, we first check if `memo[row][col]` already contains a valid result. If it does, we return the cached value immediately. Otherwise, we perform the computation and store the result in `memo[row][col]` before returning. This technique, also known as top-down dynamic programming, ensures that each subproblem is solved only once. ```java class Solution { int MOD = 1_000_000_007; int[][][] memo; List board; int n; public int[] pathsWithMaxScore(List board) { this.n = board.size(); this.board = board; this.memo = new int[n][n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { memo[i][j][0] = -1; // Using -1 to mark as uncomputed } } int[] result = dfs(n - 1, n - 1); return result[0] == -1 ? new int[]{0, 0} : result; } private int[] dfs(int r, int c) { if (r < 0 || c < 0 || board.get(r).charAt(c) == 'X') { return new int[]{-1, 0}; } if (r == 0 && c == 0) { return new int[]{0, 1}; } if (memo[r][c][0] != -1) { return memo[r][c]; } int[] resUp = dfs(r - 1, c); int[] resLeft = dfs(r, c - 1); int[] resDiag = dfs(r - 1, c - 1); int maxScore = Math.max(resUp[0], Math.max(resLeft[0], resDiag[0])); if (maxScore == -1) { return memo[r][c] = new int[]{-1, 0}; } int pathCount = 0; if (resUp[0] == maxScore) { pathCount = (pathCount + resUp[1]) % MOD; } if (resLeft[0] == maxScore) { pathCount = (pathCount + resLeft[1]) % MOD; } if (resDiag[0] == maxScore) { pathCount = (pathCount + resDiag[1]) % MOD; } int currentScore = Character.isDigit(board.get(r).charAt(c)) ? board.get(r).charAt(c) - '0' : 0; return memo[r][c] = new int[]{maxScore + currentScore, pathCount}; } } ``` ### Algorithm - Initialize a memoization table `memo[N][N]` with a sentinel value (e.g., -1) to indicate that a state has not been computed. - Use the same recursive function `dfs(row, col)` as in the brute-force approach. - At the beginning of the `dfs` function, check if `memo[row][col]` contains a pre-computed result. If it does, return the cached value immediately. - If the result is not in the cache, proceed with the computation as in the brute-force method (handle base cases, make recursive calls, combine results). - Before returning the newly computed `[score, count]` pair, store it in `memo[row][col]` to cache it for future calls. - The main function initializes the memoization table and starts the recursion with `dfs(n-1, n-1)`. ## Bottom-Up Dynamic Programming This is an iterative approach to dynamic programming, often called bottom-up DP. We build the solution from the base case ('S') and iterate through the grid to compute the values for all cells up to 'E'. This avoids recursion and its associated overhead. **Time:** O(N^2), as we iterate through the grid once. · **Space:** O(N^2), for the two DP tables. **Pros:** Efficient and robust, with no risk of stack overflow.; Often slightly faster in practice than memoization due to the lack of function call overhead. **Cons:** Uses O(N^2) space, which might be suboptimal for problems with very large constraints. ### Explanation We use two 2D arrays, `dpScore[N][N]` and `dpPaths[N][N]`, to store the maximum score and the number of paths to reach each cell `(i, j)` from 'S'. Since the moves are up, left, and up-left, the state for cell `(i, j)` depends on cells with greater indices: `(i+1, j)`, `(i, j+1)`, and `(i+1, j+1)`. This dictates an iteration order from `(N-1, N-1)` backwards to `(0, 0)`. We initialize the DP tables and set the base case for 'S' at `(N-1, N-1)` with a score of 0 and 1 path. Then, we fill the tables iteratively. The final answer is found at `(0, 0)`. ```java class Solution { public int[] pathsWithMaxScore(List board) { int n = board.size(); int MOD = 1_000_000_007; int[][] dpScore = new int[n + 1][n + 1]; int[][] dpPaths = new int[n + 1][n + 1]; for (int i = 0; i <= n; i++) { java.util.Arrays.fill(dpScore[i], -1); } dpScore[n - 1][n - 1] = 0; dpPaths[n - 1][n - 1] = 1; char[][] grid = new char[n][n]; for(int i=0; i= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (grid[i][j] == 'X') continue; int maxScore = Math.max(dpScore[i + 1][j], Math.max(dpScore[i][j + 1], dpScore[i + 1][j + 1])); if (maxScore == -1) continue; // This check is to avoid overwriting the base case at S if (i != n-1 || j != n-1) { dpScore[i][j] = maxScore + (Character.isDigit(grid[i][j]) ? grid[i][j] - '0' : 0); } int pathCount = 0; if (dpScore[i + 1][j] == maxScore) { pathCount = (pathCount + dpPaths[i + 1][j]) % MOD; } if (dpScore[i][j + 1] == maxScore) { pathCount = (pathCount + dpPaths[i][j + 1]) % MOD; } if (dpScore[i + 1][j + 1] == maxScore) { pathCount = (pathCount + dpPaths[i + 1][j + 1]) % MOD; } // This check is to avoid overwriting the base case at S if (i != n-1 || j != n-1) { dpPaths[i][j] = pathCount; } } } return dpPaths[0][0] == 0 ? new int[]{0, 0} : new int[]{dpScore[0][0], dpPaths[0][0]}; } } ``` ### Algorithm - Create two 2D DP tables, `scores[N+1][N+1]` and `paths[N+1][N+1]`, to handle boundary conditions easily. - Initialize `scores` with -1 (unreachable) and `paths` with 0. - Set the base case at the starting point 'S': `scores[N-1][N-1] = 0` and `paths[N-1][N-1] = 1`. - Iterate through the grid from bottom-right to top-left (e.g., `i` from `N-1` down to `0`, `j` from `N-1` down to `0`). - For each cell `(i, j)` that is not an obstacle: - Consider the three cells from which we could have arrived: `(i+1, j)`, `(i, j+1)`, and `(i+1, j+1)`. - Find the maximum score (`max_prev_score`) among these three predecessor cells from the `scores` table. - If `max_prev_score` is -1, cell `(i, j)` is unreachable, so we skip it. - Update `scores[i][j]` by adding the current cell's numeric value to `max_prev_score`. - Update `paths[i][j]` by summing the path counts from all predecessor cells that have `max_prev_score`. - The final answer is `[scores[0][0], paths[0][0]]`. If `paths[0][0]` is 0, no path exists. ## Space-Optimized Bottom-Up DP This approach optimizes the space complexity of the bottom-up DP solution. We observe that to compute the DP values for the current row `i`, we only need the values from the immediately preceding row `i+1` and the already computed values in the current row. This allows us to reduce the space from O(N^2) to O(N). **Time:** O(N^2). The time complexity remains the same as the unoptimized DP approach. · **Space:** O(N), where N is the dimension of the board. We only need to store DP states for two rows. **Pros:** Most efficient solution with optimal time and space complexity.; Scales well for larger N where memory might be a concern. **Cons:** The logic can be slightly more complex to implement correctly compared to the standard 2D DP approach. ### Explanation We can optimize the O(N^2) space complexity by noticing that the calculation for row `i` only depends on row `i+1`. Therefore, we only need to store two rows of DP data at any time. We use 1D arrays to represent the current row being computed and the previous row. As we iterate up the grid row by row, we update the current row's DP values based on the previous row and the values already computed in the current row. This is the most efficient approach in terms of both time and space. ```java class Solution { public int[] pathsWithMaxScore(List board) { int n = board.size(); int MOD = 1_000_000_007; int[] dpScore = new int[n + 1]; int[] dpPaths = new int[n + 1]; java.util.Arrays.fill(dpScore, -1); dpScore[n - 1] = 0; dpPaths[n - 1] = 1; for (int i = n - 1; i >= 0; i--) { int[] nextDpScore = new int[n + 1]; int[] nextDpPaths = new int[n + 1]; java.util.Arrays.fill(nextDpScore, -1); for (int j = n - 1; j >= 0; j--) { if (board.get(i).charAt(j) == 'X') continue; int maxScore = -1; // From down (i+1, j) -> dpScore[j] // From right (i, j+1) -> nextDpScore[j+1] // From diag (i+1, j+1) -> dpScore[j+1] maxScore = Math.max(maxScore, dpScore[j]); maxScore = Math.max(maxScore, nextDpScore[j + 1]); maxScore = Math.max(maxScore, dpScore[j + 1]); if (maxScore == -1) continue; nextDpScore[j] = maxScore + (Character.isDigit(board.get(i).charAt(j)) ? board.get(i).charAt(j) - '0' : 0); if (i == 0 && j == 0) nextDpScore[j] = maxScore; // 'E' has no score int pathCount = 0; if (dpScore[j] == maxScore) { pathCount = (pathCount + dpPaths[j]) % MOD; } if (nextDpScore[j + 1] == maxScore) { pathCount = (pathCount + nextDpPaths[j + 1]) % MOD; } if (dpScore[j + 1] == maxScore) { pathCount = (pathCount + dpPaths[j + 1]) % MOD; } nextDpPaths[j] = pathCount; } dpScore = nextDpScore; dpPaths = nextDpPaths; } return dpPaths[0] == 0 ? new int[]{0, 0} : new int[]{dpScore[0], dpPaths[0]}; } } ``` ### Algorithm - Instead of full 2D tables, use two pairs of 1D arrays: `scores_curr[N]`, `paths_curr[N]` for the current row `i`, and `scores_prev[N]`, `paths_prev[N]` for the previous row `i+1`. - Iterate `i` from `N-1` down to `0`. - In each outer loop, compute the `_curr` arrays for row `i` by iterating `j` from `N-1` down to `0`. - The state for `(i, j)` depends on `(i+1, j)`, `(i, j+1)`, and `(i+1, j+1)`. In the 1D array representation, this corresponds to: - `scores_prev[j]` and `paths_prev[j]` - `scores_curr[j+1]` and `paths_curr[j+1]` - `scores_prev[j+1]` and `paths_prev[j+1]` - After the inner loop for `j` completes, the `_curr` arrays now hold the data for row `i`. They become the `_prev` arrays for the next iteration (for row `i-1`). This can be done by swapping pointers or copying the arrays. - The final answer is the value computed for `(0, 0)`. # Solutions ### Java ```java class Solution { private List board; private int n; private int[][] f; private int[][] g; private final int mod = (int)1 e9 + 7; public int[] pathsWithMaxScore(List board) { n = board.size(); this.board = board; f = new int[n][n]; g = new int[n][n]; for (var e : f) { Arrays.fill(e, -1); } f[n - 1][n - 1] = 0; g[n - 1][n - 1] = 1; for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { update(i, j, i + 1, j); update(i, j, i, j + 1); update(i, j, i + 1, j + 1); if (f[i][j] != -1) { char c = board.get(i).charAt(j); if (c >= '0' && c <= '9') { f[i][j] += (c - '0'); } } } } int[] ans = new int[2]; if (f[0][0] != -1) { ans[0] = f[0][0]; ans[1] = g[0][0]; } return ans; } private void update(int i, int j, int x, int y) { if (x >= n || y >= n || f[x][y] == -1 || board.get(i).charAt(j) == 'X' || board.get(i).charAt(j) == 'S') { return; } if (f[x][y] > f[i][j]) { f[i][j] = f[x][y]; g[i][j] = g[x][y]; } else if (f[x][y] == f[i][j]) { g[i][j] = (g[i][j] + g[x][y]) % mod; } } } ``` ### CPP ```cpp class Solution { public: vector pathsWithMaxScore(vector &board) { int n = board.size(); const int mod = 1e9 + 7; int f[n][n]; int g[n][n]; memset(f, -1, sizeof(f)); memset(g, 0, sizeof(g)); f[n - 1][n - 1] = 0; g[n - 1][n - 1] = 1; auto update = [&](int i, int j, int x, int y) { if (x >= n || y >= n || f[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S') { return; } if (f[x][y] > f[i][j]) { f[i][j] = f[x][y]; g[i][j] = g[x][y]; } else if (f[x][y] == f[i][j]) { g[i][j] = (g[i][j] + g[x][y]) % mod; } }; for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { update(i, j, i + 1, j); update(i, j, i, j + 1); update(i, j, i + 1, j + 1); if (f[i][j] != -1) { if (board[i][j] >= '0' && board[i][j] <= '9') { f[i][j] += (board[i][j] - '0'); } } } } vector ans(2); if (f[0][0] != -1) { ans[0] = f[0][0]; ans[1] = g[0][0]; } return ans; } }; ``` ### Python ```python 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] ```