h2. <tex> O(N * M) </tex> - $100$ de puncte

De asemenea, vom face cateva calcule intermediare de complexitate <tex> O(M) </tex> pentru fiecare segment, astfel:

Vom face cateva calcule intermediare de complexitate <tex> O(M) </tex> pentru fiecare segment, astfel:

Mai intai calculam $x[j]$ care e costul minim sa ajung in punctul $j$ pe segmentul $i - 1$, stiind ca prin punctul $j$ trec, pe punctea de lungime $A[j]$, pe segmentul $i$. Pentru inceput, $x[j] = d[i - 1][j]$, daca $X[i - 1] ≤ j ≤ Y[i - 1]$, sau $infinit$ daca nu. Apoi facem o parcurgere de la $2$ la $M$ si zicem $x[j] = min {x[j], x[j - 1] + 1}$. Apoi facem o parcurgere de la $M - 1$ la $1$ si recalculam $x[j] = min {x[j], x[j + 1] + 1}$. Astfel, simulam o plimbare pe segmentul $i - 1$.