h1(#Twoton). 'G. Twoton':problema/twoton

Obesrvam ca functia adecvat denumita $wtf()$, odata apelata de la pozitia $i$, dupa un anumit numar de pasi se va intoarce la pozitia $i$ si nu va mai ajunge niciodata la $i + 1$. De aici ne vine ideea de a calcula, pentru fiecare pozitie $i, 0 <= i < N$, doua valori: $steps[i] = cati pasi face functia pana se intoarce in valoarea i$ si $ret[i] = ce valoare returneaza wtf(i)$. Evident, $steps[N - 1] = 1$, iar $ret[N - 1] = V[N - 1]$. Parcurgem descrescator pozitiile, iar pentru pozitia $i$, $0 <= i < N - 1$, vom calcula cele doua valori astfel: $steps[i]$ se initializeaza cu $1 + steps[i + 1]$ (functia cheama la inceput $wtf(i + 1)$). Apoi, ne uitam la $ret[i + 1]$. Daca acesta este mai mare sau egal cu $V[i]$, recursivitatea pe acest nivel se sfarseste, setam $ret[i] = V[i]$ si continuam. Altfel, $wtf(i + 1)$ se mai apeleaza odata, deci $steps[i] += steps[i + 1]$, iar $ret[i] = ret[i + 1]$. Raspunsul se va gasi in $steps[0]$.

Obesrvam ca functia adecvat denumita $wtf()$, odata apelata de la pozitia $i$, dupa un anumit numar de pasi se va intoarce la pozitia $i$ si nu va mai ajunge niciodata la $i + 1$. De aici ne vine ideea de a calcula, pentru fiecare pozitie $i, 0 <= i < N$, doua valori: $steps[i] = cati pasi face functia pana se intoarce in valoarea i$ si $ret[i] = ce valoare returneaza wtf(i)$. Evident, $steps[N - 1] = 1$, iar $ret[N - 1] = V[N - 1]$. Parcurgem descrescator pozitiile, iar pentru pozitia $i$, $0 <= i < N - 1$, vom calcula cele doua valori astfel: $steps[i]$ se initializeaza cu $1 + steps[i + 1]$ (functia cheama la inceput $wtf(i + 1)$). Apoi, ne uitam la $ret[i + 1]$. Daca acesta este mai mare sau egal cu $V[i]$, recursivitatea pe acest nivel se sfarseste, setam $ret[i] = V[i]$ si continuam. Altfel, $wtf(i + 1)$ se mai apeleaza odata, deci $steps[i] += steps[i + 1]$, iar $ret[i] = ret[i + 1]$. Raspunsul se va gasi in $steps[0] $.

Complexitate timp: $O(N)$.
Complexitate spatiu: $O(N)$.