The solution seems to be working with an unweighted graph (or a graph where all the weights are 1). But the problem says our input has real-valued edge weights. I believe the correct solution has the same underlying idea, but I don't think it's exactly this.
After stating the naive bound, the solution claims that we must consider this many subproblems in the case of the complete graph on |V| vertices. But, the complete graph on |V| is NOT a directed acyclic graph.
This problem explicitly states that we are supposed to "Describe a dynamic-programming approach..." and it's in the dynamic programming section. So I'm pretty sure that the solution should use dynamic programming.
The solution seems to be working with an unweighted graph (or a graph where all the weights are 1). But the problem says our input has real-valued edge weights. I believe the correct solution has the same underlying idea, but I don't think it's exactly this.
After stating the naive bound, the solution claims that we must consider this many subproblems in the case of the complete graph on |V| vertices. But, the complete graph on |V| is NOT a directed acyclic graph.
This problem explicitly states that we are supposed to "Describe a dynamic-programming approach..." and it's in the dynamic programming section. So I'm pretty sure that the solution should use dynamic programming.