dynamic programming

dynamic programming (tsz. dynamic programmings)

1. (informatika) dinamikus programozás

A dinamikus programozás (DP) egy optimalizálási technika, amelyet olyan problémák megoldására használnak, amelyek több, egymásra épülő részproblémára bonthatók. A lényege, hogy ne számoljuk ki többször ugyanazt a részmegoldást, hanem elmentjük (memorizáljuk) a már kiszámolt eredményeket, és újra felhasználjuk őket.

Az ötlet Richard Bellmantől származik az 1950-es évekből, aki ezt a módszert „optimalitás elve” alapján alkotta meg:

„Az optimális megoldás mindig optimális részmegoldásokból épül fel.”

A dinamikus programozás akkor alkalmazható, ha egy probléma rendelkezik az alábbi két tulajdonsággal:

A probléma megoldása során ugyanazokat a részfeladatokat többször kiszámolnánk.

Az egész probléma megoldása az alproblémák optimális megoldásain alapul.

Ez egy rekurzív megközelítés, ahol a főproblémából indulunk ki, és fokozatosan bontjuk le az alproblémákra. Az ismétlődő számításokat memorizálással (memoization) kerülhetjük el.

Ebben az esetben a kisebb alproblémák megoldásával fokozatosan építjük fel a végső megoldást. Itt általában táblázatot használunk (pl. egy tömböt), amelybe minden részmegoldást elmentünk.

A Fibonacci-sorozat:

$${\displaystyle F(n)=F(n-1)+F(n-2)}$$

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

def fib_dp(n):
    dp = 
    for i in range(2, n + 1):
        dp.append(dp + dp)
    return dp

Adott tárgyak halmaza, mindegyikhez tartozik egy súly és érték. A cél, hogy kiválasszuk a tárgyakat úgy, hogy az összsúly ne lépje túl a hátizsák kapacitását, miközben az érték maximális.

def knapsack(w, v, W):
    n = len(w)
    dp =  * (W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(W+1):
            if w <= j:
                dp = max(dp, dp] + v)
            else:
                dp = dp
    return dp

Két karakterlánc leghosszabb közös részszekvenciáját keressük.

def lcs(a, b):
    n, m = len(a), len(b)
    dp = *(m+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if a == b:
                dp = dp + 1
            else:
                dp = max(dp, dp)
    return dp

• 2D-táblázat: ha a probléma két változós (pl. LCS, hátizsák)
• 1D tömb: ha az eredmény csak az előző értékektől függ (pl. Fibonacci)
• Memorization (dict): kényelmes Pythonban rekurzív megközelítéshez

• Bioinformatika: DNS-elemzés, szekvencia-illesztés
• Pénzügy: árfolyamok optimalizálása
• Szövegfeldolgozás: szerkesztési távolság, szövegek hasonlósága
• Robotika, AI: pályatervezés, stratégiai döntések
• Játékok: optimális lépéssorozat keresése (pl. sakkvégjáték)
• Fordítóprogramok: szintaktikai elemzés (pl. CYK-algoritmus)

• Sok problémát hatékonyan old meg (polinomiális idő)
• Rekurzív vagy iteratív módon is megoldható
• Könnyen átlátható táblázatos formában

• Nagy memóriaigény (főleg 2D DP esetén)
• Nehéz felismerni, hogy mikor alkalmazható
• Nem mindig triviális a részproblémák megfogalmazása

Gyakran a teljes 2D tömb helyett elegendő csak 1 sor vagy oszlop, így csökkenthető a memóriahasználat.

Példa: LCS probléma → csak 2 sor kell a számításokhoz, nem az egész mátrix.

A dinamikus programozás egy rendkívül hatékony és sokoldalú eszköz optimalizálási és döntési problémák megoldására:

• Ismétlődő részproblémákra épül
• Részmegoldásokat tárol → időmegtakarítás
• A programozási versenyek és ipari megoldások alapköve

• dynamic programming - Szótár.net (en-hu)
• dynamic programming - Sztaki (en-hu)
• dynamic programming - Merriam–Webster
• dynamic programming - Cambridge
• dynamic programming - WordNet
• dynamic programming - Яндекс (en-ru)
• dynamic programming - Google (en-hu)
• dynamic programming - Wikidata
• dynamic programming - Wikipédia (angol)