Problem Analysis
The task is to find, among all top-to-bottom paths through a number triangle, the one whose sum of visited values is largest. At each step we descend from a cell to one of the two cells immediately below it. A triangle with N rows therefore has 2^(N-1) distinct paths - 16,384 for the 15-row triangle here, and an astronomical 2^99 for the 100-row variant in Problem 67. A brute-force enumeration of every path quickly becomes intractable, so I needed a smarter method.
The unlocking observation is that this problem has optimal substructure: the best path from any cell down to the base is that cell's value plus the better of the two best paths starting from its two children. Because the best overall path must also be the best path through every sub-triangle it crosses, I can solve the problem with dynamic programming - a technique that builds up an answer from solutions to smaller, overlapping sub-problems instead of recomputing them. By computing "the maximum sum reachable from this cell down to the base" for every cell, starting at the bottom and working upward, the apex eventually holds the global answer. Each cell is visited exactly once, so the algorithm runs in O(N^2) time (proportional to the number of cells) - a dramatic improvement over the exponential enumeration, and one that scales effortlessly to the 100-row case.
Solution Approach
Bottom-Up Reduction of the Triangle (Python and C)
Both p0018_s0.py and p0018_s0.c implement the same algorithm. I first
parse the triangle from a multiline string into a two-dimensional array of integers, then
collapse it row by row from the bottom up.
The collapse works as follows. I look at the last two rows. For each position i in
the second-to-last row, I add the larger of its two children - the cells at indices
i and i+1 in the last row - to the value already stored there. After
this, every cell in the second-to-last row holds "the maximum sum reachable from here to the
base". I then discard the last row and repeat. When only the single apex cell remains, it holds
the global maximum. This is the direct expression of the
optimal-substructure
recurrence: best(cell) = value(cell) + max(best(left child), best(right child)),
evaluated bottom-up so that each child's answer is already known when its parent is processed.
The whole reduction touches each of the N(N+1)/2 cells once, which is why it runs in
O(N^2)
time.
In Python the inner step is a single
list comprehension:
triangle[-2] = [v + max(triangle[-1][i], triangle[-1][i + 1]) for i, v in enumerate(triangle[-2])],
followed by del triangle[-1] to shrink the structure. I call
deep copy
(copy.deepcopy) first so that the caller's triangle is never mutated - important
because the benchmark harness calls solve repeatedly with the same data. In C I
perform the update in place on triangle[current_rows - 2] and simply decrement
current_rows rather than freeing rows mid-loop; this is cache-friendly and avoids
repeated allocation. The C parser counts rows by scanning for newlines, makes a mutable copy of
the input (strtok
modifies its argument), and allocates each row to its exact length via a count-then-fill pass.
All allocations are freed after the result is computed.