Number of Paths with Max Score - Practice Coding Problems

Number of Paths with Max Score - Problem

Number of Paths with Max Score

Imagine you're navigating a treasure-filled dungeon represented as a square grid! You start at the bottom-right corner marked with 'S' and need to reach the top-left corner marked with 'E'.

Each cell contains either:
• A treasure value (digits 1-9) that you can collect
• An obstacle marked with 'X' that blocks your path

You can move in three directions: up, left, or diagonally up-left. Your goal is to find the path that maximizes your treasure collection!

Return: A list with two integers:
1. The maximum sum of treasure you can collect
2. The number of different paths that achieve this maximum sum (modulo 10⁹ + 7)

If no path exists, return [0, 0].

Input & Output

example_1.py — Basic Path Finding

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

› Output: [7, 1]

💡 Note: There is one path: S(0) → 1(1) → 2(3) → 2(5) → 3(8) → E. The maximum score is 7 and there's exactly 1 path achieving this score.

example_2.py — Multiple Optimal Paths

$ Input: board = ["E12", "1X1", "21S"]

› Output: [4, 2]

💡 Note: There are two optimal paths: S(0) → 1(1) → 2(3) → 1(4) → E and S(0) → 2(2) → 1(3) → 1(4) → E. Both achieve maximum score of 4.

example_3.py — No Valid Path

$ Input: board = ["E11", "XXX", "11S"]

› Output: [0, 0]

💡 Note: All paths from S to E are blocked by obstacles 'X', so there's no valid path. Return [0, 0].

Constraints

2 ≤ board.length == board[i].length ≤ 100
board[i][j] is one of 'E', 'S', '1', '2', ..., '9', or 'X'
It is guaranteed that board[0][0] == 'E' and board[n-1][n-1] == 'S'
Answer fits in 32-bit signed integer

Visualization

Tap to expand

16 coinsNumber of optimal paths: 1💡 DP builds solution backwards:Each room knows the best future treasure!

Understanding the Visualization

Set Base Camp

Mark the destination 'E' with score (0, 1) - no treasure needed here, one way to 'finish'

Map Adjacent Rooms

Calculate treasure scores for cells next to destination, considering all three possible approaches

Build Treasure Map

Continue row by row, each cell learns the optimal treasure and path count from future positions

Find Starting Strategy

The starting position 'S' now contains the maximum treasure and total optimal paths

Key Takeaway

🎯 Key Insight: Dynamic Programming transforms this exponential search into an efficient O(n²) solution by building optimal substructure from destination to source, avoiding redundant path explorations.

Asked in

G Google 45 a Amazon 38 ⊞ Microsoft 32 f Meta 25

The optimal solution uses Dynamic Programming with O(n²) time complexity. We build a DP table where each cell stores the maximum treasure score and count of optimal paths. The key insight is to work from the destination 'E' to the source 'S', considering three possible previous positions for each cell. This avoids redundant calculations while correctly handling multiple optimal paths and obstacles.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Exploration (Brute Force)	O(3^(n²))	O(n²)	Explore all possible paths recursively to find maximum treasure sum
Dynamic Programming (Optimal)	O(n²)	O(n²)	Build solution incrementally using bottom-up DP with memoization

Recursive Exploration (Brute Force) — Algorithm Steps

Start from bottom-right cell marked 'S'
For each cell, recursively try three moves: up, left, up-left diagonal
Skip cells with obstacles ('X')
Track maximum sum and count paths that achieve this maximum
Return when reaching top-left cell marked 'E'

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at 'S'

Begin exploration from bottom-right corner

Branch paths

Try all three directions from current cell

Collect treasures

Add treasure values along each path

Find maximum

Compare all complete paths to find maximum sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MOD 1000000007
#define MAXN 105

struct Result {
    int score;
    int paths;
};

struct Result memo[MAXN][MAXN];
int visited[MAXN][MAXN];
char board[MAXN][MAXN];
int n;

struct Result dfs(int i, int j) {
    struct Result invalid = {-1, 0};
    
    if (i < 0 || j < 0 || board[i][j] == 'X') {
        return invalid;
    }
    
    if (visited[i][j]) {
        return memo[i][j];
    }
    
    if (i == 0 && j == 0) {
        struct Result base = {0, 1};
        visited[i][j] = 1;
        memo[i][j] = base;
        return base;
    }
    
    int directions[3][2] = {{-1, 0}, {0, -1}, {-1, -1}};
    int maxScore = -1;
    int totalPaths = 0;
    
    for (int k = 0; k < 3; k++) {
        int ni = i + directions[k][0];
        int nj = j + directions[k][1];
        struct Result subResult = dfs(ni, nj);
        
        if (subResult.score == -1) continue;
        
        int currentScore = subResult.score;
        if (isdigit(board[i][j])) {
            currentScore += board[i][j] - '0';
        }
        
        if (currentScore > maxScore) {
            maxScore = currentScore;
            totalPaths = subResult.paths;
        } else if (currentScore == maxScore) {
            totalPaths = (totalPaths + subResult.paths) % MOD;
        }
    }
    
    struct Result result;
    if (maxScore == -1) {
        result = invalid;
    } else {
        result.score = maxScore;
        result.paths = totalPaths;
    }
    
    visited[i][j] = 1;
    memo[i][j] = result;
    return result;
}

int* pathsWithMaxScore(char** boardInput, int boardSize, int* returnSize) {
    n = boardSize;
    *returnSize = 2;
    
    memset(visited, 0, sizeof(visited));
    
    for (int i = 0; i < n; i++) {
        strcpy(board[i], boardInput[i]);
    }
    
    struct Result result = dfs(n-1, n-1);
    
    int* answer = (int*)malloc(2 * sizeof(int));
    if (result.score >= 0) {
        answer[0] = result.score;
        answer[1] = result.paths;
    } else {
        answer[0] = 0;
        answer[1] = 0;
    }
    
    return answer;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^(n²))

Each cell can be reached from 3 directions, creating exponential branching

⚠ Quadratic Growth

Space Complexity

O(n²)

Recursion depth can be up to n² in worst case

⚠ Quadratic Space

48.2K Views

Medium-High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Exploration (Brute Force) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler