Dinamikus programozás: Példák, gyakori problémák és megoldások

Kétségtelen, hogy a dinamikus programozási problémák nagyon megfélemlítőek lehetnek egy kódolási interjúban. Még akkor is, ha tudja, hogy egy problémát dinamikus programozási módszerrel kell megoldani, kihívás, hogy korlátozott időn belül működőképes megoldást tudjunk előállítani.

A dinamikus programozási problémák kezelésének legjobb módja az, ha minél többet átél. Bár nem feltétlenül kell minden problémára megoldást megjegyeznie, jó, ha van ötlete arról, hogyan lehetne ezt végrehajtani.

Mi a dinamikus programozás?

Egyszerűen fogalmazva, a dinamikus programozás optimalizálási módszer a rekurzív algoritmusokhoz, amelyek többségét számítási vagy matematikai problémák megoldására használják.

Az optimalizálási probléma megoldásának algoritmikus technikának is nevezhető, egyszerűbb részproblémákra bontva. A dinamikus programozás alapelve az, hogy a probléma optimális megoldása az alproblémák megoldásaitól függ.

Bárhol is látunk olyan rekurzív megoldást, amely ismételten kéri ugyanazokat a bemeneteket, optimalizálhatjuk dinamikus programozással. Az ötlet az, hogy egyszerűen tároljuk a részproblémák eredményeit, hogy ne kelljen később újra kiszámítanunk őket.

A dinamikusan programozott megoldások polinomiális összetettséggel bírnak, ami sokkal gyorsabb futási időt biztosít, mint más technikák, például a rekurzió vagy a visszalépés. A legtöbb esetben a dinamikus programozás csökkenti az idő bonyolultságát, más néven nagy-O, exponenciálisról polinomra.

Mi a Big-O jelölés?

A kódjának hatékonynak kell lennie, de hogyan lehet megmutatni, hogy valami mennyire hatékony? Big-O-val!

Most, hogy van egy jó ötlete a dinamikus programozásról, itt az ideje, hogy megvizsgáljon néhány gyakori problémát és azok megoldásait.

Dinamikus programozási problémák

1. Hátizsák probléma

Probléma nyilatkozat

Adjon meg egy sor tételt, amelyek mindegyikének van súlya és értéke, határozza meg az egyes elemek számát, amelyeket fel kell venni a gyűjtést, hogy a teljes tömeg ne haladja meg az adott határt, és az összérték akkora legyen, mint lehetséges.

Két egész tömböt kapsz értékek [0..n-1] és súlyok [0..n-1] amelyek n elemhez tartozó értékeket és súlyokat jelentenek. Egy egész számot is megadunk W ami a hátizsák kapacitását képviseli.

Itt megoldjuk a 0/1 hátizsák problémát, ami azt jelenti, hogy választhatunk egy elem hozzáadását vagy kizárását.

Algoritmus

• Hozzon létre kétdimenziós tömböt a n + 1 sorok és w + 1 oszlopok. Egy sorszám n az elemek halmazát jelöli 1-től én, és egy oszlop számát w a táska maximális teherbírását jelöli.
• A számérték a [i] [j] -ig a tételek összértékét jelöli én olyan zsákban, amely maximálisan j súlyt képes szállítani.
• Minden koordinátán [i] [j] a tömbben válassza ki azt a maximális értéket, amely nélkül megszerezhetjük i. tétel, vagy a maximális érték, amellyel megszerezhetjük i. tételamelyik nagyobb.
• Az i tétel felvételével elérhető maximális érték a tétel összege én és a hátizsák fennmaradó kapacitásával elérhető legnagyobb érték.
• Végezze el ezt a lépést, amíg meg nem találja a W^th sor.

Kód

def FindMax (W, n, értékek, súlyok):
MaxVals = [[0 x tartományban (W + 1)] x tartományban (n + 1)]
az i tartományban (n + 1):
w tartományban (W + 1):
ha i == 0 vagy w == 0:
MaxVals [i] [w] = 0
elif súlyok [i-1] <= w:
MaxVals [i] [w] = max (értékek [i-1]
+ MaxVals [i-1] [w-súlyok [i-1]], 
MaxVals [i-1] [w])
más:
MaxVals [i] [w] = MaxVals [i-1] [w]
visszatér MaxVals [n] [W]

2. Érmeváltási probléma

Probléma nyilatkozat

Tegyük fel, hogy olyan számtömböt kap, amely az egyes érmék értékét képviseli. Megadva egy adott összeget, keresse meg az érmék minimális számát, amelyre szükség van.

Algoritmus

• Inicializáljon egy tömböt n + 1, ahol n az összeg. Inicializálja minden index értékét én a tömbben egyenlő legyen az összeggel. Ez az érmék maximális számát jelöli (1. címletű érméket használva), amelyek az adott összeg elkészítéséhez szükségesek.
• Mivel 0-nak nincs megnevezése, inicializálja a bázist, ahol tömb [0] = 0.
• Minden más indexhez én, összehasonlítjuk a benne lévő értéket (amelyet eredetileg a n + 1) értékével tömb [i-k] +1, hol k kevesebb mint én. Ez lényegében az i-1-ig ellenőrzi a teljes tömböt, hogy megtalálja a lehető legkisebb érmeszámot.
• Ha az érték bármelyik tömb [i-k] + 1 kisebb, mint a tömb [i], cserélje ki a következő értéket: tömb [i] a valakivel tömb [i-k] +1.

