Hint la problema cu Dinamica!

[•gerd13]

Avem o matrice N*N. Trebuie sa alegem un sir care are suma maxima cu urmatoarele conditi: pornim de pe prima coloana-> putem merge in fata, fata sus, fata jos. De pe fiecare coloana trebuei sa avem doar un singur element!
ex:

Cod:

4
2 -3 4 -1
-4 -2 15 -7
12 -6 -9 7
3 6 2 5

Daca ma puteti ajuta cu un hint! Am incercat eu cu DP dar nu mi-a iesit!
Multumesc!

[•Cristian1997]

Construiesti o matrice best[ i ][ j ] - suma maxima a unui sir care se termina pe pozitia (i, j)

Cod:

best[i][1] = a[i][1] (prima coloana)

best[i][j] = a[i][j] + max(best[i-1][j-1], best[i][j-1], best[i+1][j-1])

parcurgerea se face pe coloane, nu pe linii

raspunsul este maximul dintre best[ i ][ n ], 1<=i<=n

pentru reconstituire trebuie o matrice auxiliara, pred[ i ][ j ] care retine linia elementului precedent celui de pe pozitia (i, j)

[•gerd13]

Multumesc! Am rezolvat problema! Eu greseam la initializarea primei coloane! Si atunci nici recurenta nu era corecta!