LeetCode 1301: Number of Paths with Max Score Solution

Master LeetCode problem 1301 (Number of Paths with Max Score), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1301. Number of Paths with Max Score

Hard

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through the board from bottom right to top left, calculating the maximum sum of numeric characters we can collect and the number of paths to reach each cell. We will also keep track of the number of paths that result in the maximum sum.

Initialize a 2D DP array to store the maximum sum and number of paths to reach each cell.
Start iterating from the bottom right cell towards the top left cell.
For each cell, calculate the maximum sum and number of paths to reach that cell based on the adjacent cells below, to the left, and diagonally down-left.
At the end, return the maximum sum and number of paths to reach the top left cell.

Time Complexity: O(n^2) where n is the size of the board Space Complexity: O(n^2)

Solution Code

class Solution {
    public int[] pathsWithMaxScore(List<String> board) {
        int MOD = 1000000007;
        int n = board.size();
        int[][] dp = new int[n][n];
        int[][] count = new int[n][n];
        count[n-1][n-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') {
                    continue;
                }
                for (int k = 0; k < 3; k++) {
                    int ni = i + (k == 2 ? -1 : 0);
                    int nj = j + (k == 1 ? -1 : 0);
                    if (ni >= 0 && nj >= 0 && count[ni][nj] > 0) {
                        int nsum = dp[ni][nj] + (board.get(i).charAt(j) == 'E' ? 0 : board.get(i).charAt(j) - '0');
                        if (nsum > dp[i][j]) {
                            dp[i][j] = nsum;
                            count[i][j] = count[ni][nj];
                        } else if (nsum == dp[i][j]) {
                            count[i][j] = (count[i][j] + count[ni][nj]) % MOD;
                        }
                    }
                }
            }
        }
        
        return new int[]{dp[0][0], count[0][0]};
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1301 (Number of Paths with Max Score)?

This page provides optimized solutions for LeetCode problem 1301 (Number of Paths with Max Score) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1301 (Number of Paths with Max Score)?

The time complexity for LeetCode 1301 (Number of Paths with Max Score) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1301 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1301 in Java, C++, or Python.

Back to LeetCode Solutions