Dynamisk programmering 1.2

  • Vad skiljer dekomposition från dynamisk programmering?
    Svar: I dekomposition återkommer inte samma delproblem flera gånger i den rekursiva formuleringen av problemet. Därför implementeras dekomposition nästan alltid med rekursion.
  • Varför går det snabbare med dynamisk programmering än med en rekursiv implementation?
    Svar: Vid dynamisk programmering beräknas inte samma delproblem många gånger.
  • Titta på andra videon om dynamisk programmering.
  • Fråga: Vid beräkning av Fibonaccitalen räcker det att spara dom två senaste delproblemens värde. Går det på liknande sätt att slippa spara hela historiken vid beräkning av längsta växande delföljd?
  • Klicka här för att få se svaret och sista videon.

Lärare Viggo Kann skapade sidan 12 september 2016

Viggo Kann flyttade sidan från Algoritmer, datastrukturer och komplexitet (DD1352) 12 september 2016

Lärare Viggo Kann ändrade rättigheterna 12 september 2016

Kan därmed läsas av alla och ändras av lärare.
kommenterade 14 september 2016

Jag förstår inte algoritmen i videon för att lösa delproblemet. Är det fler som inte förstår den får du gärna ha en genomgång på föreläsningen. Ska det möjligtvis stå q[j] i den inre iterationen?

Lärare kommenterade 14 september 2016

Tack! Ja, det står fel. Det ska vara q[j] i if-satsen i slingan. Jag tar upp det på föreläsningen.

Feedback Nyheter