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?

  • 2
    $\begingroup$ Not research level? $\endgroup$ – Mahdi Cheraghchi 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