We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all points exactly once.
A tour is pyramidal if it is of the form: $(n\rightarrow 1 \rightarrow n)$ such that all points in $n\rightarrow 1 $ are decreasing and all points in $1\rightarrow n$ are increasing (example: $(6,5,4,2,1,3,6)$.
I want to find a solution to this problem using Dynamic Programming where $f(i,j)$ is the length of the shortest pyramidal path $(i\rightarrow 1 \rightarrow j)$.
My solution is the following:
$f(i,j)=\begin{Bmatrix} min_{1\leq k<i}(f(k,1)+l(i,k)),\text{when } j=1 \\ min_{1\leq r<j}(f(1,r)+l(r,i)),\text{when } i=1 \\ min_{\begin{matrix} 1\leq k<i \\1\leq r<j,\end{matrix} }(f(k,r)+l(i,k)+l(r,j),\text{when } j>1, i>1 \end{Bmatrix}$
Assuming that $f(1,1)=0$ we find the shortest possible tour by compution $f(n,n)$ is this correct?