435. The Longest Climbing Path

Each cell of a grid holds a height. From a cell you may step to one of its four side neighbours, and only to a STRICTLY greater height. Print the number of cells on the longest such path. A single cell is a path of length 1.

9 9 4 6 6 8 -> 4 the path 1, 2, 6, 9 up the left side 2 1 1

There is no obvious order in which to fill a table, and that is what makes this the clearest memoisation problem in the file. The dependencies run from low cells to high ones, which follows the VALUES rather than the geometry, so neither row-major nor column-major order works.

Two routes.

Memoise the recursion:

best(r, c) = 1 + max over strictly higher neighbours of best(neighbour)

and take the largest over all starting cells. Each cell is computed once and cached, so the whole thing is O(rows * cols).

Or sort the cells by height and fill in that order, which makes the dependency order explicit. Both are correct; the first needs no sort and is shorter.

Note that no visited set is needed, and that is worth understanding rather than copying. Because every step strictly increases the height, no path can revisit a cell, so there are no cycles and a plain cache is safe. Equal neighbours are not steps, which is what keeps that true and why the grid of all-equal values answers 1.

Constraints - `1 ≤ r, c ≤ 200` - `0 ≤ height ≤ 1000000000`