Dynamic Programming • 2D Grids

Maximum Path Sum in Matrix

Find the maximum sum of a falling path through a matrix. You can start at any cell in the top row and fall down-left, down, or down-right.

Try Interactive Simulator

Overview

This is standard 2D Grid DP with a twist: you can start ANYWHERE in the top row, and you must reach the bottom row. At each step, you can fall to 3 possible adjacent columns.

The Logic

For any cell `(r, c)`, the maximum path to reach it is its own value plus the maximum of the three valid cells directly above it: `(r-1, c-1)`, `(r-1, c)`, or `(r-1, c+1)`.

Out of Bounds

When calculating `upLeft` or `upRight` for edge columns, the out-of-bounds cells are treated as `-Infinity` so they are never picked by the `Math.max` function.

The Answer

Because the path can end anywhere in the bottom row, the final answer is the maximum value in the entire last row of the `dp` array.

Code Tracker

:::

1for (let c = 0; c < C; c++) dp[0][c] = matrix[0][c];

2

3for (let r = 1; r < R; r++) {

4 for (let c = 0; c < C; c++) {

5 let up = dp[r-1][c];

6 let upLeft = c > 0 ? dp[r-1][c-1] : -Infinity;

7 let upRight = c < C - 1 ? dp[r-1][c+1] : -Infinity;

8

9 dp[r][c] = matrix[r][c] + Math.max(up, upLeft, upRight);

10 }

11}

12return Math.max(...dp[R-1]);

Maximum Path Sum Matrix

Maximum Path Sum Matrix

Maximum Path Sum in Matrix

Overview

The Logic

Out of Bounds

The Answer

Maximum Path Sum in Matrix

Overview

The Logic

Out of Bounds

The Answer