Maximum number of points that two paths can reach
The problem, restated and generalized: given a finite set $S$ equipped with a partial order $\le$, find chains $C_1, C_2 \subseteq S$ maximizing $\lvert C_1 \cup C_2 \rvert$. The question is about the case where $S \subseteq \mathbb R_+^2$ and $(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$.

Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$\bigl((0,0),(0,0)\bigr) &lt; \bigl((1,0),(0,0)\bigr) &lt; \bigl((2,0),(0,0)\bigr) &lt; \bigl((2,0),(1,0)\bigr),$$ so this notion of best does not have optimal substructure.

Instead, we look for chains in the set $T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement.

Lemma 1 (no retracing). Let $C \subseteq T$ be a chain and define $C_1 := \{x \mid (x, y) \in C\}$ and $C_2 := \{y \mid (x, y) \in C\}$. For all $z \in S$, we have $z \in C_1 \cap C_2$ if and only if $(z, z) \in C$.

Proof. The if direction is trivial. In the only if direction, for all $z \in C_1 \cap C_2$, there exist $x, y \in S$ such that  $(x, z), (z, y) \in C$. Since $C$ is a chain, $(x, z) \le (z, y) \vee (z, y) \le (x, z)$. Assume symmetrically that $(x, z) \le (z, y)$, which implies that $x \le z \le y$. We know by the definition of $T$ that $x \nless z \wedge z \nless y$, so $x = z = y$, and $(z, z) \in C$.

Lemma 2 (existence of restricted best chain). For all chains $C_1, C_2 \subseteq S$, there exists a chain $C \subseteq T$ such that $C_1 \subseteq \{x \mid (x, y) \in C\} \subseteq C_1 \cup C_2$ and $C_2 \subseteq \{y \mid (x, y) \in C\} \subseteq C_1 \cup C_2$.

Proof (revised). We give an algorithm to construct $C$. For convenience, define sentinels $\bot, \top$ such that $\bot &lt; x &lt; \top$ for all $x \in S$. Let $C_1' := C_1 \cup \{\top\}$ and $C_2' := C_2 \cup \{\top\}$.


Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.
Let $x'$ be the next element of $C_1$, that is, $x' := \inf \{z \mid z \in C_1' \wedge x &lt; z\}$. Let $y'$ be the next element of $C_2$, that is, $y' := \inf \{w \mid w \in C_2' \wedge y &lt; w\}$.
If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.
If $y &lt; x' &lt; y'$, set $(x, y) := (x', x')$ and go to step 9.
If $y \nless x' &lt; y'$, set $x := x'$ and go to step 9. Note that $x &lt; x' \wedge x \nless y$ implies that $x' \nless y$.
If $x &lt; y' &lt; x'$, set $(x, y) := (y', y')$ and go to step 9.
If $x \nless y' &lt; x'$, set $y := y'$ and go to step 9. Note that $y &lt; y' \wedge y \nless x$ implies that $y' \nless x$.
This step is never reached, as the conditions for steps 3&ndash;7 are exhaustive.
If $x \ne \top$ (equivalently, $y \ne \top$), set $C := C \cup \{(x, y)\}$ and go to step 2.


Dynamic Program. For all $(x, y) \in T$, compute $$
D[x, y] := \sup\biggl(\Bigl\{D[z, w] + [x \ne z] + [y \ne w] - [x = y] \mathrel{\Bigl|\Bigr.} (z, w) \in T \wedge (z, w) &lt; (x, y)\Bigr\} \cup \bigl\{2 - [x = y]\bigr\}\biggr),
$$
where $[\textit{condition}] = 1$ if $\textit{condition}$ is true and $[\textit{condition}] = 0$ if $\textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.