Introduction

The maximum-route-cost problem in a numeric pyramid asks for the largest possible sum from the top row to the bottom row. Although the movement rule is simple, a greedy choice can fail, so the standard solution is dynamic programming.

Problem Definition

A pyramid such as the one below lets you move from each number to one of the two adjacent numbers in the next row.

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

A valid path starting at 3 might be 3 -> 7 -> 4 -> 9, giving a total of 23. The goal is to find the maximum total among all valid paths.

At first glance, picking the larger child at each step seems reasonable. That approach is not reliable because a smaller local choice can lead to a larger total deeper in the pyramid.

Bottom-Up Dynamic Programming

The cleanest solution works from the bottom row upward. For each cell, compute the best total obtainable from that cell down to the base. The recurrence is:

best[row][col] = pyramid[row][col] + max(best[row + 1][col], best[row + 1][col + 1])

The last row is already optimal because there is nowhere else to go. Once you know the best totals for row r + 1, you can compute row r.

For the sample pyramid:

• row 3 stays 8 5 9 3
• row 2 becomes 10 13 15
• row 1 becomes 20 19
• row 0 becomes 23

So the answer is 23.

Python Example

This implementation copies the pyramid so the original input stays unchanged.

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

The running time is O(n^2) for a pyramid with n rows, because each cell is processed once. The extra space in this version is also O(n^2) because of the copied table.

Space Optimization

You can reduce memory usage by storing only one working row. Since each row depends only on the row below it, a single list is enough.

1def max_route_cost_optimized(pyramid):
2    best = pyramid[-1][:]
3
4    for row in range(len(pyramid) - 2, -1, -1):
5        for col in range(len(pyramid[row])):
6            best[col] = pyramid[row][col] + max(best[col], best[col + 1])
7
8    return best[0]

This keeps the same time complexity while reducing extra space to O(n).

Recovering the Actual Path

If you need the path and not only the total, store decisions while computing the DP table. One approach is to keep a second structure that records whether the left or right child gave the larger total. After the table is complete, walk from the top using those recorded choices.

That detail is important in interview problems and real applications where the route itself matters, not just the score.

Why Greedy Fails

Suppose the top of a pyramid has children 9 and 8. A greedy algorithm picks 9, but that side may lead into small numbers while the 8 side leads into much larger totals. Dynamic programming works because it accounts for the full future cost of each branch before choosing.

Whenever a problem has overlapping subproblems and an optimal result can be built from optimal sub-results, dynamic programming is the right tool.

Common Pitfalls

• Using a greedy choice at each row can produce the wrong answer. Local maxima are not guaranteed to lead to the best overall path.
• Updating rows from top to bottom with the bottom-up recurrence uses values that have not been computed yet. The bottom-up method must start near the base.
• Modifying the original pyramid in place can surprise callers who reuse the input later. Copy the data unless mutation is intentional.
• Forgetting that row r has exactly r + 1 values often causes index mistakes. Respect the triangular structure in your loops.
• Returning only the score when the caller needs the path leads to a partial solution. Record decisions during DP if the route itself matters.

Summary

• The maximum route cost in a numeric pyramid is a classic dynamic-programming problem.
• The standard recurrence adds each value to the larger of its two children.
• A bottom-up solution runs in O(n^2) time.
• You can reduce extra memory to O(n) by reusing one working row.
• Dynamic programming is correct here because greedy selection does not reliably find the best path.