Detailed mathematical approach

Problem Summary

The input is a triangle of integers with 100 rows. If the entry in row \(i\) and column \(j\) is denoted by \(a_{i,j}\) with \(0 \le j \le i < 100\), a valid path starts at \(a_{0,0}\) and, at each step, moves either to \(a_{i+1,j}\) or to \(a_{i+1,j+1}\). The task is to maximize the sum of all visited entries. Since there are 99 downward choices, a brute-force search would have to inspect \(2^{99}\) different paths, so the problem must be reduced mathematically rather than solved by enumeration.

Mathematical Approach

The central idea is that once a path reaches a given cell, the best continuation below that cell no longer depends on the earlier part of the path. That makes the triangle a natural dynamic-programming object.

The right state: the best suffix sum from a cell

Define \(F(i,j)\) to be the maximum total obtainable from cell \((i,j)\) down to the base of the triangle, including \(a_{i,j}\) itself. With this notation, the required answer is simply \(F(0,0)\).

On the last row there is no choice left, so the boundary condition is immediate:

$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$

where \(n=100\).

The recurrence comes from the only two legal moves

From \((i,j)\) there are exactly two admissible children: \((i+1,j)\) and \((i+1,j+1)\). Any optimal path from \((i,j)\) must pick one of those children first and then continue optimally from the chosen child. Therefore

$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$

This recurrence compresses the entire subtriangle below \((i,j)\) into one number: the best path sum available from that point onward.

Why a bottom-up sweep is correct

If the rows are processed in the order \(n-2,n-3,\dots,0\), then when row \(i\) is updated, both children of every cell in that row already store their correct \(F\)-values. Replacing each entry by its value plus the larger child therefore produces the correct \(F(i,j)\) for every position in row \(i\).

This gives a clean invariant: after finishing row \(i\), every entry in that row equals the best possible total from that cell to the bottom. By induction on the row index, the invariant propagates all the way to row 0, and the single entry at the top becomes the global optimum.

The same invariant also explains why the computation can be done in place. Once row \(i+1\) has been used to update row \(i\), the original values in row \(i+1\) are never needed again, so the triangle itself can serve as the dynamic-programming table.

Worked example

Consider the sample triangle with rows \(3\), \(7,4\), \(2,4,6\), and \(8,5,9,3\). The last row is already final. Moving one row upward gives

$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$

The next row becomes

$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$

and the top entry becomes

$3+\max(20,19)=23.$

So the optimal path sum is 23, realized by the path \(3 \to 7 \to 4 \to 9\).

Why brute force loses and the recurrence wins

A path-by-path search grows exponentially because every step branches into two possible continuations. The recurrence avoids that explosion by solving each subtriangle once. For a 100-row triangle there are only \(100 \cdot 101 / 2 = 5050\) cells, so the entire problem collapses to a short pass over those entries instead of an astronomical search through \(2^{99}\) full paths.

How the Code Works

Reading the triangle into a mutable structure

The C++, Python, and Java implementations read the input as text, split it into lines, ignore blank lines, and parse each row into integers. The resulting nested container has row lengths \(1,2,3,\dots,100\), matching the geometry assumed by the recurrence.

Overwriting rows from the base upward

They then iterate from the second-last row toward the top. For each entry, the implementation adds the larger of the two children directly below it. After one complete pass over a row, that row no longer stores raw triangle values; it stores the best suffix sums defined by \(F(i,j)\). When the loop reaches the top, the single remaining value is the maximum path sum for the whole triangle.

Sanity check before the full run

Each implementation includes a built-in checkpoint using the standard four-row sample. That check confirms that the bottom-up update produces 23 before the full 100-row triangle is processed. Aside from lightweight argument handling for the input source, the program is essentially the recurrence written directly into code.

Complexity Analysis

If the triangle has \(n\) rows, then it contains \(N=n(n+1)/2\) entries. The algorithm performs one update for every entry outside the last row, so the running time is \(\Theta(N)=\Theta(n^2)\). For Problem 67, \(N=5050\), which is tiny compared with \(2^{99}\).

The extra memory usage is \(O(1)\) beyond the mutable triangle, because the dynamic-programming values are written back into the same structure. If the input had to remain unchanged, the same recurrence could still be evaluated with an \(O(n)\) buffer containing one row of suffix sums.

Footnotes and References

1. Problem page: Project Euler 67
2. Dynamic programming: Wikipedia - Dynamic programming
3. Recurrence relations: Wikipedia - Recurrence relation
4. Principle of optimality: Wikipedia - Principle of optimality