15-1 Longest simple path in a directed acyclic graph

Suppose that we are given a directed acyclic graph $G = (V, E)$ with real-valued edge weights and two distinguished vertices $s$ and $t$ . Describe a dynamic-programming approach for finding a longest weighted simple path from $s$ to $t$. What does the subproblem graph look like? What is the efficiency of your algorithm?

Since any longest simple path must start by going through some edge out of $s$, and thereafter cannot pass through $s$ because it must be simple, that is,

$$\text{LONGEST}(G, s, t) = 1 + \max_{s∼s'} \text\{LONGEST(G|_{V\backslash\{s\}}, s', t)\},$$

with the base case that if $s = t$ then we have a length of $0$.

A naive bound would be to say that since the graph we are considering is a subset of the vertices, and the other two arguments to the substructure are distinguished vertices, then, the runtime will be $O(|V|^2 2^{|V|})$. We can see that we will actually have to consider this many possible subproblems by taking $|G|$ to be the complete graph on $|V|$ vertices.