Detailed mathematical approach

Problem Summary

We are given a square matrix of positive integers. A valid path may start in any row of the first column and end in any row of the last column. The allowed moves are right, up, and down, but never left. The objective is to minimize the sum of all entries visited by the path.

The extra difficulty, compared with a purely right-and-down problem, is that vertical motion is allowed inside a column. That means the best value for one cell in a column depends on other cells in the same column, so the natural state is not a single cell but the whole frontier formed by one processed column.

Mathematical Approach

Let \(M_{r,c}\) denote the matrix entry in row \(r\), column \(c\), with \(0 \le r,c < n\). After processing column \(c\), define \(D^{(c)}_r\) to be the minimum path sum among all valid paths that end at cell \((r,c)\). The final answer is therefore

$\min_{0 \le r < n} D^{(n-1)}_r.$

The State After One Column

In the first column nothing has happened yet: every row is an admissible starting point. Hence the initial state is simply

$D^{(0)}_r = M_{r,0} \qquad (0 \le r < n).$

This is the invariant the implementations maintain: once column \(c\) has been finished, the vector \(D^{(c)}\) contains the exact optimal costs for reaching every row of that column.

What an Optimal Transition Into a New Column Looks Like

Fix a column \(c \ge 1\) and assume the previous vector \(D^{(c-1)}\) is already known. Any path that ends at row \(r\) of the new column must enter column \(c\) from the left at some row \(k\), paying \(D^{(c-1)}_k + M_{k,c}\), and then move vertically inside column \(c\) until it reaches row \(r\).

Because all matrix entries are positive and left moves are forbidden, an optimal path never changes vertical direction inside a single column. If it moved up and later down again, or down and later up again, then some row in that column would be visited twice, producing a positive detour that can be removed. So the vertical segment inside one column is always monotone.

That observation gives the exact one-column formula:

$D^{(c)}_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right).$

For each possible entry row \(k\), we pay the best cost to reach the previous column at row \(k\), then we add precisely the cells traversed in column \(c\) from row \(k\) to row \(r\).

Why Two Linear Sweeps Are Enough

The formula naturally splits into two families of candidates. If \(k \le r\), the path enters at row \(k\) and moves only downward inside the new column, contributing

$D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}.$

If \(k \ge r\), the path enters at row \(k\) and moves only upward, contributing

$D^{(c-1)}_k + \sum_{t=r}^{k} M_{t,c}.$

The implementations begin with the direct-right candidate

$T_r = D^{(c-1)}_r + M_{r,c}.$

Then they sweep from top to bottom:

$T_r \leftarrow \min\bigl(T_r,\; T_{r-1} + M_{r,c}\bigr)\qquad (r=1,2,\dots,n-1).$

After this pass, every downward-only possibility has been absorbed, so

$T_r = \min_{0 \le k \le r}\left(D^{(c-1)}_k + \sum_{t=k}^{r} M_{t,c}\right).$

A second sweep from bottom to top handles the upward-only possibilities:

$T_r \leftarrow \min\bigl(T_r,\; T_{r+1} + M_{r,c}\bigr)\qquad (r=n-2,n-3,\dots,0).$

When that pass ends, we have exactly

$T_r = \min_{0 \le k < n}\left(D^{(c-1)}_k + \sum_{t=\min(k,r)}^{\max(k,r)} M_{t,c}\right)=D^{(c)}_r.$

So the two sweeps are not a heuristic shortcut; they are a compact way to evaluate the full minimum over all possible entry rows.

Worked Example on the 5 by 5 Sample

For the sample matrix

$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}$

the first column gives

$D^{(0)} = (131, 201, 630, 537, 805).$

In column 1, the direct-right candidates are

$T = (804, 297, 1433, 1236, 1537).$

The downward sweep improves row 2, producing

$T = (804, 297, 1100, 1236, 1537),$

and the upward sweep changes nothing further, so

$D^{(1)} = (804, 297, 1100, 1236, 1537).$

Column 2 is a good illustration of why both directions matter. The direct-right vector is

$T = (1038, 639, 1846, 1733, 2061).$

After the downward sweep it becomes

$T = (1038, 639, 1385, 1733, 2061),$

and the upward sweep then improves the first row to

$D^{(2)} = (873, 639, 1385, 1733, 2061).$

That improvement comes from entering column 2 at row 1 with cost \(639\) and then moving upward through the value \(234\).

Continuing this process to the last column gives

$D^{(4)} = (994, 1144, 1255, 2211, 2222).$

Hence the sample minimum is

$\min_r D^{(4)}_r = 994,$

realized by the path \(201 \to 96 \to 342 \to 234 \to 103 \to 18\).

How the Code Works

The C++, Python, and Java implementations all read the CSV matrix into a two-dimensional array and keep a one-dimensional dynamic-programming vector for the current column. That vector starts as the first column itself, because any row there can be chosen as the starting position.

For each later column, the implementation first forms the direct-right candidates by adding the new column entry to every row. It then performs one top-to-bottom relaxation and one bottom-to-top relaxation, which exactly match the two monotone cases in the derivation above. After the final column has been processed, the minimum value in the vector is the minimum path sum from the left edge to the right edge.

Complexity Analysis

Each new column is handled by three linear passes over the rows: one initialization pass, one downward sweep, and one upward sweep. For an \(n \times n\) matrix, that is \(O(n)\) work per column and \(O(n^2)\) time overall.

The extra working memory is \(O(n)\), because the algorithm only needs the current column-cost vector in addition to the input matrix. For the \(80 \times 80\) instance in the problem, this is comfortably fast and avoids the extra overhead of running a fully general shortest-path routine on the whole grid graph.

Footnotes and References

1. Problem page: Project Euler - Problem 82
2. Dynamic programming: Wikipedia - Dynamic programming
3. Shortest path problem: Wikipedia - Shortest path problem
4. Dijkstra's algorithm: Wikipedia - Dijkstra's algorithm