The standard approach is to use a recursive solution known as dynamic programming (a type of memoization).
Your problem, computing the discrete Fréchet distance, is very close to a technique known as Dynamic Time Warping (DTW). In this context, your distance grid would be known as the ground distance matrix, defined by
$$d_{p,q}=||P_p-Q_q||$$
If we define $D_{p,q}$ to be the discrete Fréchet distance between $[P_1,\ldots,P_p]$ and $[Q_1,\ldots,Q_q]$, then the following recursion holds:
$$D_{p,q}=\max\{d_{p,q},\min\{D_{p-1,q},D_{p,q-1},D_{p-1,q-1}\}\}$$
That is, the maximum inter-curve distance either occurs at the current pair of $(p,q)$ points, or it occured prior to this along the path (i.e. further back). In the latter case, the no-backtracking requirement means that the least-cost path must have arrived at $(p,q)$ from one of the three neighbors $(p-1,q),(p,q-1),(p-1,q-1)$.
To compute the distance, you fill up the table of $D_{p,q}$ values iteratively, beginning at $D_{1,1}$ and ending at $D_{m,n}$ (where $n-m$ in your case).
The Wikipedia page links to a paper describing the details of this approach:
Eiter, T., & Mannila, H. (1994). Computing discrete Fréchet distance. Tech. Report CD-TR 94/64, Information Systems Department, Technical University of Vienna.
(Note that Dynamic Time Warping is exactly the same, except the $\max$ operation is replaced by $+$.)
Best Answer
Credits to @Dougal for his comment-answer:
The decay part is interesting: $e^{1/x}$ is a lot bigger than $1/x$, so ${\sum_k e^x}$ will be a lot bigger than ${\sum_k 1/x}$, considering the value of $k$.