Problem Analysis
This problem asks for the maximum-sum path from the apex of a triangle of integers down to its base, where at each step I may step only to one of the two numbers directly below. With 100 rows there are 299 distinct top-to-bottom paths, so trying every route - brute force - is hopeless. The problem statement makes the point explicitly: even at a trillion paths per second, exhaustive search would take longer than the age of the universe. The exercise is really about recognising that a far smarter method exists.
The crucial observation is that the problem has optimal substructure: the best path passing through any given cell equals that cell's value plus the better of the two best paths through its two children below. Because the answer for the whole is built from optimal answers to smaller, overlapping sub-problems, this is exactly the setting where dynamic programming (DP) applies - solving each sub-problem once, storing its result, and reusing it instead of recomputing. The triangle can also be viewed as a directed acyclic graph - a network of nodes connected by one-way edges that never loop back - and finding a maximum-weight path through such a graph is a textbook dynamic programming problem. Since each of the roughly n(n+1)/2 cells is visited exactly once, the algorithm runs in O(n2) time - about 5,000 operations for n = 100, which is effectively instantaneous.
Solution Approach
Bottom-Up Triangle Fold (Python and C)
The Python and C solutions implement one and the same algorithm; they differ only in syntax and in how they manage memory. I chose a bottom-up formulation - starting from the base cases (the last row) and working upward to the answer - rather than recursing from the top down. This sidesteps recursion overhead and removes any need for an explicit cache, because the base cases are simply the cells themselves and the merged values accumulate naturally as I climb.
Step 1 - Parse the input. The triangle is a text file, one row per line, with space-separated integers; row i holds i+1 numbers. I read the file and split it into a list of lists of integers (Python's text2triangle) or a heap-allocated array of arrays (C's text2triangle), indexed as triangle[row][col]. The C parser walks the buffer twice in spirit - first counting rows, then allocating each row to its exact length and filling it with atoi.
Step 2 - Deep copy. The fold mutates the triangle, so I copy it first to leave the parsed data intact and keep max_path_sum_triangle free of side effects on its input. Python uses copy.deepcopy; C allocates fresh rows and copies them with memcpy.
Step 3 - Fold from the bottom. While more than one row remains, I update the second-to-last row by adding to each entry the larger of its two children in the last row, then discard the last row. In Python this is a single expressive line:
triangle[-2] = [v + max(triangle[-1][i], triangle[-1][i + 1]) for i, v in enumerate(triangle[-2])]
followed by del triangle[-1]. In C I write the explicit loop, choose the larger child with a ternary expression (left > right ? left : right), and free the discarded row immediately after it is merged.
Step 4 - Read off the answer. When the loop ends, exactly one cell remains: triangle[0][0] holds the maximum path sum, 7273.