A dinamikus programozás egy, a divide et imperához hasonló módszer, ahol a feladatot részfeladatokra bontjuk, majd a részfeladatok megoldásait tároljuk, így minden részfeladatot csak egyszer oldunk meg. Több típusfeladatnál is használható ez a megoldás:

• Fibonacci
• Minimum erőfeszítésű út egy mátrixban
• 2 string leghosszabb közös metszete
• Hátizsák feladat

Fibonacci

A Fibonaccinál csak annyi különbség van az ismert rekurzív megoldáshoz, hogy egy tömbben/map ben tároljuk a már kiszámolt értékeket, s nem számoljuk minding újra.

Minimum erőfeszítésű út egy mátrixban

Adott egy NxN es mátrix, amelyiknek a bal felső sarkából (0,0) kell eljutni a jobb alsó (N-1, N-1) sarkába, úgy, hogy csak jobbra vagy lefelé haladhatunk. Minden cellába eljutni bizonyos erőfeszítésbe kerül, amit az illető mátrix elem tartalmaz. Keressük meg azt az utat, amelyik a legkevesebb erőfeszítésbe kerül s írjuk ki az összerőfeszítést!

Útmutatás a feladatmegoldáshoz:

• Először megfordítjuk a feladatot, vagyis nem a 0,0 ról próbálunk eljutni az N-1, N-1 re, hanem az N-1,N-1 ből indulunk
• Egyfajta rekurzív divide et imperat használunk, vagyis azt mondjuk, hogy az az erőfeszítés, ami szükséges ahhoz, hogy i, j koordinátára elérjünk, az egyenlő az i, j értékkel, plusz a minimuma a két lehetséges útnak hozzá: i-1, j illetve i, j-1
• A leállási feltételeket kell még lekezeljük, ha 0,0 n vagyunk, akkor visszatérítjük a mátrix[0][0] elemét
• Ha elértünk az első sorba, akkor mindig a jelenlegi mátrixelem értékét, plusz az i=0, j-1 ig terjedő útat térítjük vissza
• Ha elérünk az első oszlopba, akkor a jelenlegi mátrixelem értékét, plusz az i-j, j=0 ig terjedő útat térítem vissza

int cost(int i, int j) {

    if (i == 0 && j == 0) {
        return v[i][j];
    }
    if (i == 0) {
        return v[i][j] + cost(i, j-1);
    }
    if (j == 0) {
        return v[i][j] + cost(i-1, j);
    }
    return v[i][j] + min(cost(i-1,j), cost(i,j-1));
}