Detailed mathematical approach

Problem Summary

The input is a 15-row triangle of positive integers. Starting at the apex, each move from row \(r\), column \(c\) may go only to row \(r+1\), column \(c\) or \(c+1\). The goal is to maximize the sum of the visited entries from the top to the base.

If the height is \(h\), a top-to-bottom route makes one binary choice in each of the first \(h-1\) rows, so there are \(2^{h-1}\) possible routes. For Problem 18, \(h=15\), hence \(2^{14}=16384\) candidate paths. The implementations still use dynamic programming, because many different routes share the same suffixes and the optimum can be recovered without enumerating any complete path.

Mathematical Approach

Let \(a_{r,c}\) be the entry in row \(r\), column \(c\), where \(0\le r\le h-1\) and \(0\le c\le r\). A valid path is a sequence of positions beginning at \((0,0)\) and ending somewhere on the last row, with each step changing the column by either \(0\) or \(1\). The central idea is to treat every cell as the start of a smaller maximum-path problem.

Suffix subproblems inside the triangle

Define \(F(r,c)\) to be the maximum sum obtainable from cell \((r,c)\) down to the base. Once the path has reached \((r,c)\), everything above it is already fixed, so the only remaining question is the best route through the subtriangle rooted at that cell. This is the exact overlapping-subproblem structure that the implementations exploit.

At the bottom row there is no further choice, so the boundary condition is immediate:

$F(h-1,c)=a_{h-1,c} \qquad (0\le c\le h-1).$

The recurrence forced by adjacency

From \((r,c)\) there are exactly two legal next positions, namely \((r+1,c)\) and \((r+1,c+1)\). Therefore every optimal path from \((r,c)\) must take the better of those two suffixes, which gives the recurrence

$F(r,c)=a_{r,c}+\max\bigl(F(r+1,c),\,F(r+1,c+1)\bigr).$

This is not a heuristic. It follows directly from the rules of the problem: any admissible path must choose one of those two children, and after that first step the remaining task is again a maximum-path problem of the same form.

Why bottom-up evaluation is correct

The recurrence for row \(r\) depends only on row \(r+1\), so the values can be computed from the bottom upward. Start with the last row, collapse the row above it, then keep moving upward until only the apex remains. A downward induction on \(r\) proves correctness: if the row below already stores the exact values \(F(r+1,\cdot)\), then one application of the recurrence produces the exact values \(F(r,\cdot)\).

Equivalently, after row \(r\) has been processed, the working row satisfies the invariant that its \(c\)-th entry equals the best possible sum from \((r,c)\) to the base. When the process reaches \(r=0\), the lone remaining value is \(F(0,0)\), the required maximum total.

Worked example: the shared 4-row checkpoint

The sample triangle used as a checkpoint in the implementations has rows \((3)\), \((7,4)\), \((2,4,6)\), and \((8,5,9,3)\).

Begin with the last row \((8,5,9,3)\). Collapsing the row above gives

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

Collapsing the next row gives

$(7+\max(10,13),\ 4+\max(13,15))=(20,19).$

Finally the apex becomes

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

So the maximum path sum is \(23\). The full 15-row instance is solved by exactly the same bottom-up reduction, only with more rows.

How the Code Works

Initialize from the base row

The C++, Python, and Java implementations store the 15-row triangle directly and copy the last row into a one-dimensional working array. At that moment, the working array already equals the correct values of \(F(h-1,c)\) for the base row.

Overwrite one row of state upward

The implementations then iterate from the second-last row to the top. For each position they replace the current working entry by the current triangle value plus the larger of its two child values from the row below. Only one row of memory is needed, because row \(r\) depends exclusively on row \(r+1\).

The in-place update order is safe: when a position is updated, the two child values it needs still represent the row below. After a full pass over row \(r\), the first \(r+1\) entries of the working array are exactly the values \(F(r,0),F(r,1),\dots,F(r,r)\). All three implementations also verify the 4-row sample whose correct answer is \(23\).

Complexity Analysis

A triangle of height \(h\) contains

$N=\frac{h(h+1)}{2}$

entries. The dynamic program touches each non-base cell once, so the running time is \(O(N)\), equivalently \(O(h^2)\). The extra memory is \(O(h)\), because only one working row is stored.

For Problem 18 specifically, \(h=15\) and \(N=120\). After copying the bottom row, the reduction phase performs \(1+2+\cdots+14=105\) updates, which is far smaller than exploring all \(2^{14}=16384\) complete routes one by one.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=18
2. Dynamic programming: Wikipedia - Dynamic programming
3. Optimal substructure: Wikipedia - Optimal substructure
4. Principle of optimality: Wikipedia - Principle of optimality