In a triangular cost pyramid, why is filling from the bottom row upward simpler than from the apex?

## The shape A tiered surcharge pyramid has one entry in the top row, two in the next, three in the one after, and so on: row `i` holds `i+1` entries. From entry `j` of row `i` you may descend to entry `j` or entry `j+1` of row `i+1` — a step straight down or a step down-and-right. The task is the cheapest total from the apex to any entry of the base. It is a grid problem wearing a triangular hat, and the interesting content is that the two obvious fill directions are not equally pleasant. ## Downward: irregular in-edges Going top to bottom, define `best[i][j]` as the cheapest total from the apex down to `(i, j)`. Its predecessors are `(i-1, j-1)` and `(i-1, j)`. For a cell in the middle of a row both exist. For `j = 0` the first does not exist — the leftmost entry of every row can only be reached by descending straight down the left flank. For `j = i` the second does not exist, symmetrically. So the transition is three cases instead of one, and every case is a place to write an off-by-one. Worse, the answer is not in any single cell: you must scan the entire bottom row and take the minimum at the end. ## Upward: regular out-edges Go bottom to top instead and redefine `best[i][j]` as the cheapest total from `(i, j)` down to the base. Now the recurrence reads ``` best[i][j] = cost[i][j] + min(best[i+1][j], best[i+1][j+1]) ``` and it has no exceptions at all. Every cell that is not on the base has exactly two children, and `j+1` is always a valid index in the row below because that row is one entry wider. Seed the base row with its own costs and sweep upward; the answer is `best[0][0]`, a single lookup with no final scan. The asymmetry is structural, not stylistic: in this shape *out-degree is uniform and in-degree is not*. Choosing the direction with the uniform degree is what removes the boundary cases. That is the transferable lesson — when a DP has irregular in-edges, check whether reversing the direction gives you regular out-edges instead. ## Cost, and what does not change Both directions touch every one of the roughly `n^2 / 2` entries once and do constant work each, so both are `O(n^2)` time. Neither is asymptotically better. The upward sweep also compresses naturally to one row of scratch as wide as the base: keep an array holding the row below, and update in place with `scratch[j] = cost[i][j] + min(scratch[j], scratch[j+1])` sweeping `j` upward. Each entry is read before it is overwritten, so the in-place update is safe, and the extra space drops to `O(n)`. ## The claim not to overreach on "Bottom-up always beats top-down" is wrong as a general statement, and interviewers listen for it. Direction is chosen per problem shape. Recursion with memoization — logically the downward direction, evaluated lazily — wins whenever only a small fraction of the state space is actually reachable, because it computes only the states it needs, while a bottom-up sweep fills everything unconditionally. A dense pyramid needs every entry, so the sweep wins on constant factors and avoids recursion depth proportional to the number of rows, which is itself part of the space cost. On a sparse or heavily constrained state space the same reasoning points the other way. ## What an interviewer is checking Three things. First, that you noticed the in-degree asymmetry rather than defaulting to whichever direction you saw first. Second, that you can state the recurrence and the seed for your chosen direction without hand-waving the indices — `j` and `j+1` below, not `j-1` and `j`. Third, that you know the direction is a code-clarity and boundary-bug decision rather than a performance one, and you can say so plainly instead of claiming a speedup that is not there.