Zadanie z dodawaniem wartości

Potrzebuję pomocy. Już nie wiem o co z tym chodzi mam do zrobienia takie zadanie:

Do celów testowych zbudowaliśmy schody składające się z N stopni. Każdy ze stopni przypisaną ma pewną liczbę punktów (od -500, 500 ). Poziomy Start i Finish (chodnik A i B) posiadają liczbę punktów równą 0. Robot może poruszać się po schodach pokonując na raz jeden lub dwa stopnie.
Opracuj dla robota algorytm schodzenia po schodach w taki sposób, aby suma punktów przyporządkowana stopniom, na których stanie po drodze była jak największa.
Zadanie:
Na wejściu funkcji downStairs otrzymasz tablicę T oraz liczbę elementów tablicy n. Liczba elementów tablicy odpowiada liczbie stopni schodów, natomiast wartości elementów odpowiadają liczbie punktów przyporządkowanych poszczególnym stopniom. Uwzględniając specyfikę poruszania się robota opisaną wyżej, niech funkcja downStairs zwrórc wartość najwyżej punktowanej trasy.

Wejście:
tablica punktów : int T[n]
liczba schodków : unsigned int n
gdzie : 0 ≤ n ≤ 50 oraz -500 ≤ T[n] ≤ 500

Wyjście:
Suma punktów T[ x ] dla optymalnej ścieżki

Przykład:

Tablica T[] n Wynik:
{ 3,-2,-3,1,5,-3,-2 } 7 5
{ 5, -3, -2, 1 } 4 4
{ 2, 2, 2, 2 } 4 8
{ 5, -1, 5, -1, -2 } 5 9
{ -1, -2, -3, -4, -5 } 5 -6

**Dobra napisałem taki program:

int downStairs( const int T[], unsigned n )
{
unsigned i = 0, j = 1, suma = 0;
while(j <= n){

    if (T[i] > T[j]){
        suma += T[i];
        i++;
        j += 1;
        
    }
    if (T[i] < T[j])
    {
        suma += T[j];
        i += 2;
        j += 2;
        
    }
    if (T[i] == T[j]){
        suma += T[i];
        i++;
        j += 1;
    }
   
    
}
return suma;

}

Ale on nie w pełni działa ktoś mi to wyjaśni? Oto wyniki mojego programu: NIE DZIALA TYLKO DLA n=5 I n=4
PASS downStairs( [ 3, -2, -3, 1, 5, -3, -2 ], 7 ) { return 5; } == 5
FAILED downStairs( [ 5, -3, -2, 1 ], 4 ) { return 53; } == 4
FAILED downStairs( [ 2, 2, 2, 2 ], 4 ) { return 56; } == 8
FAILED downStairs( [ 5, -1, 5, -1, -2 ], 5 ) { return 840969275; } == 9
FAILED downStairs( [ -1, -2, -3, -4, -5 ], 5 ) { return 840969256; } == -6
PASS downStairs( [ -1, -2, 1, -2, 1, -3, 4 ], 7 ) { return 5; } == 5
PASS downStairs( [ 2, -1, -3, 5, -4, 7 ], 6 ) { return 13; } == 13
PASS downStairs( [ -380, -148, 301, -351, 61, -306, -307, 312, 90, -211, -494, 315, -190, -46, -443, -494, -36, -131, 223, 498, 59, -499, 248, -56, 322, -363, -465, 422, -215, 148 ], 30 ) { return 1446; } == 1446**

Nie znam się, ale się wypowiem :P
Bez wygenerowania wszystkich możliwych ścieżek to się chybe nie obejdzie.

tajny_agent napisał(a):

Nie znam się, ale się wypowiem :P
Bez wygenerowania wszystkich możliwych ścieżek to się chybe nie obejdzie.

Myślę, że się obejdzie w złożoności istotnie niższej niż wykładnicza, którą proponujesz.

DawidD135 napisał(a):

Ale on nie w pełni działa ktoś mi to wyjaśni?

Bo jest to błędny algorytm.

Podpowiedź: DLa każdego stopnia (w kolejności od Start do Finish) obliczasz, jaką maksymalną wartość punktów można zdobyć, jeśli robot stawia stopę na tym stopniu i nie idzie dalej. By to obliczyć, wymagana jest znajomość tej wartości dla DWÓCH poprzednich stopni. (Przyda się funkcja max)

Wynik to wartość dla Finish.