The Longest Climb Across a Grid
From any cell you may step to a side-adjacent cell (up, down, left or right) whose value is STRICTLY GREATER. Print the length of the longest such path, counted in CELLS.
9 9 4
6 6 8 -> 4 1 -> 2 -> 6 -> 9
2 1 1
The path may start anywhere and end anywhere, and diagonal steps are not allowed.
## Why there is no fill order
Every grid DP so far has had a direction: row by row, or by increasing interval length. Here a cell depends on its four neighbours, and which of them are smaller depends on the VALUES, not on the positions. There is no order over the grid that visits dependencies first.
Two ways out.
Memoised recursion. Define go(r, c) as the longest path starting at (r, c), recurse
into strictly larger neighbours, and cache. The recursion discovers the order itself, which
is exactly what memoisation buys over tabulation.
Sort the cells. Process cells in increasing value order, so every strictly smaller neighbour is already final. That recovers a fill order by constructing one.
The first is shorter. The second is worth knowing because it is what you do when recursion depth is a problem.
## Why it always terminates
Each step strictly increases the value, so no cell can repeat and there are no cycles. The
grid is a directed ACYCLIC graph and go is well defined with no visited set needed.
That is the whole reason the problem is a DP rather than a search: strictness makes the
graph acyclic. With >= instead of >, equal neighbours would form cycles and the
recursion would not terminate.
1 1 / 1 1 answers 1 and is the test for that: all four cells are equal, so no step is
legal and every path is a single cell.
## The answer is over all starts
Take the maximum of go(r, c) across every cell. The longest path need not begin at a
local minimum that you could identify cheaply, so all starts have to be tried, and the memo
is what keeps that from costing anything.
## Counting cells, not steps
A single cell is a path of length 1, not 0. 1 as a one-cell grid answers 1.
## Cost
Time O(m n): each cell is computed once and looks at four neighbours. Space O(m n) for
the memo, plus recursion depth up to m n in the worst case, which is why an explicit
stack or the sorted order is the safer choice at the upper bound.