Two-dimensional Dynamic Programming
Memoized search on a grid
When there is no fill order to find, let the recursion discover it.
Key idea
Movement in every direction
Every grid table so far moved in one direction, which is what made row-by-row filling correct. When movement is allowed in all four directions, there is no such order: a cell can depend on its neighbor above and its neighbor below.
That looks circular and is not, provided the movement rule forbids returning. When each step must strictly increase, no cell can depend on itself through any chain, so the dependencies form a directed graph with no cycles.
Why it works
Stop finding an order and let recursion find it
Memoized recursion needs no fill order. It computes what it needs when it needs it, and the memo prevents recomputation. That is the whole reason to prefer it here.
The state is the cell. Its answer is the best achievable starting from it, and the transition takes the best over the neighbors that the rule allows moving to.
Which neighbors those are is worth seeing before writing anything. Below, one grid is listed cell by cell with the moves the rule permits out of each.
Gotcha
There is no visited set here
Written out, this looks like the grid searches from U10 and U12, and it needs no visited marking at all. That is correct and worth pausing on.
The strictly-increasing rule already prevents revisiting: a path cannot return to a cell it has left, because that would require decreasing. Adding a visited set would be harmless for correctness and would defeat the memo, since a cell's answer would then depend on the path taken to reach it and could no longer be cached.
That is the important point. Memoization is only valid when the answer for a state depends on the state alone. If it depended on the path, the memo would be wrong.
Tip
Why equal values are not a problem
The comparison is strict, so a plateau of equal cells has no moves between them and every one of them answers 1. Notice above that neither 9 offers a move to the other, and neither 1 in the bottom row offers a move to the other.
If the rule allowed equal steps, cycles would become possible, the dependency graph would no longer be acyclic, and this approach would recurse forever. Checking that the rule actually forbids cycles is the precondition for using it.
Cost
Cost
Each cell's answer is computed once and examines four neighbors, so O(rows times cols) time and the same space for the memo plus the recursion depth.
Without the memo it would be exponential, since the same cell would be recomputed once per path reaching it. The memo is what turns a search into a table.
Edge cases
Recursion depth on a large grid
The recursion can go as deep as the longest increasing path, which on a large grid can exceed Python's limit. Mention it, and note that an explicit topological order by cell value would avoid recursion entirely if the constraints demanded.
For interview-sized inputs the recursion is fine and clearer. This is the same trade as the flood-fill lesson in U12.
Predict the output: does the answer depend on how you arrived?
The same cell is reached along two different routes. Type the three lines it prints.
Longest Increasing Path In A Matrix
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.