Dünaamiline programmeerimine

Dünaamiline programmeerimine on algoritmiline probleemi lahendamise meetod, mis lahendab kõigepealt alamprobleemid ja salvestab need mingisse andmestruktuuri. Neid andmeid kasutatakse üldisema probleemi lahendamiseks. Ehk lahendatakse probleem, mis esialgu tundub keerulisem. Näiteks, kui on vaja leida pikim tee kaaludega graafis punktist A punkti B, siis leitakse pikimad teed kõikidesse punktidesse, mille põhjal leitakse lahendus esialgsele probleemile. On vaieldav, mis moodustab DP probleemi, sest DP ei ole nii selgelt määratud nagu  näiteks lineaarne programmeerimine. Dünaamiliseks programmeerimiseks võib nimetada ka algoritme, mis kasutavad vahepealsete tulemuste hoidmiseks puhvreid. Dünaamilist programmeerimist ei rakendata ainult optimeerimise probleemide lahendamisel.

Ajalugu

Dünaamiline programmeerimine kui teooria sai alguse ligi 60 aastat tagasi Richard Bellmanni kirjutatud artiklist. Sellest ajast alates on dünaamiline programmeerimine kasutusel paljudes teadusharudes, nagu arvutiteadus, majandus, kaubandus jt.

Bioinformaatikas

Sõnede A = a₁a₂...aₘ  ja B = 
b₁b₂...bₙ pikim ühine alamjada (longest common subsequence, LCS) on C, kui C on pikim sõne, mis on nii A kui B alamjada. Näiteks kui ATTGCTA on jada, siis AGCA ja ATTA on alamjadad, aga TGTT ei ole. ATCTGAT ja TGCATA ühine alamjada on TCTA.
LCS on lihtsaim meetod jadade võrdlemiseks, kus on lubatud ainult sisestamised ja kustutamised. Niimoodi saab pikimat alamjada leida O(n*m) ajaga. Pole tõestatud, et kiiremaid algoritme selle probleemi jaoks ei leidu.
Järgnev kood on pikima ühtse alamjada leidmiseks C# keeles. Kusjuures ta hakkab lugema argumente esimesest elemendist. Maatriksit c kasutatakse vahepealsete tulemuste hoidmiseks.
public StringBuilder LCS(char[] m, char[] n)
        {
            int[,] c = new int[m.Length, n.Length];
            int m_ = m.Length;
            int n_ = n.Length;

            for (int i = 1; i < m.Length; i++)
            {
                for (int j = 1; j < n.Length; j++)
                {
                    if (m[i] == n[j])
                        c[i, j] = c[i - 1, j - 1] + 1;
                    else
                        c[i, j] = Math.Max(c[i, j - 1], c[i - 1, j]);
                }

            }

            return BacktrackLCSNorecursion(c, m, n, m.Length - 1, n.Length - 1, new 

StringBuilder());
        }StringBuilder BacktrackLCSNorecursion(int[,] c, char[] m, char[] n, int i, int j, 

StringBuilder s)
        {
            while (i != 0 && j != 0)
            {
                if (m[i] == n[j])
                {
                    s.Append(m[i]);
                    i -= 1;
                    j -= 1;
                }
                else
                    if (c[i, j - 1] > c[i - 1, j])
                    {
                        j -= 1;
                    }
                    else
                        i -= 1;
            }
            return s;
        }
Tegemist on lahendusega väga üldisele probleemile. Sest näiteks kui antud jadad koosneks permutatsioonidest, kus ei ole ühtegi korduvat tähte, võiks selle probleemi lahendada ajaga O(n log n). Kui on antud n = 1, 4, 2, 5, 6, 8 ja m = 4, 1, 5, 8, 2, 6, siis saab n-i arvud panna m-i niimoodi (4,2)(1,1)(5,4)(8,6)(2,3)(6,5). Siis iga sellise paari (x,y) y= (2,1,4,6,3,5) pikim kasvav alamjada (Longest increasing subsequence) ongi pikim ühine alamjada ja seda saab leida O(n log n) ajaga. Samuti on pikim ühine kasvav alamjada (mitte segi ajada pikima kasvava alamjadaga) võimalik arvutada kasutades pikimat ühist alamjada.
Seega on paljud dünaamilise programmeerimise algoritmid sarnased.

Masinõppimises

Dünaamiline programmeerimine annab vahendid mõõta ühe sõna kaugust teisest, mis on masinõppimise ja andmekaeve jaoks infoajastul vajalik. On olemas dünaamilisel programmeerimisel põhinevad masinõppe algoritmid, nagu reinforcement learning.

Geoinformaatikas

Dijkstra algoritmi kasutatakse GIS rakendustes leidmaks optimaalset teed.