Suppose we have 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 ?nding a longest weighted simple path from s to t. (A path is simple if all vertices in the path
are distinct.) What does the subproblem graph look like? What is the e?ciency of your algorithm?