Dynaamisen ohjelmoinnin demystifiointi

Dynaamisten ohjelmointialgoritmien rakentaminen ja koodaus

Ehkä olet kuullut siitä valmistautuessasi koodaushaastatteluihin. Ehkä olet taistellut sen läpi algoritmikurssilla. Ehkä yrität oppia koodaamaan itse, ja sinulle kerrottiin jonnekin matkan varrella, että on tärkeää ymmärtää dynaaminen ohjelmointi. Dynaamisen ohjelmoinnin (DP) käyttö algoritmien kirjoittamiseen on yhtä tärkeää kuin pelätään.

Ja kuka voi syyttää niitä, jotka vetäytyvät siitä pois? Dynaaminen ohjelmointi näyttää pelottavalta, koska sitä on opetettu huonosti. Monet opetusohjelmat keskittyvät tulokseen - algoritmin selittämiseen prosessin sijaan - algoritmin löytämiseen . Tämä kannustaa muistamiseen, ymmärtämättä jättämiseen.

Tänä vuonna tekemäni algoritmitunnin aikana koottiin yhteen oma prosessi dynaamista ohjelmointia vaativien ongelmien ratkaisemiseksi. Osa siitä tulee algoritmiprofessoriltani (jolle on paljon kiitoksia!) Ja osat omasta dissektiostani dynaamisista ohjelmointialgoritmeista.

Mutta ennen kuin jaan prosessini, aloitetaan perusasioista. Mikä on dynaaminen ohjelmointi?

Dynaaminen ohjelmointi määritelty

Dynaaminen ohjelmointi tarkoittaa optimointiongelman jakamista yksinkertaisemmiksi alaongelmiksi ja ratkaisun tallentamista kuhunkin alaongelmaan siten, että kukin alaongelma ratkaistaan ​​vain kerran.

Ollakseni rehellinen, tällä määritelmällä ei ehkä ole mitään järkeä, ennen kuin näet esimerkin alaongelmasta. Se on okei, se on tulossa seuraavaan osioon.

Toivon välittävän, että DP on hyödyllinen tekniikka optimointiongelmille, niille ongelmille, jotka etsivät suurinta tai vähimmäisratkaisua tietyin rajoituksin, koska se tutkii kaikki mahdolliset alaongelmat ja ei koskaan laske uudelleen ratkaisua mihinkään alaongelmaan. Tämä takaa oikeellisuuden ja tehokkuuden, jota emme voi sanoa useimmista tekniikoista, joita käytetään algoritmien ratkaisemiseen tai likiarvoistamiseen. Pelkästään tämä tekee DP: stä erityisen.

Seuraavissa kahdessa osassa selitän, mikä osa-ongelma on, ja motivoin sitten, miksi ratkaisujen tallentamisella - muistiinpanona tunnetulla tekniikalla - on merkitystä dynaamisessa ohjelmoinnissa.

Aliongelmat aliongelmissa

Aliongelmat ovat alkuperäisen ongelman pienempiä versioita. Itse asiassa alaongelmat näyttävät usein olevan alkuperäisen ongelman uudelleen muotoiltu versio. Jos alaongelmat on muotoiltu oikein, ne rakentuvat toisiinsa saadakseen ratkaisun alkuperäiseen ongelmaan.

Saadaksemme paremman käsityksen tämän toiminnasta, etsimme alaongelma esimerkin dynaamisesta ohjelmointiongelmasta.

Teeskentele, että työskentelet 1950-luvulla IBM-650-tietokoneen parissa. Tiedät mitä tämä tarkoittaa - lyödä kortteja! Työsi on miehen tai naisen, IBM-650: n, käyttö päiväksi. Sinulle annetaan suoritettavaksi luonnollinen numero n perforaattikorttia. Jokainen lävistyskortti i on ajettava tietyllä ennalta määrätyllä aloitusajalla s_i ja lopetettava juokseminen tietyllä ennalta määrätyllä lopetusajalla f_i . Vain yksi perfokortti voi toimia IBM-650 -laitteella kerralla. Jokaisella lävistyskortilla on myös liitetty arvo v_i sen mukaan, kuinka tärkeää se on yrityksellesi.

Ongelma : IBM-650: n vastuuhenkilönä sinun on määritettävä optimaalinen leimakorttien aikataulu, joka maksimoi kaikkien ajettujen leimakorttien kokonaisarvon.

