Dynamisk programmering
Wikipedia
Dynamisk programmering är en generell metod för att lösa kombinatoriska optimeringsproblem och kan lättsamt beskrivas som "rekursion plus tabellering". Genom att systematiskt beräkna lösningar till delproblem, spara dessa på ett effektivt sätt, samt att låta alla dellösningar beräknas genom att utnyttja andra dellösningar, kan man hitta effektiva algoritmer för annars svårlösta problem. Ett klassiskt exempel är minsta editeringsavstånd som har en effektiv lösning med hjälp av dynamisk programmering, och har kommit att bli viktig inom bioinformatiken där molekulära sekvenser jämförs med hjälp av en linjering.
