the DP evaluation order

In a bottom-up dynamic program you fill a table cell by cell, and there is one rule you must never break: before you compute a cell, every cell it depends on must already hold its final value. The evaluation order is the sequence in which you visit the cells, chosen so that this rule always holds. It is the difference between building a wall brick by brick on a set foundation and trying to lay a brick in midair — get the order wrong and you read garbage from a cell you have not filled yet.

Think of the states as nodes in a graph, with an arrow from state X to state Y whenever computing X needs Y. A valid evaluation order is any topological order of this dependency graph: every state comes after all the states it points to. For one-dimensional DPs where dp[i] depends only on smaller indices, the order is just i increasing. For two-dimensional grid DPs where dp[i][j] depends on dp[i-1][*] and dp[i][j-1], filling rows top-to-bottom and within each row left-to-right works, because both predecessors are then already done. For interval DPs where dp[l][r] depends on shorter intervals inside [l, r], you iterate by increasing interval length so all shorter intervals are ready. The dependency structure dictates the order; you read it off the transition.

Top-down memoization sidesteps this entirely: recursion naturally computes a dependency before the state that needs it, so the call stack discovers a valid order for free — one reason beginners find memoization more forgiving. Bottom-up forces you to make the order explicit, which is both the burden and the benefit: it is the explicit order that lets you prove the rule holds, lets you compress memory by discarding cells you will never read again, and, crucially, only works if the dependency graph has no cycles. If state A needs B and B needs A, no order exists and the formulation is broken — a sign you must redefine the state.