Koska käyn läpi tämän esimerkin hyvin yksityiskohtaisesti läpi tämän artikkelin, aion vain kiusata teitä sen alaongelmasta:

Sub-ongelma : maksimiarvo aikataulu punchcards i kautta n siten, että punchcards lajitellaan alkamisaika.

Huomaa, kuinka osa-ongelma jakaa alkuperäisen ongelman komponentteihin, jotka rakentavat ratkaisun. Aliongelman avulla löydät maksimiarvon aikataulun leimakorteille n-1 - n ja sitten leimakorteille n-2 - n , ja niin edelleen. Löytämällä ratkaisut jokaiseen yksittäiseen ongelmaan, voit sitten puuttua itse alkuperäiseen ongelmaan: leimakorttien 1 - n maksimiarvojen aikataulu . Koska alaongelma näyttää alkuperäiseltä ongelmalta, osaongelmia voidaan käyttää alkuperäisen ongelman ratkaisemiseen.

Dynaamisessa ohjelmoinnissa, kun olet ratkaissut jokaisen alaongelman, sinun on muistettava tai tallennettava se. Selvitetään miksi seuraavassa osassa.

Motivoiva muistiinpano Fibonacci-numeroilla

Kun sinua käsketään toteuttamaan algoritmi, joka laskee Fibonacci-arvon mille tahansa numerolle, mitä tekisit? Useimmat tuntemani ihmiset valitsevat rekursiivisen algoritmin, joka näyttää tältä tältä Pythonissa:

