Visa version
Version skapad av Viggo Kann 2016-09-15 22:13
Visa
< föregående
|
nästa >
Jämför
< föregående
|
nästa >
Dynamisk programmering 2.2
- Frågan var:
Vad är lämpliga dellösningar för en dynamiskprogrammeringsalgoritm för triangelstigsproblemet?
a) V[i,j]=värdet på bästa stigen från toppen ner till elementet
Dessa dellösningar fungerar för dynamisk programmering, men rekursionen blir ganska krånglig, eftersom den kommer att se olika ut för element inuti triangeln, på vänsterkanten och på högerkanten.
b) V[i,j]=värdet på bästa stigen från toppen till botten som passerar elementet
Detta fungerar inte som dellösningar eftersom det inte går att bygga en rekursion på dom.
c) V[i,j]=värdet på bästa stigen från elementet ner till botten
Dessa dellösningar fungerar och ger en enkel rekursion, så c) är att föredra. - Nästa fråga gäller steg 2 för samma problem, där dellösningarna väljs som i c) ovan.
Basfallen för rekursionen är V[n,j]=
Rekursionssteget är V[i,j]= + ???
Vad är ???
a) max(V[i-1,j], V[i-1,j+1])
b) max(V[i,j-1], V[i,j+1])
c) max(V[i+1,j], V[i+1,j+1]) - Svaret visas i andra videon.