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

Ne bazam pe faptul ca $A{~i-1~} &le; A{~i~}$, pentru orice {~i~}. De asemenea, vom face cateva calcule intermediare de complexitate <tex> O(M) </tex> pentru fiecare segment, astfel:

De asemenea, 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$.

Acum, nu ne mai ramane de facut decat sa notam ca $d[i][j] = y[j]$ daca $X[i] ≤ j ≤ Y[i]$, sau $infinit$ daca nu.

De observat ca aceste calcule pot fi facute cu un singur sir $d[1...M]$, nefiind nevoie nici de tabloul bidimensional $d$, nici de $x$ sau $y$.

De observat ca aceste calcule pot fi facute cu un singur sir $d[1...M]$, nefiind nevoie nici de tabloul bidimensional $d$, nici de $x$ sau $y$.
 
+Observatie+: Solutia nu se foloseste de faptul ca $A{~i~} ≤ A{~i+1~}$. Acest detaliu este unul care sa simplifice vizualizarea panzei de paianjen