Kód

def coin_change (d, összeg, k):
számok [0] * (összeg + 1)
j tartományban (1, összeg + 1):
minimum = összeg
i-re az (1, k + 1) tartományban:
ha (j> = d [i]):
minimum = min (minimum, 1 + számok [j-d [i]])
számok [j] = minimum
visszatérési számok [összeg]

3. Fibonacci

Probléma nyilatkozat

A Fibonacci sorozat egész számok sorozata, ahol a sorozat következő egész száma az előző kettő összege.

A következő rekurzív reláció határozza meg: F (0) = 0, F (n) = F (n-1) + F (n-2), hol F (n) az n^th kifejezés. Ebben a feladatban az összes számot egy Fibonacci-szekvenciában kell generálnunk egy adott n-ig^th kifejezés.

Algoritmus

• Először alkalmazzon rekurzív megközelítést az adott ismétlődési reláció megvalósításához.
• A probléma rekurzív megoldása lebontással jár F (n) -ba F (n-1) + F (n-2), majd meghívja a függvényt a gombbal F (n-1) és F (n + 2) mint paramétereket. Tesszük ezt addig az alapesetig, ahol n = 0, vagy n = 1 elérik.
• Most az emlékeztetésnek nevezett technikát alkalmazzuk. Tárolja az összes függvényhívás eredményét egy tömbben. Ez biztosítja, hogy minden n, F (n) csak egyszer kell kiszámolni.
• Bármely későbbi számításhoz az értéke egyszerűen lekérhető a tömbből állandó időben.

Kód

def fibonacci (n): 
fibNums = [0, 1] 
i-re a (2, n + 1) tartományban:
fibNums.append (fibNums [i-1] + fibNums [i-2])
return fibNums [n] 

4. Leghosszabb növekvő következmény

Probléma nyilatkozat

Keresse meg a leghosszabb növekvő részszakasz hosszát egy adott tömbön belül. A leghosszabb növekvő alszekvencia a növekvő sorrendű számtömbön belüli szekvencia. Az utólagos számoknak egyedinek és növekvő sorrendben kell lenniük.

A szekvencia tételeinek nem kell egymást követniük.

Algoritmus

• Kezdje egy rekurzív megközelítéssel, ahol kiszámítja a leghosszabb növekvő részének értékét minden lehetséges alrész a nullától az i indexig, ahol i kisebb vagy egyenlő a méretével sor.
• Ahhoz, hogy ezt a módszert dinamikussá alakítsa, hozzon létre egy tömböt, amely tárolja az értéket az összes alsor számára. Inicializálja ennek a tömbnek az összes értékét 0-ra.
• Minden index én ennek a tömbnek a hossza növekszik a leghosszabb növekvő alszakasz méretének egy részrajzánál én.
• Most minden egyes rekurzív híváshoz findLIS (arr, n), ellenőrizd a n^th a tömb indexe. Ha ez az érték 0, akkor az első lépésben használt módszerrel számítsa ki az értéket, és tárolja a n^th index.
• Végül adja vissza a tömb maximális értékét. Ez egy adott méret leghosszabban növekvő szakaszának hossza n.

Kód

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
i-re az (1, n) tartományban:
j esetén a (0, i) tartományban:
ha myArray [i]> myArray [j] és lis [i] lis [i] = lis [j] +1
maxVal = 0
i-re az (n) tartományban:
maxVal = max (maxVal, lis [i])
visszatér maxVal

Dinamikus programozási problémák megoldása

Most, hogy átesett a legnépszerűbb dinamikus programozási problémákon, itt az ideje, hogy kipróbálja a megoldásokat egyedül. Ha elakadt, akkor bármikor visszatérhet, és a fenti problémák mindegyikéhez olvassa el az algoritmus részt.

Tekintettel arra, hogy napjainkban milyen népszerű technikák, például rekurzió és dinamikus programozás vannak, nem árt megnézni néhány népszerű platformot, ahol megtanulhatja az ilyen fogalmakat csiszolja a kódolási képességeit. Bár előfordulhat, hogy nem napi szinten találkozik ezekkel a problémákkal, biztosan találkozik velük egy technikai interjú során.

Természetesen a közös problémák know-how birtoklása osztalékot fizet, amikor elmész a következő interjúra. Tehát nyisd ki a kedvenc IDE, és kezdje!

A 9 legjobb kód-mentes YouTube-csatorna a programozás elsajátításához

Készen áll a kódolás megkezdésére? Ezek a YouTube-csatornák nagyszerű módja a játék, alkalmazás, web és egyéb fejlesztések megkezdésének.

A szerzőről