[Algoritmi]Programmazione Dinamica

[HeroGian]

Salve a tutti, volevo chiedervi un piccolo aiuto riguardo il seguente problema da risolvere per mezzo della programmazione dinamica:
"Supponiamo di avere una scacchiera con nxn celle ed una pedina che parte dall'estremità inferiore della tabella (x, n).
La pedina ha tre mosse a disposizione: movimento in alto, alto a destra e alto a sinistra.
Supponendo di avere dei numeri interi per ogni cella (peso), scrivere un algoritmo basato sulla programmazione dinamica che massimizzi il peso."

p(x, y) = peso relativo ad ogni cella

L'equazione di ricorrenza che ho scritto è la seguente.. ma non sono per niente sicuro del risultato

$P(n) = {(p(x, y) rArr y = n ),(max{ p(x-1, y-1), p(x+1, y-1), p(x, y-1) } rArr otherwise):}$

[apatriarca]

Qual'è l'obiettivo dell'algoritmo? Non mi è chiaro il peso di cosa debba insomma massimizzare. Devi raggiungere una qualche cella particolare? Le devi raggiungere "tutte" (cioè trovare il percorso che massimizzi il peso tra la cella di partenza e ogni altra)? Sei certo che si voglia proprio massimizzare? Normalmente i pesi si vogliono minimizzare quando si cerca un percorso tra due celle. Devi insomma fare altro?

P.S. Le implicazione sono da scrivere al massimo al contrario, ma il modo corretto di scriverlo è il seguente (se premi con il tasto destro sopra la formula ti permette di vedere cosa ho inserito):
\[
P(n) =
\begin{cases}
p(x, y) & y = n \\
\max \{ p(x - 1, y - 1), p(x + 1, y - 1), p(x, y-1) \} & \text{otherwise}
\end{cases}
\]

[HeroGian]

in pratica devo partire da una cella qualsiasi dell'ultima riga della scacchiera e devo arrivare ad una qualsiasi della prima riga, facendo in modo di massimizzare la somma dei numeri presenti in ogni cella che visito..
ahh si capito.. volevo scrivere "per y = n" ma me lo metteva attaccato xd

più che altro non so come ragionare per scrivere l'ultima riga della ricorrenza, quella che tiene conto delle 3 possibili scelte..

[hamming_burst]

Quindi basta trovare un cammino dalla base della scacchiera all'ultima riga che sia massimo rispetto al peso della mossa?