Esercizio matrice di programmazione dinamica [chiuso]

1

Mi sto esercitando con la programmazione dinamica e sto cercando di risolvere questo esercizio link ma non riesco a capire come utilizzare la programmazione dinamica.

Il mio ragionamento è di usare una tabella T[n][m] per memorizzare i risultati e in ogni cella per trovare il valore massimo da percorrere (corrispondente a una cella).

Usando l'esempio mostrato nel link: come faccio a sapere alla prima cella [0][0] di andare a " 3 " invece di " 5 "? Usando il mio ragionamento la scelta è di andare a " 5 " ma è un cattivo modo

    
posta Haring 15.06.2016 - 11:34
fonte

1 risposta

0

Per rispondere alla tua domanda su come sapere quale rotta scegliere, devi fare la scelta che massimizzerà il tuo punteggio accumulato. Quindi nel tuo esempio, se stai cercando di decidere tra una rotta che ti dà 5 e una che ti dà 3, scegli la più grande (5).

Il tuo ragionamento sull'uso di una tabella per utilizzare la programmazione dinamica per questo problema è corretto. Mentre calcoli i valori della tabella, inseriscili. Quando ti imbatti in un calcolo che hai già eseguito e memorizzato nella tua tabella, sarai in grado di accedere al calcolo memorizzato in precedenza a quella cella nella tabella anziché calcolandolo una seconda volta.

    
risposta data 15.06.2016 - 17:55
fonte

Leggi altre domande sui tag