Number of Paths with Max Score - Video Solutions

Problem Overview: You are given an n x n board containing digits, obstacles (X), a start cell S, and an end cell E. Starting from S (bottom‑right), you can move up, left, or diagonally up‑left until reaching E. Each path collects numeric values from cells, and the goal is to compute the maximum possible score and the number of distinct paths that achieve that score.

Approach 1: Dynamic Programming (State Tracking) (Time: O(n²), Space: O(n²))

This solution uses a DP table where each cell stores two values: the maximum score achievable when reaching that cell and the number of ways to achieve that score. Starting from S, you iterate through the grid in reverse directions that match the allowed moves (up, left, diagonal). For every valid cell, check the three predecessor states and choose the one producing the highest score. If multiple predecessors produce the same score, sum their path counts (mod 1e9+7). This works well because each cell’s result depends only on previously computed states, a classic pattern in dynamic programming.

Approach 2: Dynamic Programming from Bottom‑Right to Top‑Left (Time: O(n²), Space: O(n²))

This is the most common implementation used in interviews. Instead of expanding from the start, the algorithm fills the DP table while scanning the grid from bottom‑right to top‑left. At each cell, examine the three reachable neighbors (down, right, and down‑right) that represent valid forward moves. Compute the best score among them, then update the current cell’s score and path count accordingly. Obstacles (X) immediately invalidate states. Because each cell is processed exactly once, the algorithm runs in O(n²) time and efficiently handles grids up to typical constraints. The grid traversal pattern is common in matrix DP problems.

Approach 3: Breadth‑First Search with Priority Queue (Time: O(n² log n), Space: O(n²))

This alternative models the board as a graph. Each cell is a node and edges represent valid moves. A max‑priority queue always expands the state with the highest accumulated score first, similar to a modified Dijkstra traversal. For each expansion, update neighbor states if a higher score is found or if an equal score adds additional paths. While conceptually intuitive for graph thinking, the priority queue introduces a log factor and makes it slower than pure DP. This approach highlights how grid traversal problems can also be framed as graph searches over an array structure.

Recommended for interviews: The bottom‑right to top‑left dynamic programming solution is what most interviewers expect. It shows you can translate grid movement constraints into DP state transitions and track both score and path counts simultaneously. A brute‑force search would explore exponentially many paths, so demonstrating the DP optimization proves strong algorithmic reasoning.