def fibonacciVal(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacciVal(n-1) + fibonacciVal(n-2)

Tämä algoritmi saavuttaa tarkoituksensa, mutta valtavasti . Katsotaan esimerkiksi, mitä tämän algoritmin on laskettava ratkaisemaan n = 5 (lyhennettynä F (5)):

F(5) / \ / \ / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ / \ / \ F(2) F(1) F(1) F(0) F(1) F(0) / \ F(1) F(0)

Yllä oleva puu edustaa kutakin laskutoimitusta, joka on tehtävä Fibonacci-arvon löytämiseksi n = 5: lle. Huomaa, kuinka n = 2: n alaongelma ratkaistaan kolmesti. Suhteellisen pienessä esimerkissä (n = 5), se on paljon toistettua ja hukkaan laskettua!

Entä jos sen sijaan, että laskisimme Fibonacci-arvon n = 2: lle kolme kertaa, luomme algoritmin, joka laskee sen kerran, tallentaa sen arvon ja käyttää tallennettuja Fibonacci-arvoja jokaisen seuraavan n = 2 esiintymisen yhteydessä? Se on juuri sitä , mitä memoization tekee.

Tämän vuoksi olen kirjoittanut dynaamisen ohjelmointiratkaisun Fibonacci-arvo-ongelmaan:

def fibonacciVal(n): memo = [0] * (n+1) memo[0], memo[1] = 0, 1 for i in range(2, n+1): memo[i] = memo[i-1] + memo[i-2] return memo[n]

Huomaa, kuinka palautusarvon ratkaisu tulee muistiinpanotiedostosta [], jonka for-silmukka täyttää iteratiivisesti. Sanalla "iteratiivisesti" tarkoitan, että muistio [2] lasketaan ja tallennetaan ennen muistiota [3], muistiota [4],… ja muistiota [ n ]. Koska muistio [] täytetään tässä järjestyksessä, kunkin alaongelman (n = 3) ratkaisu voidaan ratkaista ratkaisuilla sen edellisiin alaongelmiin (n = 2 ja n = 1), koska nämä arvot on jo tallennettu muistio [] aikaisemmin.

Muistiinpano ei tarkoita uudelleenlaskentaa, mikä tekee algoritmista tehokkaamman. Siten muistiointi varmistaa, että dynaaminen ohjelmointi on tehokasta, mutta oikean alaongelman valitseminen takaa, että dynaaminen ohjelma käy läpi kaikki mahdollisuudet löytää paras.

Nyt kun olemme käsitelleet muistiinpanoja ja alaongelmia, on aika oppia dynaaminen ohjelmointiprosessi. Solki sisään.

Oma dynaaminen ohjelmointiprosessi

Vaihe 1: Tunnista alaongelma sanoin.

Liian usein ohjelmoijat kääntyvät kirjoittamaan koodia ennen kuin ajattelevat kriittisesti käsiteltävää ongelmaa. Ei hyvä. Yksi strategia aivojesi sytyttämiseksi ennen kuin kosketat näppäimistöä, on englanninkielisten tai muiden sanojen käyttäminen kuvaamaan alkuperäisen ongelman tunnistama alaongelma.

Jos ratkaiset ongelmaa, joka vaatii dynaamista ohjelmointia, tartu paperiin ja mieti mitä tarvitset ongelman ratkaisemiseksi. Kirjoita alaongelma tässä mielessä.

Esimerkiksi reikäkorttiongelmassa totesin, että alaongelma voidaan kirjoittaa "reikäkorttien i - n maksimiarvoaikatauluksi siten, että leimakortit lajitellaan aloitusajan mukaan". Löysin tämän alaongelman ymmärtämällä, että voidakseni löytää vastauksen seuraaviin alaongelmiin, jotta voisin määrittää enimmäisarvoaikataulun leikekorteille 1 - n siten, että leimauskortit lajitellaan aloitusajan mukaan:

  • Lävistyskorttien n-1 - n enimmäisarvoaikataulu siten, että leimauskortit lajitellaan aloitusajan mukaan
  • Lävistyskorttien n-2 - n enimmäisarvoaikataulu siten, että leimauskortit lajitellaan aloitusajan mukaan
  • Lävistyskorttien n-3 - n enimmäisarvoaikataulu siten, että leimauskortit lajitellaan aloitusajan mukaan
  • (Jne)
  • Rei'ityskorttien 2 - n maksimiarvoaikataulu siten, että leimauskortit on lajiteltu aloitusajan mukaan

Jos pystyt tunnistamaan alaongelman, joka perustuu aiempiin alaongelmiin ratkaistaksesi käsillä olevan ongelman, olet oikealla tiellä.

Vaihe 2: Kirjoita alaongelma toistuvaksi matemaattiseksi päätökseksi.

Kun olet tunnistanut alaongelman sanoin, on aika kirjoittaa se matemaattisesti. Miksi? No, matemaattinen toistuminen tai toistuva päätös, jonka löydät, on lopulta se, mitä laitat koodiin. Sen lisäksi, että alaongelman kirjoittaminen matemaattisesti tarkastaa aliongelmasi sanojen avulla vaiheesta 1. Jos matemaattisessa vaiheessa on vaikea koodata alaongelmaa vaiheesta 1, se voi olla väärä alaongelma!

On kaksi kysymystä, jotka kysyn itseltäni joka kerta, kun yritän löytää toistumisen:

  • Mitä päätän jokaisessa vaiheessa?
  • Jos algoritmini on vaiheessa i , mitä tietoja sen tarvitsisi päättääksesi mitä tehdä vaiheessa i + 1 ? (Ja joskus: Jos algoritmini on vaiheessa i , mitä tietoja sen tarvitsi päättääksesi mitä tehdä vaiheessa i-1 ?)

Palataan takaisin perforaattikorttiongelmaan ja kysytään näitä kysymyksiä.

Mitä päätän jokaisessa vaiheessa? Oletetaan, että perfokortit on lajiteltu aloitusajan mukaan, kuten aiemmin mainittiin. Algoritmin on valittava kahden vaihtoehdon välillä jokaisesta tähänastisen aikataulun kanssa yhteensopivasta leimakortista (sen aloitusaika on käynnissä olevan leimakortin päättymisajan jälkeen).

Jos algoritmini on vaiheessa i , mitä tietoja sen tarvitsisi päättääksesi mitä tehdä vaiheessa i + 1 ? Jos haluat päättää näiden kahden vaihtoehdon välillä, algoritmin on tiedettävä seuraava yhteensopiva lävistyskortti järjestyksessä. Seuraava yhteensopiva leimakortti tietylle leimakortille p on leimakortti q siten, että s_q (ennalta määrätty leimakortin q alkamisaika ) tapahtuu f_p: n (leimakortin p ennalta määrätty päättymisaika ) ja s_q: n ja f_p: n välisen eron jälkeenminimoidaan. Hylkää matemaatikko-puhuminen, seuraava yhteensopiva lävistyskortti on aikaisin aloitusaika sen jälkeen, kun nykyinen leimakortti on suoritettu loppuun.

Jos algoritmini on vaiheessa i , mitä tietoja sen tarvitsi päättääksesi mitä tehdä vaiheessa i-1 ? Algoritmin on tiedettävä tulevista päätöksistä: niistä, jotka on tehty leimakortteja i - n varten , jotta voidaan päättää, suoritetaanko kortti i-1 .

Nyt kun olemme vastaaneet näihin kysymyksiin, ehkä olet alkanut muodostaa mielessäsi toistuvan matemaattisen päätöksen. Jos ei, se on myös okei, toistojen kirjoittaminen on helpompaa, kun altistut dynaamisemmille ohjelmointiongelmille.

Ilman jatkojalostelua, tässä on toistumme:

OPT(i) = max(v_i + OPT(next[i]), OPT(i+1))

Tämä matemaattinen toistuminen vaatii selitystä, etenkin niille, jotka eivät ole kirjoittaneet sitä aiemmin. Käytän OPT ( i ): tä edustamaan lävistyskorttien i - n enimmäisarvoaikataulua siten, että leimauskortit on lajiteltu aloitusajan mukaan. Kuulostaa tutulta, eikö? OPT (•) on alaongelmamme vaiheesta 1.

Jotta voidaan määrittää arvon OPT ( i ), pidämme kaksi vaihtoehtoa, ja haluamme ottaa enintään näistä vaihtoehdoista täyttääkseen tavoitteemme: Tällä suurin arvo aikataulu kaikkien punchcards. Kun valitsemme vaihtoehdon, joka antaa maksimaalisen tuloksen vaiheessa i , muistiin merkitään sen arvo OPT ( i ): ksi.

Kaksi vaihtoehtoa - ajaa tai ei suorittaa lävistyskortti i - on esitetty matemaattisesti seuraavasti:

v_i + OPT(next[i])

Tämä lauseke edustaa päätöstä suorittaa lävistyskortti i . Se lisää lävistyskortin i suorittamisesta saadun arvon OPT: ään (seuraava [ i ]), missä seuraava [ i ] edustaa seuraavaa yhteensopivaa leimakorttia, joka seuraa leimakorttia i . OPT (seuraava [ i ]) antaa enimmäisarvon aikataulun seuraaville [ i ] - n: n leikekorteille siten, että leimauskortit lajitellaan aloitusajan mukaan. Näiden kahden arvon yhteenlaskeminen tuottaa maksimiarvon aikataulun lävistyskorteille i - n siten, että leimauskortit lajitellaan aloitusajan mukaan, jos leimakortti i suoritetaan.

OPT(i+1)

Päinvastoin, tämä lauseke edustaa päätöstä olla käyttämättä lävistyskorttia i . Jos lävistyskorttia i ei käytetä, sen arvoa ei saavuteta. OPT ( i + 1 ) antaa leimakorttien i + 1 - n maksimiarvoaikataulun siten, että leimauskortit lajitellaan aloitusajan mukaan. Joten, OPT ( i + 1 ) antaa maksimiarvon aikataulun lävistyskorteille i - n siten, että leimauskortit lajitellaan aloitusajan mukaan, jos leimakorttia i ei käytetä.

Tällä tavalla rei'ikorttiongelmien jokaisessa vaiheessa tehty päätös koodataan matemaattisesti vastaamaan vaiheen 1 alaongelmaa.

Vaihe 3: Ratkaise alkuperäinen ongelma vaiheiden 1 ja 2 avulla.

Vaiheessa 1 kirjoitimme muistikirjaongelman alaongelman sanoin. Vaiheessa 2 kirjoitimme toistuvan matemaattisen päätöksen, joka vastaa näitä alaongelmia. Kuinka voimme ratkaista alkuperäisen ongelman näillä tiedoilla?

OPT(1)

Se on niin yksinkertaista. Koska vaiheessa 1 löydetty alaongelma on lävistyskorttien i - n enimmäisarvotaulukko siten, että lävistyskortit lajitellaan aloitusajan mukaan, voimme kirjoittaa ratkaisun alkuperäiseen ongelmaan leimakorttien 1 - n maksimiarvoaikatauluna siten, että leimakortit lajitellaan aloitusajan mukaan. Koska vaiheet 1 ja 2 kulkevat käsi kädessä, alkuperäinen ongelma voidaan kirjoittaa myös nimellä OPT (1).

Vaihe 4: Määritä muistiinpanoryhmän mitat ja suunta, johon se tulisi täyttää.

Löysitkö vaiheen 3 petollisesti yksinkertaiselta? Se näyttää varmasti siltä. Saatat ajatella, kuinka OPT (1) voi olla ratkaisu dynaamiseen ohjelmaamme, jos se perustuu OPTiin (2), OPTiin (seuraava [1]) ja niin edelleen?

Olet oikeassa huomatessasi, että OPT (1) luottaa OPT (2): n ratkaisuun. Tämä seuraa suoraan vaiheesta 2:

OPT(1) = max(v_1 + OPT(next[1]), OPT(2))

Mutta tämä ei ole murskaava asia. Ajatelkaa Fibonacci-muistiinpanomallia. Fibonacci-arvon löytämiseksi n = 5: lle algoritmi perustuu siihen tosiasiaan, että Fibonacci-arvot n = 4, n = 3, n = 2, n = 1 ja n = 0 oli jo muistiinpanttu. Jos täytämme muistiinpanotaulukomme oikeassa järjestyksessä, OPT (1): n luottaminen muihin alaongelmiin ei ole iso juttu.

Kuinka voimme tunnistaa oikean suunnan muistiinpanotaulukon täyttämiseksi? Lävistyskorttiongelmassa, koska tiedämme, että OPT (1) perustuu ratkaisuihin OPT (2) ja OPT (seuraava [1]), ja että leimakorteilla 2 ja seuraavilla [1] on aloitusajat leimakortin 1 jälkeen lajittelun vuoksi, voi päätellä, että meidän on täytettävä muistiinpanotaulukko OPT ( n ) - OPT (1).

Kuinka määritämme tämän muistiinpanoryhmän mitat? Tässä on temppu: taulukon mitat ovat yhtä suuret kuin muuttujien määrä ja koko, joihin OPT (•) perustuu. Leikekorttiongelmassa meillä on OPT ( i ), mikä tarkoittaa, että OPT (•) luottaa vain muuttujaan i , joka edustaa leimakortin numeroa. Tämä viittaa siihen, että muistiointiryhmämme on yksiulotteinen ja että sen koko on n, koska reikäkortteja on yhteensä n .

Jos tiedämme, että n = 5, muistutusryhmä saattaa näyttää tältä:

memo = [OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Koska monet ohjelmointikielet alkavat matriisien indeksoinnin nollasta, voi olla helpompaa luoda tämä muistiryhmä siten, että sen indeksit ovat linjassa perfokortin numeroiden kanssa:

memo = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Vaihe 5: Koodaa se!

Dynaamisen ohjelmamme koodaamiseksi koomme vaiheet 2–4. Ainoa uusi tieto, jonka sinun tarvitsee kirjoittaa dynaaminen ohjelma, on peruskohde, jonka löydät, kun hakeudut algoritmiin.

Leikekorttiongelman dynaaminen ohjelma näyttää tältä:

def punchcardSchedule(n, values, next): # Initialize memoization array - Step 4 memo = [0] * (n+1) # Set base case memo[n] = values[n] # Build memoization table from n to 1 - Step 2 for i in range(n-1, 0, -1): memo[i] = max(v_i + memo[next[i]], memo[i+1]) # Return solution to original problem OPT(1) - Step 3 return memo[1]

Onnittelut ensimmäisen dynaamisen ohjelman kirjoittamisesta! Nyt kun olet kastellut jalkasi, käyn läpi erilaista dynaamista ohjelmaa.

Valinnan paradoksi: Useita vaihtoehtoja DP-esimerkki

Vaikka edellisessä dynaamisessa ohjelmointiesimerkissä oli kaksi vaihtoehtoa - lyödä tai jättää lyödä kortti - jotkut ongelmat vaativat useiden vaihtoehtojen huomioon ottamista ennen päätöksen tekemistä kussakin vaiheessa.

Aika uudelle esimerkille.

Pretend you’re selling the friendship bracelets to n customers, and the value of that product increases monotonically. This means that the product has prices {p_1, …, p_n} such that p_i ≤ p_j if customer j comes after customer i. These n customers have values {v_1, …, v_n}. A given customer i will buy a friendship bracelet at price p_i if and only if p_iv_i; otherwise the revenue obtained from that customer is 0. Assume prices are natural numbers.

Problem: You must find the set of prices that ensure you the maximum possible revenue from selling your friendship bracelets.

Take a second to think about how you might address this problem before looking at my solutions to Steps 1 and 2.

Step 1: Identify the sub-problem in words.

Sub-problem: The maximum revenue obtained from customers i through n such that the price for customer i-1 was set at q.

I found this sub-problem by realizing that to determine the maximum revenue for customers 1 through n, I would need to find the answer to the following sub-problems:

  • The maximum revenue obtained from customers n-1 through n such that the price for customer n-2 was set at q.
  • The maximum revenue obtained from customers n-2 through n such that the price for customer n-3 was set at q.
  • (Et cetera)

Notice that I introduced a second variable q into the sub-problem. I did this because, in order to solve each sub-problem, I need to know the price I set for the customer before that sub-problem. Variable q ensures the monotonic nature of the set of prices, and variable i keeps track of the current customer.

Step 2: Write out the sub-problem as a recurring mathematical decision.

There are two questions that I ask myself every time I try to find a recurrence:

  • What decision do I make at every step?
  • If my algorithm is at step i, what information would it need to decide what to do in step i+1? (And sometimes: If my algorithm is at step i, what information would it need to decide what to do in step i-1?)

Let’s return to the friendship bracelet problem and ask these questions.

What decision do I make at every step? I decide at which price to sell my friendship bracelet to the current customer. Since prices must be natural numbers, I know that I should set my price for customer i in the range from q — the price set for customer i-1 — to v_i — the maximum price at which customer i will buy a friendship bracelet.

If my algorithm is at stepi, what information would it need to decide what to do in stepi+1? My algorithm needs to know the price set for customer i and the value of customer i+1 in order to decide at what natural number to set the price for customer i+1.

With this knowledge, I can mathematically write out the recurrence:

OPT(i,q) = max~([Revenue(v_i, a) + OPT(i+1, a)])
such that max~ finds the maximum over all a in the range q ≤ a ≤ v_i

Once again, this mathematical recurrence requires some explaining. Since the price for customer i-1 is q, for customer i, the price a either stays at integer q or it changes to be some integer between q+1 and v_i. To find the total revenue, we add the revenue from customer i to the maximum revenue obtained from customers i+1 through n such that the price for customer i was set at a.

In other words, to maximize the total revenue, the algorithm must find the optimal price for customer i by checking all possible prices between q and v_i. If v_iq, then the price a must remain at q.

What about the other steps?

Working through Steps 1 and 2 is the most difficult part of dynamic programming. As an exercise, I suggest you work through Steps 3, 4, and 5 on your own to check your understanding.

Runtime Analysis of Dynamic Programs

Now for the fun part of writing algorithms: runtime analysis. I’ll be using big-O notation throughout this discussion . If you’re not yet familiar with big-O, I suggest you read up on it here.

Generally, a dynamic program’s runtime is composed of the following features:

  • Pre-processing
  • How many times the for loop runs
  • How much time it takes the recurrence to run in one for loop iteration
  • Post-processing

Overall, runtime takes the following form:

Pre-processing + Loop * Recurrence + Post-processing

Let’s perform a runtime analysis of the punchcard problem to get familiar with big-O for dynamic programs. Here is the punchcard problem dynamic program:

def punchcardSchedule(n, values, next): # Initialize memoization array - Step 4 memo = [0] * (n+1) # Set base case memo[n] = values[n] # Build memoization table from n to 1 - Step 2 for i in range(n-1, 0, -1): memo[i] = max(v_i + memo[next[i]], memo[i+1]) # Return solution to original problem OPT(1) - Step 3 return memo[1]

Let’s break down its runtime:

  • Pre-processing: Here, this means building the the memoization array. O(n).
  • How many times the for loop runs: O(n).
  • How much time it takes the recurrence to run in one for loop iteration: The recurrence takes constant time to run because it makes a decision between two options in each iteration. O(1).
  • Post-processing: None here! O(1).

The overall runtime of the punchcard problem dynamic program is O(n) O(n) * O(1) + O(1), or, in simplified form, O(n).

You Did It!

Well, that’s it — you’re one step closer to becoming a dynamic programming wizard!

One final piece of wisdom: keep practicing dynamic programming. No matter how frustrating these algorithms may seem, repeatedly writing dynamic programs will make the sub-problems and recurrences come to you more naturally. Here’s a crowdsourced list of classic dynamic programming problems for you to try.

So get out there and take your interviews, classes, and life (of course) with your newfound dynamic programming knowledge!

Paljon kiitoksia Steven Bennettille, Claire Durandille ja Prithaj Nathille tämän viestin oikolukemisesta. Kiitos professori Hartlineille siitä, että sain minut niin innostuneeksi dynaamisesta ohjelmoinnista, että kirjoitin siitä pitkään.

Nautitko lukemastasi? Levitä rakkaus pitämällä ja jakamalla tämä pala. Onko sinulla ajatuksia tai kysymyksiä? Ota yhteyttä minuun Twitterissä tai alla olevissa kommenteissa.