DDSA Solutions

1301. Number of Paths with Max Score

HardView on LeetCode
ArrayDynamic ProgrammingMatrix
Time: O(n^2)
Space: O(n^2)

Problem Overview

Paths move only right, down, or diagonally from start to end.

Intuition

Paths move only right, down, or diagonally from start to end. Work backward from the bottom-right: each cell inherits the best score reachable from its three forward neighbors, and we count how many ways achieve that best. Blocked cells (X) and the start cell (S) contribute zero digit value.

Algorithm

  1. 1Initialize dp and count at (n−1,n−1): score 0, one path.
  2. 2Iterate cells (i,j) from bottom-right to top-left.
  3. 3Skip X and S for score accumulation; for each of three directions, relax dp[i,j] with neighbor score.
  4. 4On a strictly better neighbor score, replace dp and reset count; on a tie, add counts modulo 1e9+7.
  5. 5If dp[i,j] is reachable and cell is not E, add board[i][j] digit to dp[i,j].
  6. 6Return [dp[0,0], count[0,0]].

Example Walkthrough

Input: board = ["E23","2X2","12S"]

  1. 1.From (2,2) backward: only path to E is diagonal chain.
  2. 2.At each step, pick the neighbor direction with maximum accumulated score.
  3. 3.Ties in score add their path counts together.

Output: [7, 1] (max score 7 along one optimal path)

Common Pitfalls

  • •Process from (n−1,n−1) toward (0,0); forward DP from S is harder because max-score paths merge backward.
  • •Modulo applies to count, and digit addition on dp also uses mod in this formulation.
  • •Do not add digit value on E or X cells.
1301.cs
C#
// Approach: Bottom-up DP from (n−1,n−1). For each cell, take max score from right/down/diagonal
// neighbors and sum path counts on ties. Add digit score when the cell is reachable.
// Time: O(n^2) Space: O(n^2)
public class Solution
{
    public int[] PathsWithMaxScore(IList<string> board)
    {
        const int MOD = 1_000_000_007;
        int[][] DIRS = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 1, 1 } };
        int n = board.Count;
        // dp[i][j] := the maximum sum from (n - 1, n - 1) to (i, j)
        int[,] dp = new int[n + 1, n + 1];
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
                dp[i, j] = -1;
        }
        // count[i][j] := the number of paths to get dp[i][j] from (n - 1, n - 1) to (i, j)
        int[,] count = new int[n + 1, n + 1];

        dp[0, 0] = 0;
        dp[n - 1, n - 1] = 0;
        count[n - 1, n - 1] = 1;

        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                char c = board[i][j];
                if (c == 'S' || c == 'X')
                    continue;
                foreach (var dir in DIRS)
                {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x < 0 || x >= n || y < 0 || y >= n)
                        continue;
                    if (dp[i, j] < dp[x, y])
                    {
                        dp[i, j] = dp[x, y];
                        count[i, j] = count[x, y];
                    }
                    else if (dp[i, j] == dp[x, y])
                        count[i, j] = (count[i, j] + count[x, y]) % MOD;
                }
                // If there's path(s) from 'S' to (i, j) and the cell is not 'E'.
                if (dp[i, j] != -1 && c != 'E')
                    dp[i, j] = (dp[i, j] + (c - '0')) % MOD;
            }
        }

        return new int[] { dp[0, 0], count[0, 0] };
    }
}
Was this solution helpful?

Related Problems