Qualcuno può aiutarmi a capire quest'algoritmo in pseudocodice?
Questa è la traccia:
Si consideri una scacchiera M di m righe (numerate 0, . . . ,m - 1) ed n colonne
(numerate 0, . . . , n - 1) in cui la cella (i, j) contiene l’intero positivo M(i, j). Un
cammino legale sulla scacchiera `e un cammino da una casella della riga 0 ad una
casella della riga m - 1 che ha la seguente caratteristica: se ci si trova nella casella
(i, j) (riga j e colonna i) con j < m - 1, al prossimo passo si pu`o visitare o la casella
((i - 3) mod n, j + 1) o la casella ((i + 3) mod n, j + 1). Il valore di un cammino
legale `e semplicemente la somma degli interi nelle caselle visitate.
Si progetti un algoritmo che riceve in input una scacchieraM e calcola il valore massimo
di un cammino legale in M.
SOLUZIONE:
Scacchiera(M)
for i = 0 to n - 1
V (i,m - 1) = M(i,m - 1);
for j = n - 2 downto 0
for i = 0 to n - 1
V (i, j) = M(i, j) + max{V ((i - 3) mod n, j + 1), V ((i + 3) mod n, j + 1)}.
Vmax= V (0, 0);
for i = 1 to n - 1
Vmax= max{Vmax, V (i, 0)};
return Vmax;