Nie jestem w stanie złamać tego algorytmu - algorytmu

Właśnie ćwiczyłem jakieś pytanie od HackerEarth. Spróbowałem tego pytania, ale nie mogłem złapać logiki. Zgodnie z tagami obejmuje to rekursję programowania dynamicznego.

Czy ktoś może dowiedzieć się, jak odpowiedzieć na to pytanie i wyjaśnić mi je?

https://www.hackerearth.com/problem/algorithm/avoid-boredom/

Odpowiedzi:

Podstawowe programowanie dynamiczne. Z powodu wymogu zachowania pierwotnego zamówienia.

V[x,y] to maksymalna suma osiągnięta, jeśli wybrałeś już przedmioty, a ostatnia to x.

Oczywiście V[x,1] = 0 dla wszystkich x (wybranie jednego tematu nie daje ci nic za sumę).

V[x,y] = max_a(V[a,y-1] + abs(A[a] - A[x]), for a in y-1, x-1 To jest dla wszystkich innych, za których patrzysz za najlepszą opcję.

Rozwiązaniem jest max_x(V[x, M]).

W przypadku implementacji wystarczy upewnić się, że nie wybierzesz nieprawidłowych komórek (V [0, 3] powinno być nieprawidłowe, możesz „wybrać 3 elementy, jeśli ostatni to 0).