I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem.

From what I see, I need to sort the x-coordinates of the given set of points and then form a optimal path from the smallest x coordinate to the largest x coordinate.

For eg. (x1,y1) (x2,y2) ...(xn,yn) are sorted points. Isnt the optimal path simply x1,x2,x3,...xn-1,xn,xn-1,...,x3,x2,x1.

What am I missing here? How does dynamic programming come into picture here?


closed as off topic by Kaveh Aug 17 '11 at 15:50

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Not research level? $\endgroup$ – MCH Aug 17 '11 at 15:24
  • 1
    $\begingroup$ I have not consulted the book and I do not know which problem you are talking about, but if it is an exercise in the Introduction to Algorithms, then probably it is not suitable on cstheory.stackexchange.com. $\endgroup$ – Tsuyoshi Ito Aug 17 '11 at 15:31
  • $\begingroup$ Vote to close. This is a homework exercise in Cormen, et al, and a complete answer can be found on the first link via Google by searching for the problem name. $\endgroup$ – Daniel Apon Aug 17 '11 at 15:48
  • 1
    $\begingroup$ I am closing the question as off-topic, the question is probably more suitable for Math.SE, please refer to the FAQ to understand the scope of the site. $\endgroup$ – Kaveh Aug 17 '11 at 15:49