Detailed mathematical approach

Problem Summary

Let \(a_{i,j}\) be the entry in row \(i\), column \(j\) of an \(80 \times 80\) matrix of positive integers. Starting at the top-left cell and finishing at the bottom-right cell, each move is restricted to one step right or one step down, and the cost of a path is the sum of every visited entry, including the first and last cell.

A brute-force search would have to examine every monotone lattice path from \((0,0)\) to \((79,79)\). There are

$\binom{158}{79}\approx 2.32\times 10^{46}$

such paths, so enumeration is hopeless. The key simplification is that any path into a cell \((i,j)\) must arrive either from \((i-1,j)\) or from \((i,j-1)\), which turns the problem into a small dynamic program on the grid itself.

Mathematical Approach

The natural quantity to compute is not the best complete path all at once, but the best partial path ending at each cell. Once those partial optima are known, the answer at the bottom-right corner follows immediately.

The state that matters

Define \(F_{i,j}\) to be the minimum possible path sum from the start \((0,0)\) to the cell \((i,j)\), with both endpoints included in the sum. The final answer is therefore \(F_{79,79}\).

This state is problem-specific and sufficient: if we know the optimal cost to each predecessor of \((i,j)\), then we know everything needed to compute the optimal cost to \((i,j)\) itself.

The boundary strip has only one path

Along the top row there is no freedom at all: every valid path must keep moving right. Along the left column there is the analogous forced path moving only downward. Therefore the boundary values satisfy

$F_{0,0}=a_{0,0},\qquad F_{0,j}=F_{0,j-1}+a_{0,j}\quad (j\ge 1),\qquad F_{i,0}=F_{i-1,0}+a_{i,0}\quad (i\ge 1).$

These formulas are exactly what the implementations use when they initialize the first row and the first column before touching the interior of the matrix.

The interior recurrence

For any interior cell \((i,j)\) with \(i\ge 1\) and \(j\ge 1\), the last move of a valid path must come from above or from the left. No other predecessor is possible because the path may move only right and down. Hence

$F_{i,j}=a_{i,j}+\min\!\bigl(F_{i-1,j},F_{i,j-1}\bigr).$

The proof is the standard optimal-substructure argument. Take an optimal path ending at \((i,j)\). Remove its last cell. What remains must already be an optimal path to whichever predecessor was used; otherwise, replacing that prefix by a cheaper one would produce a cheaper full path, contradicting optimality.

Why row-major order is valid

The recurrence depends only on the cell directly above and the cell directly to the left. If we process the grid row by row from top-left to bottom-right, both of those values are already final when \((i,j)\) is updated. Equivalently, the grid with right/down edges is a directed acyclic graph, and row-major order is one valid topological order.

This gives the core invariant behind all three implementations: after a cell has been processed, the stored value at that position is exactly the minimum path sum to that cell. The C++, Python, and Java versions differ only in where they store those values, not in the invariant itself.

Worked example: the 5 by 5 sample

The sample matrix used in the problem statement and in the built-in C++ checkpoint is

$A=\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}.$

After filling the first row and first column, the interior cells are updated by the recurrence. For instance,

$F_{1,1}=96+\min(804,332)=428,\qquad F_{2,3}=422+\min(1735,1516)=1938.$

Continuing to the end gives the full dynamic-programming table

$F=\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159 \\ 332 & 428 & 770 & 1735 & 1309 \\ 962 & 1231 & 1516 & 1938 & 1420 \\ 1499 & 1930 & 2013 & 2059 & 2376 \\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}.$

So the minimum path sum for the sample is \(2427\). One optimal path is

$131 \to 201 \to 96 \to 342 \to 746 \to 422 \to 121 \to 37 \to 331,$

whose total is indeed \(2427\).

How the Code Works

The C++, Python, and Java implementations all parse the input as comma-separated rows of integers, then perform exactly the boundary initialization and interior recurrence described above.

Reading the matrix

Each implementation reads the matrix line by line, splits each line on commas, and converts the resulting tokens to integers. The mathematical object is therefore the same in all three languages: a square grid of weights.

The dynamic-programming sweep

The update order is top-left to bottom-right. The start cell is left unchanged. Then the first row is turned into cumulative sums from left to right, the first column into cumulative sums from top to bottom, and every remaining cell is replaced by its own weight plus the smaller of the already computed top and left totals.

The C++ implementation also includes a small sample verification: before solving the full input, it checks that the sample matrix above produces \(2427\). That checkpoint matches the worked example in the mathematical derivation.

Why the storage choices differ but the mathematics does not

The C++ implementation keeps a separate table of path sums, using a wider integer type for the accumulated totals. The Python and Java implementations instead overwrite the matrix in place, so each entry becomes the minimum path sum to that cell. Both strategies implement the same recurrence and preserve the same invariant; the only difference is whether the original matrix values are kept separately after processing begins.

Complexity Analysis

The running time is \(\Theta(n^2)\) for an \(n \times n\) matrix, because each cell is processed once and each update uses only constant-time arithmetic and one minimum comparison. For the \(80 \times 80\) instance, there are \(6400\) cells and \(6399\) updates after the start cell.

Space depends on the chosen storage strategy. A separate table uses \(\Theta(n^2)\) additional memory, which is what the C++ implementation does. Overwriting the matrix uses \(O(1)\) extra space beyond the input itself, which is what the Python and Java implementations do. A one-row rolling array would reduce the extra space to \(O(n)\) while keeping the same recurrence.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=81
2. Dynamic programming overview: Wikipedia - Dynamic programming
3. Bellman equation: Wikipedia - Bellman equation
4. Shortest path problem: Wikipedia - Shortest path problem
5. Directed acyclic graph: Wikipedia - Directed acyclic graph