Introduction

Project Euler 18 asks for the maximum path sum from top to bottom of a number triangle, moving only to adjacent numbers on the next row. The brute-force approach explores all paths and grows exponentially. The practical solution is dynamic programming, which computes the answer in quadratic time.

Problem Restatement

Given a triangle:

1      3
2     7 4
3    2 4 6
4   8 5 9 3

You can move from row r, column c to either r+1,c or r+1,c+1. The goal is the largest possible sum from top to bottom.

For the sample above, best route is 3 -> 7 -> 4 -> 9, total 23.

Why Brute Force Does Not Scale

Each row gives two branching choices, so the number of paths is 2^(n-1) for n rows. That growth is fine for tiny triangles but becomes expensive quickly.

Naive recursion:

1def brute(triangle, r=0, c=0):
2    if r == len(triangle) - 1:
3        return triangle[r][c]
4
5    left = brute(triangle, r + 1, c)
6    right = brute(triangle, r + 1, c + 1)
7
8    return triangle[r][c] + max(left, right)

This recalculates the same subproblems many times.

Bottom-Up Dynamic Programming

The key insight is local optimal substructure. Best sum at each cell equals cell value plus max of the two best sums directly below it.

1def max_path_sum(triangle):
2    dp = [row[:] for row in triangle]
3
4    for r in range(len(dp) - 2, -1, -1):
5        for c in range(len(dp[r])):
6            dp[r][c] += max(dp[r + 1][c], dp[r + 1][c + 1])
7
8    return dp[0][0]
9
10
11triangle = [
12    [3],
13    [7, 4],
14    [2, 4, 6],
15    [8, 5, 9, 3],
16]
17
18print(max_path_sum(triangle))  # 23

Complexity is O(n^2) for n rows because triangle contains about n(n+1)/2 values.

Space-Optimized Variant

You do not need a full DP matrix. One rolling row is enough.

1def max_path_sum_optimized(triangle):
2    best = triangle[-1][:]
3
4    for r in range(len(triangle) - 2, -1, -1):
5        next_row = []
6        for c in range(len(triangle[r])):
7            next_row.append(triangle[r][c] + max(best[c], best[c + 1]))
8        best = next_row
9
10    return best[0]

This keeps the same runtime and reduces extra space to O(n).

Recovering the Actual Path

Euler 18 only asks for the max sum, but in real interviews and production analytics you may need the chosen path too.

1def max_sum_with_path(triangle):
2    dp = [row[:] for row in triangle]
3    pick = [[0] * len(row) for row in triangle]
4
5    for r in range(len(dp) - 2, -1, -1):
6        for c in range(len(dp[r])):
7            if dp[r + 1][c] >= dp[r + 1][c + 1]:
8                dp[r][c] += dp[r + 1][c]
9                pick[r][c] = c
10            else:
11                dp[r][c] += dp[r + 1][c + 1]
12                pick[r][c] = c + 1
13
14    path = [triangle[0][0]]
15    c = 0
16    for r in range(len(triangle) - 1):
17        c = pick[r][c]
18        path.append(triangle[r + 1][c])
19
20    return dp[0][0], path
21
22
23s, p = max_sum_with_path(triangle)
24print(s, p)

Path reconstruction adds small bookkeeping overhead and is often worth it for debugging.

Parsing Euler Input Text

Euler datasets are usually provided as multiline text. Parse once and reuse DP function.

1def parse_triangle(text):
2    lines = text.strip().splitlines()
3    return [list(map(int, line.split())) for line in lines]
4
5raw = """
675
795 64
817 47 82
918 35 87 10
10"""
11
12tri = parse_triangle(raw)
13print(max_path_sum(tri))

Separating parser from solver makes testing easier.

Relation to Euler 67

Project Euler 67 is the same triangle problem with much larger input. A brute-force solution that passes 18 will fail for 67, while bottom-up DP scales naturally.

That is one reason Euler 18 is often treated as an introduction to dynamic programming mindset.

Validation Strategy

Use small known triangles to verify correctness before running full problem input.

Test cases should include:

• one-row triangle
• triangles with ties
• triangles containing negative numbers
• larger random triangles compared against slower reference for small sizes

Negative values are important because greedy local choices can fail badly there.

Common Pitfalls

A common mistake is greedy choice at each step, always taking the larger immediate child. That does not guarantee global optimum.

Another issue is in-place mutation without awareness. If you mutate input triangle and reuse it later, results can become misleading.

Off-by-one errors with c + 1 are also frequent in manual loops. Unit tests on tiny triangles catch this quickly.

Some solutions forget edge cases such as one-row input and crash on indexing.

Finally, developers may optimize too early. Start with clear DP, then apply space optimization only if needed.

Summary

• Euler 18 is a maximum path sum problem best solved with dynamic programming.
• Bottom-up DP gives O(n^2) time and simple implementation.
• Space can be reduced to O(n) with a rolling-row approach.
• Path reconstruction is easy when you store child choices.
• The same approach scales directly to larger variants such as Euler 67.