Wanted
Problema se va rezolva folosind programare dinamica. Vom considera satele sortate dupa ordonata X. Vom construi matricile
- Ai,j - distanta minima parcursa pentru a rezolva intervalul i...j si daca ne-am afla initial in satul i-1
- Bi,j - distanta minima parcursa pentru a rezolva intervalul i...j si daca ne-am afla initial in satul j+1
Relatia de recurenta se poate observa usor. Fixam pe rand fiecare sat k pe care il vom vizita prima oara si ne uitam la Ak+1,j si Bi,k-1, alegand maximul dintre cele doua (luam in coniderare doar cazul cel mai defavorabil). Dintre toate posibilitatile de a alege k o vom retine pe cea care da rezultatul minim.
Pentru a stabili rezultatul fixam din nou k, primul sat vizitat si alegem minimul dintre toate posibilitatile.
Complexitatea algoritmului va fi O(n3).
