[Algoritmi] Problema esercizio Prog. Dinamica

[alexiousus7]

Salve ragazzi, innanzitutto volevo fare i complimenti alla community perchè oltre ad essere attiva è anche molto preparata a quanto ho visto

Dunque sono iscritto ad ing. gestionale ma sono alle prese con l'esame di algoritmi ( scelto da me )
Ho alcuni problemi nel risolvere però un esercizio di programmazione dinamica:
Vi scrivo la traccia:
In una (ignota) localita’ sciistica, vi sono n stazioni s 1 , s 2 , ···, s n , collegate tra loro da piste da
sci. Dalla stazione s 1 , in vetta alla montagna, e’ possibile arrivare alla stazione s n a valle in vari
modi. Poiche’ le stazioni s 1 , s 2 , ···, s n , sono ordinate secondo la loro altezza decrescente, una
pista che parte da s i arriva in una stazione s j , con j > i; inoltre per ogni 1 ≤ i < j ≤ n c’e’ una
pista da s i a s j a cui e’ associato un tempo di percorrenza t i,j . Poiche’ le piste hanno diverso
grado di difficolta’, e’ possibile che per andare da s i a s j , si impieghi meno tempo utilizzando
piu’ piste collegate che non quella diretta.
Si consideri il problema di determinare il tempo minimo per andare da s 1 ad s n , avendo in
input i tempi di percorrenza t i,j ,
a) Indicare qual e’ il tempo di esecuzione di un algoritmo di ”forza bruta” che risolve il problema.
b) Descrivere un algoritmo di programmazione dinamica per lo stesso problema. Analizzare la
complessita’ dell’algoritmo proposto e confrontarla con quella del punto a).

[apatriarca]

Non hai proprio alcuna idea? Neanche per il primo punto? Come potresti risolvere il problema usando la forza bruta?