Longest increasing path in matrix — why DFS + memo beats brute force?

Question presented to candidate: "Given an m by n matrix of integers, return the length of the longest strictly increasing path, moving only up, down, left or right. Start with the brute force, explain why it is slow, then make it fast. Please write it in Python."

What a strong answer should cover:

• The model: every cell is a node with an edge to each strictly larger neighbour; strictly increasing means no cycles, so it is a DAG, and the answer is its longest path.
• Brute force: DFS from every cell exploring every increasing path is exponential, because the same cells are re-explored from many starts.
• DFS + memo: the longest path starting at a cell does not depend on how you reached it, so cache it; each cell is solved once and each edge is followed once: O(m·n) time and space.
• No visited set is needed (values strictly increase, so a path cannot revisit a cell), and the alternative is Kahn topological layering, which avoids recursion.
• Python specifics: a nested dfs closing over a memo list of lists (or functools.lru_cache(maxsize=None) on a nested function), and the recursion limit: a 1 x 1000 strictly increasing row already raised RecursionError, so large inputs need the iterative topological version.

Clarifying questions expected:

• "Strictly increasing, or is equal allowed?" (equal values would create cycles and break memoisation)
• "Only four directions, no diagonals? Can the matrix be empty?"

Code / implementation expected: Yes — longest_increasing_path(matrix) in Python with DFS + memo; the Kahn layering version is a bonus.