Depth Against Density

A DP has states dp[i][r] with $1 \le i \le 10^6$ and $0 \le r \le 9999$ , and every transition is $O(1)$ . Instrumenting the recursion on the real inputs shows that from the start state only about 3000 of the $10^{10}$ states are ever reached. Limits: 2 seconds, 256 MB, and the default 8 MB stack.

Which implementation do you write?

Memoized recursion rewritten with an explicit stack of frames, because a dependency chain here can run $10^6$ deep and 8 MB does not hold that many frames.

Memoized recursion with a hash map keyed on (i, r). It computes about 3000 entries, and no path down the recursion can visit a state twice, so the depth cannot exceed the reachable count either.

Bottom-up over the whole table. An iterative sweep has no per-call overhead and no stack limit, and measuring reachability does not change how many cells the table has.

Bottom-up rolled to two rows of 10000 ints, which brings the footprint down to 80 KB.