[SCRÂTÂT] [FOSȘIT] [CLIC] ERIK DEMAINE: Bine, bine ați revenit la 006. Astăzi începem o secțiune complet nouă a clasei. Până acum, v-am arătat în mare parte algoritmi foarte tari și puternici , algoritmi de sortare, algoritmi grafici, structuri de date, copaci, o mulțime de lucruri bune pe care le puteți aplica pentru a rezolva o mulțime de probleme algoritmice, fie reducând la structurile de date. pe care vi le-am arătat, sau reducând la problemele grafice pe care vi le-am arătat, sau modificând puțin acei algoritmi. Astăzi vom începe o nouă secțiune despre proiectarea algoritmică - cum să venim de la zero cu un algoritm de timp polinomial pentru a rezolva o problemă. Și în special, vom vorbi despre o paradigmă de proiectare algoritmică numită programare dinamică, care este extrem de puternică. Este probabil cea mai puternică paradigmă de proiectare algoritmică. Foarte general. Poate rezolva o mulțime de probleme. Este un tip particular de proiectare a algoritmului recursiv. Și, în general, această clasă -- toți algoritmii -- este despre proiectarea algoritmilor recursivi la un anumit nivel, deoarece dorim să scriem bucăți de cod de dimensiune constantă care rezolvă probleme de dimensiune arbitrară. Avem o problemă de dimensiune n și încercăm să scriem 100 de linii de cod sau orice altceva, o cantitate constantă care nu depinde de dimensiunea problemei. Avem un singur algoritm care rezolvă toate cazurile problemei. Așa că trebuie să scriem cod recursiv sau care folosește bucle sau reutilizează cumva instrucțiunile pe care le dăm computerului. Și poate știți că puteți converti orice algoritm bazat pe bucle într-un algoritm folosind recursiunea. Și vom lua azi viziunea recursivă, în special pentru că se potrivește foarte bine cu tehnica noastră de demonstrare prin inducție , pe care am folosit-o în această clasă, dar și pentru că ne oferă o structură a modului în care diferitele subprobleme se relaționează în ceva numit grafic subproblemă, despre care vom vorbi astăzi. Și așa că vom începe cu, în general, cum proiectăm algoritmi recursivi? Acesta este un fel de general, care cuprinde totul. Ne-am gândit foarte mult să găsim un acronim grozav pentru această paradigmă pe care am inventat-o, numită SRTBOT -- mulțumesc, Jason. Și așa vom vorbi... nu este de fapt pentru sortare. Este doar un acronim pentru sub-probleme, relații, ordine topologică, caz de bază, problemă originală și timp. Dar este un acronim care vă va ajuta să vă amintiți toți pașii de care aveți nevoie pentru a specifica un algoritm recursiv. Și programarea dinamică se va baza pe acest șablon, adăugând o idee nouă numită memorare, care este doar ideea de a reutiliza munca pe care ați făcut-o înainte. Și asta ne va permite să rezolvăm o mulțime de probleme. Și să vedem. Eu nu... hai să intrăm în asta. Așa că vom începe astăzi cu SRTBOT. Deci, aici este SRTBOT în coloana de aici. Aceasta este o paradigmă de proiectare a algoritmului recursiv. Și, în general, ceea ce vom face este să luăm problema pe care vrem de fapt să o rezolvăm și să o împărțim în o mulțime de posibile subprobleme. Și astfel prima parte este să definiți care naiba sunt subproblemele. În general, vom dori un număr polinomial dintre ele. Dar este destul de deschis cum arată acestea. Iar cea mai grea parte, de obicei, în definirea unui algoritm recursiv este să descoperi care ar trebui să fie subproblemele. De obicei, acestea sunt legate de problema pe care doriți să o rezolvați. Adesea, problema pe care doriți să o rezolvați -- aceasta este de fapt aproape de ultimul pas -- problema inițială pe care încercați să o rezolvați este adesea una dintre aceste subprobleme. Și apoi folosiți subproblemele mai mici pentru a construi problema finală, originală. Dar uneori, la sfârșit, trebuie să luați o grămadă de subprobleme și să le combinați în problema dvs. inițială. Vă puteți gândi... o analogie la care vă puteți gândi aici este algoritmii de împărțire și cuceri, care aveau și acest tip de stil. Dar, mai general, vom raporta diferite soluții de subproblemă cu o structură recursivă - o relație de recurență. Acesta este doar un algoritm recursiv care definește cum se rezolvă o problemă în termeni de sub-probleme mai mici pentru o noțiune de mai mic. Și aceasta este dată de ordinea topologică. Deci, dacă ne gândim la subprobleme ca pe un grafic și tragem o muchie între-- deci vârfurile graficului sunt subprobleme. Marginile sunt dependențele dintre acele subprobleme. Apoi, ceea ce ne-am dori este ordonarea topologică, problema de sortare topologică despre care am vorbit în contextul celor mai scurte căi DFS sau DAG. Ceea ce ne-am dori este ca subproblemele și apelurile -- apelurile recursive dintre ele în această relație recursivă -- să formeze un DAG. Vrem să fie aciclic, altfel aveți o buclă infinită în apelurile recursive. Dacă ai un ciclu, nu vei înceta niciodată. Și astfel, pentru a vă asigura că aceste dependențe între subproblemele date de această relație de recurență sunt aciclice, o modalitate de a face acest lucru este să specificați o ordine topologică. Sau ai putea demonstra asta într-un alt mod. Dar de multe ori este doar o buclă pentru a spune, doar fă-o în această ordine. Atunci, desigur, orice structură recursivă are nevoie de cazuri de bază. Deci, acesta este un pas util de nu uitat. Dorim să rezolvăm problema inițială folosind aceste subprobleme. Și apoi analizăm un timp de rulare la sfârșit. Deci șase pași simpli. De fapt, cele mai grele sunt acestea două, care sunt interdependente. Și ceea ce vom vedea în următoarele patru prelegeri - aceasta este prima dintre cele patru prelegeri despre programarea dinamică - este o mulțime de exemple de aplicare a acestei paradigme din nou și din nou împreună cu ideea de memorare, la care vom ajunge. curând. Să vedem mai întâi un exemplu de algoritm pe care l-am văzut deja, care este sortare de îmbinare, deci un algoritm de împărțire și cucerire, formulat cu această structură a SRTBOT. Deci, pentru problemele secundare, deci problema noastră inițială este să sortăm elementele lui A. Și unele subprobleme pe care le rezolvăm pe parcurs sunt sortarea diferitelor sub-matrice ale lui A. Deci pentru fiecare... ei bine, nu pentru fiecare i și j, dar pentru unele i și js, sortăm elementele de la i până la j minus 1. Deci voi defini acea subproblemă ca fiind s din ij. Deci, acesta este ceva ce aș putea dori să rezolv. Problema inițială pe care vreau să o rezolv este s de 0 virgulă n, unde n este lungimea matricei. Deci asta e ceea ce îmi pasă de fapt până la urmă. Dar vom rezolva asta scriindu-l recursiv în ceea ce privește sortarea diferitelor sub-matrice, după cum urmează. Aceasta este relația de recurență. Am scris-o foarte simplu aici. Desigur, există un algoritm de îmbinare, care este oarecum complicat. Dar după cum am văzut algoritmul de îmbinare liniară în timp cu două degete, având în vedere două matrice sortate - deci aceasta ar trebui să fie versiunea matricei sortate a elementelor de la i la m. m este elementul mijlociu dintre i și j și matricea sortată a elementelor de la m până la j. Dacă le îmbinăm, asta ne oferă matricea sortată de la i până la j. Și exact asta face sortarea de îmbinare. Deci, în general, această relație este doar un algoritm pentru că, dacă vi se oferă soluțiile unor subprobleme mai mici, cum rezolv subproblema pe care vreau să o rezolv? Și deci trebuie să ne asigurăm că această problemă este mai mare decât cele pe care le apelăm recursiv și că nu obținem o buclă ciclică infinită de recursiuni. Și aici ordinea noastră topologică validă este de a spune, rezolvați aceste probleme în ordinea în care j minus i-- lungimea sub-matrice-- este în creștere. Și apoi puteți verifica pentru că m este strict între i și j. Atâta timp cât nu ne aflăm într-un caz de bază, atunci știm că putem... aceste subgrupuri vor fi mai mici decât acesta. Și astfel această ordine crescătoare ne oferă o ordine topologică validă pentru toate problemele, toate subproblemele. Avem un caz de bază, adică dacă nu vrem să sortăm nimic, acesta este matricea goală, sau cel puțin în problema originală. Și apoi timpul de rulare este... Adică, nu există o modalitate mai bună de a o rezolva decât recurența pe care am văzut deja cum să o rezolvăm. Deci, acesta este doar un alt mod de a ne gândi la sortarea n log n merge în acest cadru etichetat al SRTBOT. Să ajungem la o altă problemă care nu se potrivește atât de bine cu recursiunea. Dar o putem face mai bună. Deci, aceasta este... vom începe cu o problemă foarte simplă , care este calcularea numerelor Fibonacci. Este într-adevăr doar o problemă de jucărie pentru a ilustra o idee foarte puternică , care este memorarea. Deci problema care mă interesează este că mi se dă un anumit număr, n. Și vreau să calculez al n-lea număr Fibonacci. Și în cazul în care ați uitat, al n-lea număr Fibonacci este dat de această recurență. fn este fn minus 1 plus fn minus 2 cu cazul de bază, să spunem, f1 este egal cu f2 este egal cu 1. Și așa am dori să calculăm acest lucru. Aceasta pare... aceasta este o recurență. Așa că pare foarte natural să-l scrieți ca algoritm recursiv. Deci hai să încercăm să o facem. Începem cu care sunt problemele secundare. Subproblemele evidente sunt doar diferitele numere Fibonacci, f i pentru i între 1 și n. Deci există n dintre aceste subprobleme. Misto. Să vedem. Vrem o relație între ei. Ei bine, poate doar pentru a distinge problemele de numerele Fibonacci, permiteți-mi să scriu f din i. Aceasta este o funcție, un algoritm pe care îl vom defini. Și este definit a fi-- scopul pe care încercăm să-l obținem este al i-lea număr Fibonacci dat i. Și apoi putem scrie relația de recurență pe acești tipi, doar f din i este egal cu f din i minus 1 plus f din i minus 2. Deci, cu alte cuvinte, calculați recursiv acele numere Fibonacci apoi adăugați-le împreună. Acesta este un algoritm. Urmează t pentru ordinea topologică. Aici, desigur, vrem doar să le calculăm în ordinea creșterii i din cazul de bază. Un alt mod în care îmi place să scriu acest lucru este ca o buclă for pentru i este egală cu 1 la n. Vom vedea de ce. Dar aceasta dă o ordine explicită pentru a calcula aceste subprobleme. Și cazul de bază este la fel cu numerele Fibonacci, dar cred că ar trebui să scriu în paranteze. Problema originală pe care vrem să o rezolvăm este f din n. Și timpul... în regulă, aici lucrurile devin interesante sau rele. Deci, care este timpul de rulare al acestui algoritm recursiv? După cum am spus până acum, timpul de rulare este dat de o recurență. Să scriem recurența. Deci, pentru a calcula f din n, calculez recursiv f din i minus 1 sau f din n minus 1 aici. Și calculez recursiv f din n minus 2. Deci va dura t din n minus 2. Acest prim pas va lua t din n minus 1. Și acum trebuie să rezolv această recurență. Aceasta nu este o recurență care cade în sarcina metodei master. Nu are o împărțire la. Așa că trebuie să ne gândim puțin la asta. Dar nu trebuie să ne gândim prea mult la asta, pentru că această recurență este aceeași cu această recurență, care este aceeași cu această recurență. Am scris-o de trei ori acum. Deci soluția la aceasta este al n-lea număr Fibonacci. Oh scuze. Este puțin mai rău pentru că pe lângă acele recursiuni, petrec și timp constant pentru a face adăugarea, poate mai mult decât timp constant. Dar dacă numărăm doar numărul de adunări pe care le facem, acesta va fi plus 1 adunări. BINE. Dar acesta este mai mare decât al n-lea număr Fibonacci. Și dacă știi ceva despre numerele Fibonacci, acestea cresc exponențial. Sunt aproape proporția de aur până la sfârșit. Port proporția de aur, în caz că ai uitat numărul. Deci este rău, pentru că raportul de aur este mai mare decât 1. Deci aceasta este o creștere exponențială, după cum știm, mai ales în acest timp, creșterea exponențială este proastă. În algoritmi, creșterea exponențială este proastă, deoarece putem rezolva probleme foarte mici cu creșterea exponențială. Foarte mic n. Deci, acesta este un mod groaznic de a calcula al n-lea număr Fibonacci -- exponențial rău. OK, deci nu face asta. Dar există o modificare foarte mică la acest algoritm care îl face foarte bun, și anume memorarea. Și aceasta este o idee mare. Este ideea mare a programării dinamice. Este un cuvânt amuzant, probabil inventat de informaticieni. În loc de memorare, este memorare, pentru că vom scrie lucrurile într-un bloc de note. Este ideea. Și este o idee foarte simplă, care este doar amintirea și reutilizarea soluțiilor la subprobleme. Deci, să desenăm arborele recursiv pentru acest algoritm recursiv așa cum am făcut-o până acum. Deci, în partea de sus, lasă-mă să fac un pic de spațiu. În partea de sus numim f din n. Și apoi se numește f din n minus 1 și f din n minus 2. Și face o adunare aici sus. Și apoi aceasta numește f din n minus 2. Și aceasta numește f din n minus 3. Aceasta numește f din n minus 3. Și aceasta numește f din n minus 4. OK. Și observăm că această problemă secundară este aceeași cu această problemă secundară. Deci, pentru a calcula f de n minus 1, am nevoie de f de minus 3. Și, de asemenea, pentru a calcula f de n minus 2, am nevoie de f de n minus 3. Deci, de ce îl calculăm de două ori? Hai să o facem doar o dată. Când o rezolvăm, să o scriem într-un tabel undeva. Și atunci când vom avea nevoie din nou, vom reutiliza acea valoare. Întrebare? PUBLIC: Dar f din n minus 2? ERIK DEMAINE: f din n minus 2 este de asemenea partajat. Deci, permiteți-mi să folosesc un alt simbol. f din n minus 2 este deja aici. Deci asta a fost la același nivel. Dar obținem și reutilizare partajată între diferite niveluri. De fapt, nici măcar nu aș numi f de n minus 3 pentru că toată această parte nu trebuie calculată a doua oară. Dacă l-am calculat deja aici, nu contează care este primul. Să spunem că acesta este primul. Odată ce s-a terminat, îl pot nota și reutiliza aici. Și apoi aici, vom numi f din n minus trei. Deci, mai există un alt calcul al lui f de n minus 3. Când termin, nu va trebui să fac acest lucru recursiv. OK, așa că magic, acest lucru va face acest algoritm eficient cu această modificare foarte simplă. Permiteți-mi să notez modificarea mai explicit. Nu voi scrie cod aici. Dar descrie-o doar ca pe o structură de date. Așa că vom menține bunul nostru prieten, dicționarul, care este tipul sau interfața abstractă de date. Am putea folosi diferite structuri de date pentru a face acest lucru. Dar vom mapa unele probleme cu soluțiile lor, cel puțin pe cele pe care le-am rezolvat deja. Și, de obicei, putem face acest lucru doar cu o matrice de acces direct , deși ați putea folosi un tabel hash. Primiți doar săritura așteptată. Deci, atunci când scriem codul pentru funcția noastră recursivă - deci, în general, odată ce avem o descriere a botului de sortare, putem transforma aceasta în cod. Definim f din i. Și spune că sunt într-un caz de bază? Dacă da, returnați aceasta. În caz contrar, faceți acest apel recursiv. Acesta este algoritmul nostru recursiv. Dar acum vom face ceva mai mult. Și mai întâi vom verifica dacă această problemă secundară pe care încercăm să o rezolvăm a fost deja rezolvată. Și dacă da, returnăm acea soluție de stocare. Acesta este cazul ușor, dar s-ar putea să nu existe. Și apoi îl vom calcula în mod obișnuit. Deci, cum ar arăta codul pentru a defini f din i este mai întâi să verificăm că este i în structura noastră de date. Aceasta se numește de obicei notă. Așa că spunem, este această sub-problemă - sunt în structura mea de date de memoriu? Dacă da, doar returnați nota de i. Terminat. Nu este nevoie de recursivitate. În caz contrar, verifică dacă sunt un caz de bază. Dacă da, gata. În caz contrar, recurge. Deci, apelați recursiv f din i minus 1 și f din i minus 2. Și în această recursie, putem vedea că, după ce numim f din i minus 1, de fapt, va fi calculat deja f din i minus 2. Deci, în timp ce acest lucru apelul este recursiv, acesta se va termina imediat, deoarece i minus 2 va fi deja în tabelul de note. Și așa că, dacă te gândești la ceea ce se întâmplă, de fapt, vom avea doar recursivitate în ramura stângă a acestui lucru. Și toate ramurile potrivite vor fi gratuite. Putem doar să căutăm lucrurile în tabelul de note. Deci, care este durata generală de funcționare? Pentru Fibonacci, acesta ar trebui să fie ordinul n. De ce este ordinul n? Acesta este numărul de completări. Revino la asta într-o secundă. În general, modul de a analiza un algoritm ca acesta care utilizează memorarea este doar să numărăm câte sub-probleme diferite există? Pentru că odată ce rezolvăm sub-problema, nu o vom mai rezolva niciodată. Aceasta este ideea unui tabel de memorii. Deci vom rezolva fiecare subproblemă cel mult o dată. Și deci trebuie doar să numărăm, cât timp este nevoie pentru a rezolva fiecare sub-problemă? Și aici puteți vedea că este constant. Fie este un caz de bază și necesită timp constant, fie numim recursiv aceste lucruri. Dar acestea sunt sub-probleme diferite. Așa că le vom număra mai târziu. Și apoi munca care este de fapt făcută de această recurență este o singură adăugare. Deci, de fapt, sunt n completări. Pentru a calcula fn ar fi exact n adunări. Deci, se dovedește a fi o formă închisă foarte frumoasă în acest caz. Ar trebui să fie exact n subprobleme pentru a calcula f din n pentru că am început ca punct la 1. Și fiecare are câte una suplimentară-- Presupun că nu este cazul de bază. Poate n minus 2. OK. Cu siguranta comanda n. Acum, există această subtilitate care-- să uităm pentru un moment de programarea dinamică și să ne întoarcem la vechea prelegere unu și doi, vorbind despre cuvântul model ram de calcul. O întrebare aici care de obicei nu contează la această clasă. De obicei presupunem că adăugările necesită timp constant. Și de obicei facem asta pentru că de obicei este adevărat. Și, în general, modelul nostru este adăugările de biți w - unde w este dimensiunea cuvântului nostru de mașină - durează constant. Dar pentru această problemă și numai pentru această problemă, destul de mult, pentru numerele Fibonacci, se întâmplă să știu că numerele Fibonacci cresc exponențial. Deci, pentru a le scrie, de fapt, este nevoie de biți theta, deoarece sunt niște constante pentru puterea n. Și așa că sunt de fapt foarte mari. n este probabil mai mare decât w. De obicei, te gândești la probleme care sunt mult mai mari decât 64 sau oricare ar fi dimensiunea cuvântului tău. Presupunem că w este cel puțin log n. Dar n este probabil mai mare decât w. Poate fi mai mare sau mai mic. Nu știm. Și, în general, pentru a face o adăugare de n biți - acestea sunt adăugări de n biți - va avea un plafon de n peste w timp. Deci, în final, vom petrece acest timp n, pentru că trebuie să facem asta, multe dintre ele, care este n plus n pătrat în timpul w. Deci un timp de rulare puțin ciudat. Dar este polinom, în timp ce acest algoritm recursiv original a fost exponențial aici. Folosind această idee simplă de a ne aminti munca pe care am făcut-o, brusc acest algoritm de timp exponențial devine polinom. De ce? Pentru că avem puține probleme secundare. Am avut n subprobleme. Și pentru fiecare subproblemă, am putea scrie o relație de recurență prin care, dacă am ști deja soluțiile pentru subprobleme mai mici , am putea calcula această problemă mai mare foarte eficient. S-a întâmplat să fie timp constant sau adăugiri constante. n peste w timp. Dar atâta timp cât acesta este polinom și acesta este polinom, suntem fericiți, pentru că avem această formulă frumoasă că timpul necesar este, cel mult, suma tuturor subproblemelor relației de timp. Deci mă refer la subprobleme, cum ar fi un număr de ele și timpul necesar pentru a evalua acest lucru, ignorând apelurile recursive. Asta este important. Aceasta este partea nerecursivă. În note, eu numesc această lucrare nerecursivă. Deci, această formulă ne oferă o modalitate de a limita timpul de rulare al unuia dintre acești algoritmi dacă folosim memorizarea. Fără memorare, acest lucru nu este adevărat, Fibonacci la timp exponențial. Dar dacă adăugăm memorarea, știm că rezolvăm fiecare sub-problemă o singură dată. Și așa trebuie doar să vedem, pentru fiecare, cât m-a costat să-l calculez, presupunând că toată munca de recursivitate este gratuită, pentru că asta este deja luată în considerare de însumare. Deci, în special, această însumare este cel mult numărul de sub-probleme ori timpul per sub-problemă, care în acest caz era ordinul n. Am putea încerca să aplicăm acea analiză pentru sortarea prin îmbinare, pentru că la urma urmei, acesta este și un algoritm recursiv. Se întâmplă să nu beneficieze de memorare. Dar am putea introduce memorarea. Nu ne-ar răni. Dar dacă vă gândiți la graficul de apel aici, care este ca s de 0 m, care numește s de m-- 0 n peste 2 și o de n peste 2n și așa mai departe. Are aceeași imagine, dar de fapt nu există nicio substructură comună aici. Nu veți vedea niciodată o sub-problemă repetată, deoarece acest interval este complet separat de acest interval. Dar ai putea să arunci în memorie și să încerci să analizezi în același mod și să spui, ei bine, câte subprobleme există? Se pare că există n opțiuni pentru i și nu chiar n opțiuni, dar sunt cel mult n opțiuni diferite la pătrat. De fapt, suma numerică triunghiulară a lui i este egală cu 1 la n din i, diferite opțiuni posibile pentru inj. Dar acestea sunt sub-probleme theta n pătrat, care nu pare atât de bine. Și atunci cât timp petrecem pe sub problemă? Ei bine, pentru a rezolva s din ij, trebuie să îmbinăm cam atâtea elemente. Știm că îmbinarea necesită timp liniar. Și astfel, pentru a evalua acest lucru, este nevoie de theta j minus i. Și deci, ceea ce am dori să facem este să însumăm toate subproblemele lui j minus i. Acesta nu este numărul triunghiular, ci numărul tetraedric, cred. Și așa ajungem că timpul de rulare este, cel mult, n cuburi. Grozav. Deci este adevărat că n log n este mai mic sau egal cu n cub, dar evident că nu este foarte util. Acest algoritm, apropo, știm deja cum să-l analizăm este, într-adevăr, n log n. Și timpul de funcționare se dovedește a fi theta n log n. Deci, uneori, această ecuație nu este ceea ce doriți să utilizați. Dar de multe ori este suficient de bun. Și mai ales dacă doriți doar să obțineți o limită superioară a polinomului , atunci puteți încerca să o optimizați mai târziu. Acest lucru vă va oferi o limită superioară a polinomului, atâta timp cât numărul de sub-probleme este polinom și timpul pentru fiecare sub-problemă este polinom. Și într-adevăr, n cub este polinom. Nu este un polinom grozav, dar acesta este o modalitate alternativă de a analiza sortarea de îmbinare. Evident, nu faceți acest lucru pentru sortarea îmbinării. Dar ilustrează tehnica. Până aici e bine? Alte intrebari? În regulă. Lasă-mă să-mi amintesc unde suntem. Misto. Așa că următorul lucru pe care aș dori să-l fac este să vă arăt încă un algoritm pe care l-am văzut deja în această clasă care se potrivește foarte bine în această structură -- probabil că este un program dinamic -- și acestea sunt cele mai scurte căi DAG. Deci doar pentru a închide bucla aici, când spun programare dinamică, mă refer la recursivitate cu memorare. Adică, luăm-- scriem o bucată recursivă de cod, care este ca definiția unor argumente, o specificație a unei sub-probleme. Verificăm dacă problema este în tabelul de note? Dacă da, returnați nota de sub-problema. Și altfel verificați dacă este un caz de bază și rezolvați-l dacă este un caz de bază. Și în caz contrar, scrieți recurența recursă prin relație. Și setați tabelul de memorii al sub-problemei să fie unul dintre acele lucruri. OK, deci acesta este programul dinamic generic. Și implicit, scriu Fibonacci în acest fel. Și toate programele dinamice au această structură implicită în care încep cu un tabel de memorii care este gol și întotdeauna verific doar dacă sunt în tabelul de note. Dacă sunt, îl returnez. În caz contrar, calculez conform acestei relații recursive apelând recursiv f. Si asta e. Deci, acesta este fiecare algoritm DP va avea acea structură. Și folosește doar recursiunea și memorarea împreună. OK, deci acum să aplicăm acea tehnică pentru a ne gândi la problema celor mai scurte căi DAG. Problema a fost că îți dau un DAG. Vă dau un vârf sursă, S-- cele mai scurte căi cu o singură sursă. Calculați cea mai scurtă greutate a căii de la S la fiecare vârf. Acesta este scopul problemei. Și am văzut o modalitate de a rezolva asta, și anume relaxarea DAG. Îți voi arăta un alt mod, care se dovedește a fi practic același, dar cu susul în jos, sau răsturnat stânga- dreapta, în funcție de felul în care îți direcționezi marginile. Deci care sunt subproblemele noastre? Ei bine, aici, de fapt, sunt oarecum descrise pentru noi. Vrem să calculăm delta și SV pentru toate acestea. Deci aceasta este dimensiunea acestor sub-probleme. Se dovedește a fi suficient pentru această problemă generală. Și problema inițială pe care vrem să o rezolvăm sunt toate sub-problemele. Rezolvăm toate subproblemele, am terminat. Și apoi avem - cred că am scris asta la un moment dat în timpul prelegerii DAG cele mai scurte căi - avem o relație recursivă care spune că cea mai scurtă cale de a ajunge de la s la v este minimul celei mai scurte căi pentru a ajunge la un vârf. u plus greutatea muchiei de la u la v. De ce? Pentru că dacă ne uităm la un vârf v, dacă nu am început de acolo, am venit de undeva. Și astfel putem lua în considerare toate opțiunile posibile pentru vârful anterior u. Și dacă începi de la s și ajungi la v, trebuie să treci prin unul dintre ele. Și astfel, aceasta este să găsești cea mai bună cale dintre toate opțiunile tale. Care este cel mai bun mod de a ajunge la tine? Și apoi luați marginea de la u la v pentru toate marginile uv. Și acesta este adiacența minus. De obicei nu ne gândim la asta. De obicei, ne uităm la adiacență plus marginile de ieșire. Acestea sunt marginile de intrare. Și deci u este un incoming-- uv este o margine de intrare în v. OK, dacă luăm acel minim-- și, desigur, este posibil să nu existe nicio modalitate de a ajunge la v. Și așa voi arunca și infinitul în set . Luați minul acelui set. Asta îmi va oferi cea mai scurtă cale într-un grafic aciclic de la s la v. Și grozav, aceasta este recursiv. Aceasta a fost o sub problemă. Acestea sunt subprobleme care sunt mai mici, cred. Nu există o noțiune clară de mai mic aici, cu excepția faptului că știm deja că noțiunea clară de mai mic este ordinea topologică a DAG-ului nostru. Deoarece graficul nostru este aciclic, știm că are o ordine topologică. Știm cum să- l calculăm cu DFS. Și asta garantează că există o ordine topologică pentru a calcula aceste probleme. Și, de fapt, relația dintre probleme este exact graficul dat, G. Pentru a calcula calea cea mai scurtă de la s la v, trebuie să știu cea mai scurtă cale de la s la toate vârfurile de intrare la v. Și deci aceasta este Bănuiesc că în graficul de apel, acest vârf numește acest vârf, dar direcționează marginea în acest fel pentru a spune că acest vârf necesită-- acest vârf trebuie calculat înainte de acesta. Și astfel le pot completa într-o ordine topologică. OK, avem un caz de bază, care este delta lui ss egal cu 0. Și timpul de rulare este, din nou, putem folosi această formulă și să spunem, să însumăm toate subproblemele lucrării nerecursive în relația noastră de recurență și deci calculează acest min. Dacă ți-am oferit aceste delte gratuit și ți-am dat aceste ponderi, pe care le știm din structura noastră de date de pondere, cât timp durează să calculezi acest min? Ei bine, oricât de multe lucruri ar fi, oricât de multe numere am depășit, care este dimensiunea listei de adiacență primite plus 1 pentru acel infinit. Și deci, dacă calculați această sumă, suma muchiilor de intrare la fiecare vârf, acestea sunt toate muchiile. Deci acesta este v plus e. Deci, de fapt, acest algoritm este din punct de vedere moral același algoritm cu cel pe care l-am văzut în cursul DAG cu calea cea mai scurtă , care a fost să calculeze o ordine topologică și să proceseze vârfurile în acea ordine și să relaxeze marginile care ies din vârfuri. Așadar, aici-- așa că în acel algoritm, am fi încercat să relaxăm această margine dacă ar exista o cale mai bună către v. Și prima este cu siguranță mai bună decât infinitul. Deci primul ne relaxăm într-adevăr. Următoarea margine, dacă aceasta ar oferi o cale mai bună de la s la v, atunci am relaxa acea margine și am actualiza drumul aici și am face același lucru aici. În cele din urmă, doar calculăm acest min în algoritmul de relaxare, dar o facem pas cu pas. În algoritmul de relaxare, relaxarea DAG, pentru fiecare muchie de intrare la v, actualizăm d din e dacă este mai bine. Și așadar, dacă actualizați în mod repetat, dacă vă simțiți mai bine, asta ajunge să calculeze un min. OK, deci acesta este același algoritm doar cam inversat. Un lucru amuzant, deși am notat ordinea topologică a graficului sub-problema aici este ordinea topologică a lui g, deoarece graficul sub-problema este g, algoritmul nu trebuie de fapt să calculeze unul. O face automat gratuit. Dacă vă gândiți la acest algoritm, algoritmul generic dp, care este să verificați dacă suntem într-un tabel de memorii. Dacă da, întoarceți-vă. În caz contrar, recurs sau caz de bază. Aceasta este de fapt o căutare în profunzime prin graficul sub-problemei -- din punct de vedere tehnic, prin reversul graficului sub-problemei. Dacă desenez o margine, deci de la mic la mare, așa că spun doar, orientez marginile de la sub-problemele mele mai mici către cele care au nevoie de ea, atunci de fapt caut mai întâi adâncimea înapoi în acest grafic deoarece problema mai mare numește problema mai mică. Și tabelul de memorii servește drept verificarea „am vizitat deja acest vârf” în DFS. Deci, acesta este de fapt un algoritm DFS. În plus, facem niște calcule pentru a rezolva efectiv sub-problemele care ne interesează. Deci implicit în acest algoritm, facem un DFS și, în același timp, facem acest calcul al celui mai scurt drum în ordinea finală a acelei traversări DFS, deoarece toate marginile sunt înapoi. Aceasta este aceeași cu ordinea inversă de finisare dacă graficul este înainte. Deci, în cele din urmă, calculăm o ordine topologică, deoarece programarea dinamică include în ea prima căutare aprofundată. Multe cuvinte. Dar este destul de grozav că acest cadru doar rezolvă cele mai scurte căi DAG fără prea multă muncă. Adică, am muncit mult pe căi scurte pentru a demonstra că această relație este adevărată. Odată ce știi că este adevărat, partea de algoritm este aproape gratuită. Scrieți doar SRTBOT și gata. BINE. Acest lucru ne duce la, în general, în acest moment, am văzut două exemple de programare dinamică. Bănuiesc că, din punct de vedere tehnic, tipul de îmbinare ați putea fi considerat un program dinamic, dar de fapt nu reutiliza nimic. Deci nu este interesant. Și într-adevăr, asta ne-a dat o legătură foarte proastă. Cu siguranță am văzut cele mai scurte căi DAG și numerele Fibonacci ca două exemple interesante. Și despre ce va fi următorul restul acestei prelegeri și următoarele trei prelegeri vor fi din ce în ce mai multe exemple de programare dinamică și cum o puteți folosi pentru a rezolva probleme din ce în ce mai generale. Până acum, tocmai am rezolvat o problemă ușoară și o problemă pe care deja știam să o rezolvăm. Să trecem la o nouă problemă, care este bowlingul. Bowling-ul este popular în Boston. Bostonului îi place să joace bowling cu lumânări, ceea ce este puțin neobișnuit. Astăzi vom juca un joc de bowling și mai neobișnuit , unul pe care l-am inventat pe baza unui joc de bowling pe care l-a inventat Henry [INAUDIBLE] în 1908. Așa că bowling antic, îl voi numi, sau cred că bowlingul liniar este cum l-as putea numi. O să-i spun bowling aici. Și acum voi încerca să desenez un pin de bowling. Nu-i rău. S- ar putea să se înrăutățească progresiv. Așa că imaginați-vă n ace de bowling identice. Vă rog să prefaceți că acestea sunt identice. Și am o minge care are aproximativ aceeași dimensiune ca un pin de bowling. Acești ace de bowling sunt destul de aproape unul de altul. Ar fi trebuit să las un mic gol aici. Și ești un bowler cu adevărat bun. Acum, din păcate, aceste ace de bowling sunt pe o linie. Și joci bowling de la infinit. Așa că atunci când joci, poți lovi doar un ace sau doi ace sau zero ace. Dar probabil că vrei să lovești niște ace. Deci, dacă aruncați direct din știft, veți lovi doar acel știft. Și dacă arunci la mijloc între doi ace, vei doborî -- asta e o minge, îmi pare rău -- vei doborî doi ace. Și acesta este modelul tău de bowling, modelul de calcul. Acum, ceea ce face acest lucru interesant este faptul că pinii au valori. Pin i are valoare - aceasta este, evident, o problemă cu jucăriile, deși această problemă - acest tip de bowling datează din 1908, a fost și o problemă cu jucăriile în acel cadru. Așa că fiecare dintre acești ace de bowling are un număr pe el, să spunem 1, 9, 9 -- Voi face un exemplu puțin mai interesant, poate încă unul aici și un 2 și un 5 și un 5, ceva de genul acesta. BINE. Sau poate faceți-l puțin mai interesant. Să punem câteva numere negative aici. BINE. Și modelul... așa că ești la bowling de carnaval. Fiecare pin are valori diferite, potențial diferite. Și modelul este că dacă ai lovit un știft, i, atunci primești vi puncte. Deci, e direct. Pentru a-l face interesant, atunci când lovești două ace, primești produsul. Deci, dacă lovesc doi ace, sunt întotdeauna i și i plus 1 pentru un I. Primești de vi ori vi plus 1 puncte. Acesta este jocul pe care îl jucați. Și nu contează cu adevărat că acesta este un produs. Produsul este doar o funcție ciudată care este greu de imaginat. Dacă te uiți la asta suficient de mult, ar trebui să te convingi că soluția optimă este probabil să-- așa că, pentru fiecare dintre aceste numere, aș putea să- l las singleton sau să- l asociez cu vecinul din stânga sau să-l asociez cu vecinul din dreapta. Dar perechile nu se pot suprapune pentru că odată ce am lovit un ac, acesta a dispărut. Este răsturnat. Dispare. Deci, din cauza acestor nouă, care au o valoare foarte mare, probabil că mi-aș dori să le lovesc pe amândouă împreună, așa că împerecheați-le, pentru că de 9 ori 9 este 81. Este foarte mare, mult mai bine decât să le lovesc individual. sau a lovi de 9 ori 1 sau 9 ori 2. 1 și 1 este cam amuzant, pentru că de fapt este mai bine să- i lovești individual. Asta vă va oferi două puncte, în timp ce dacă le-aș împerechea, voi obține doar un punct. 2 și minus 5, pare rău. 10 puncte negative. Scopul meu este să maximizez scorul. Trebuie să lovești toate știfturile? Să spunem că nu, nu trebuie să lovești toate ace. Așa că aș putea sări peste minus cinci. Dar, de fapt, aici, pentru că sunt adiacente, minus 5 ori minus 5 este bine. Adică 25 de puncte. Deci, soluția optimă pentru această instanță este să loviți toate pinii, acestea pozitive, acestea împreună, acestea împreună. Dacă aș adăuga, de exemplu, un alt pin de minus 3 aici, aș alege să nu lovesc acel pin. Buna intrebare. Așa că te joci până când ești obosit. Când decideți să vă opriți din joc, cum vă pot maximiza scorul? Există multe variante ale acestui joc. Toate acestea - practic orice variație - nu literalmente orice variație, dar multe, multe variații ale acestei probleme pot fi rezolvate rapid cu programare dinamică. Dar haideți să o rezolvăm pe aceasta. BINE. Deci acum suntem într-adevăr în modul de proiectare algoritmică. Trebuie să ne gândim la SRTBOT. Și în special, trebuie să ne gândim care ar fi problemele secundare aici? Și în acest moment, nu avem prea mult ajutor. Așa că ar trebui probabil să-ți dau niște instrumente. Dacă vreau să rezolv o problemă ca aceasta, intrarea este o secvență de numere. Este o structură de date secvențială. Poate că este o matrice de numere, care este această matrice v. Și să vedem. Un instrument general pentru proiectarea sub-problemelor care va acoperi majoritatea problemelor -- poate toate problemele pe care le vedem în această clasă pentru programarea dinamică. Iată un truc. Dacă intrarea dvs. este o secvență, iată câteva sub-probleme bune de luat în considerare. Am putea face toate prefixele. Deci, să numim șirul x. Deci am putea face x înseamnă prefix până la un i dat pentru tot i. Am putea face toate sufixele, x de la i înainte pentru tot i. Sau am putea face subșiruri, care sunt elementele consecutive de la i la j. Nu scriu aici urmatoarele. Subsecvența înseamnă că puteți omite elemente din mijloc. Deci subșir trebuie să începeți într-o anumită poziție și să faceți toate lucrurile până la j. Deci acestea sunt drăguțe, ușor de exprimat în notația Python. Și acestea sunt grozave, pentru că sunt polinomiale. Dacă am n lucruri - dacă lungimea secvenței mele, x, este n, atunci există n prefixe - din punct de vedere tehnic n plus 1. Deci, să facem prefixe theta n. Există sufixe theta n. Și există subșiruri theta n pătrate pentru că există n-- aproximativ n opțiuni pentru i și j separat. Îmi pare rău? Subsecvențe. Bun. Dreapta. Nu am scris sub-secvențe, pentru că, de fapt, există exponențial multe sub-secvențe. Este 2 la n. Pentru fiecare articol, l- aș putea alege sau nu. Deci nu vreau să parametrizez-- Nu vreau ca subproblemele mele să fie subsecvențe pentru că asta este garantat-- ei bine, atunci ești garantat că vei obține un număr exponențial de sub-probleme, ceea ce este rău. Am dori să echilibrăm numărul de sub-probleme prin polinom. Deci acestea sunt trei moduri naturale de a obține limite polinomiale. Acum, prefixele și sufixele sunt în mod evident mai bune, deoarece sunt mai puține, liniare în loc de pătratice. Și, de obicei, aproape toate problemele pe care le întâmpinați, prefixele și sufixele sunt la fel de bune. Chiar nu contează pe care o alegi. Așa că poate ți-ar plăcea să te gândești la... ei bine, vom ajunge să... alegeți care este mai confortabil pentru dvs. Dar uneori nu este suficient. Și va trebui să mergem la subșiruri. Asta nu va fi pentru o altă prelegere sau două. Astăzi susțin că prefixele sau sufixele sunt suficiente pentru a rezolva problema bowling-ului. Deci, ceea ce vom face este să ne gândim la... Prefer sufixele de obicei, pentru că îmi place să lucrez de la stânga la dreapta, de la început până la sfârșit. Așa că ne vom gândi la un sufix al pinurilor de bowling. Și, deci, care este sub-problema pe un sufix? Ei bine, o versiune naturală este doar pentru a rezolva problema inițială, bowling-ul. Cum îmi maximizez scorul dacă tot ce mi s-a dat erau acești pini? Să presupunem că pinii din stânga lui nu au existat. Cum mi-aș maximiza scorul pe pinii rămași? Sau pentru acest sufix, având în vedere acești patru pini, ce aș face? Și există câteva probleme ciudate de sub aici. Dacă ți-aș da ultimul pin, ce ai face? Nimic. Este clar diferit de ceea ce aș face la nivel global aici. Dar pretind că dacă pot rezolva toate sufixele îmi pot rezolva problema inițială, deoarece unul dintre sufixe este întreaga secvență. Deci hai sa o facem. Sortați după pentru bowling. Deci, iată programul nostru dinamic. Subproblemele sunt sufixe. Așa că voi scrie b din i este scorul maxim pe care l-am putea obține cu startul nostru -- dacă am început un joc cu ace i, i plus 1, până la n minus 1, care este un sufix al acelui. Foarte important ori de câte ori scrieți un program dinamic pentru a defini care sunt subproblemele dumneavoastră. Nu spuneți doar cum să le calculați, ci mai întâi spuneți care este scopul problemei secundare. Aceasta este o greșeală comună să uiți să spui ce încerci să faci. Deci acum am definit b din i. Acum, care este lucrul original pe care încerc să-l rezolv? Ați pus și SRTBOT -- ați putea pune O mai devreme, apoi de fapt vrăjește sortare. Deci de ce nu fac asta pentru distracție. Problema inițială pe care încercăm să o rezolvăm este b de 0, deoarece acestea sunt toți pinii. Sufixul care începe cu 0 este totul. Deci, dacă putem rezolva asta, am terminat. Urmează r pentru relație. Acesta este testul, dacă am înțeles corect sub-problemele, este dacă pot scrie o relație de recurență. Deci hai să încercăm să o facem. Vrem să calculăm b din i. Deci avem pinul i aici și apoi pinii rămași. Și ideea cea mare aici este să mă gândesc doar la -- lucrul frumos despre sufixe este că dacă scot ceva de la început, mai am un sufix. Amintiți-vă, scopul meu este să iau această subproblemă, care este sufixul care începe cu i, și să o reduc la o sub problemă mai mică, ceea ce înseamnă un sufix mai mic. Așa că aș dori să decupez unul sau două articole de aici. Și atunci problema rămasă va fi una dintre problemele mele secundare. Voi putea apela recursiv b a ceva mai mic decât i-- sau îmi pare rău, b a ceva mai mare decât i va fi o subsecvență mai mică pentru că începem mai târziu. OK, deci ce aș putea face? Ei bine, ideea este să mă uit doar la pinul i și să mă gândesc, ei bine, ce aș putea face pentru a fixa pe i? Nu am putut să-l lovesc niciodată cu o minge. Aș putea sări peste el. Aceasta este o opțiune. Care ar fi scorul meu atunci? Ei bine, dacă omit pinul i, rămân pinii rămași, care este doar un sufix mai mic. Deci, b din i plus 1. Voi scrie un maxim aici pentru că aș dori să-mi maximizez scorul. Și una dintre opțiuni este, uitați de pinul i. Doar rezolvă restul. O altă opțiune este să arunc o minge. Și exact am lovit pinul i. Ăsta e un lucru pe care l-aș putea face. Și ar lăsa exact același rest. Deci, o altă opțiune este b din i plus 1 plus vi. De ce aș prefera asta decât asta? Ei bine, dacă vi este negativ, aș prefera asta. Dar dacă vi este pozitiv, de fapt aș prefera asta decât asta. Deci vă puteți da seama care este mai bun, doar la nivel local. Dar mai este un lucru pe care îl pot face, și anume poate că am lovit acest știft într-o pereche cu un alt știft. Acum, nu există niciun pin în stânga acestuia. Presupunem că avem doar sufixul. Și astfel, singurul lucru pe care îl pot face este să arunc o minge și să lovesc i împreună cu i plus 1. Și apoi primesc produsul. Acum, ce ace rămân? i plus 2 pe. Încă un sufix. Deci, dacă elimin unul sau două elemente, desigur, mai primesc un sufix -- în acest caz, b din i plus 2 -- și apoi numărul de puncte pe care le adaug sunt de vi ori vi plus 1. Deci, acesta este maxim trei lucruri. Deci, cât timp îmi ia să-l calculez? Reclam timp constant. Dacă nu număr timpul necesar pentru a calcula aceste alte probleme secundare, care sunt mai mici pentru că sunt sufixe mai mici mai în dreapta, atunci fac câteva completări -- produs, max. Acestea sunt toate numere frumoase și voi presupune că trăiesc în cuvântul w-bit, pentru că facem doar produse de dimensiuni constante. Asta e bine. Deci, aceasta necesită muncă constantă, nerecursivă. Câte probleme secundare sunt? Ei bine, sunt sufixe, deci este un număr liniar de subprobleme. Și astfel, timpul de care voi ajunge să am nevoie este de numărul de subprobleme, n, ori munca nerecursivă pe care o fac pe subproblemă, care este constantă. Și deci acesta este timpul liniar. Grozav. Și nu am terminat SRTBOT, așa că există un alt t, care este să mă asigur că există o ordine topologică și care este în ordine descrescătoare. Sau aș putea scrie asta ca o buclă for - pentru i este egal cu n, n minus 1. Aceasta este ordinea în care mi- aș calcula problemele, deoarece sufixul care începe la n este sufixul gol. Sufixul care începe la 0, acesta este cel pe care vreau să îl calculez. Acesta este sufixul final pe care ar trebui să-l calculez. Și apoi avem un b pentru cazul de bază, care este primul caz, b de n este egal cu 0, pentru că nu există pini. Deci nu primesc niciun punct. Trist. OK, deci asta este. Luăm doar aceste componente, le conectăm la acest algoritm recursiv, memorat și avem un algoritm de timp liniar. Vreau să menționez pe scurt un mod diferit în care puteți conecta acele piese, care se numește de jos în sus dp, care este-- să o facem pentru acest exemplu. Deci, dacă am... să vedem. Permiteți-mi să încep cu cazul de bază, b din n este egal cu 0. Dar acum este o sarcină. Și voi face bucla for din ordinea topologică pentru i egal cu n, n minus 1 la 0. Acum voi face relația, b din i este egal cu max de b din i plus 1 și b din i plus 1 plus bi și b din i plus 2 plus di vi plus 1. Din punct de vedere tehnic, acest lucru funcționează numai dacă i este strict mai mic decât n minus 1. Așa că ar trebui să am un dacă i este mai mic decât minus 1 pentru ultima parte, deoarece pot face doar -- Pot lovi doar doi ace dacă au mai rămas cel puțin doi ace. Și apoi returnați b de 0. Deci, ceea ce tocmai am făcut a fost o transformare din acest șablon SRTBOT într- un algoritm non-recursiv, un algoritm de buclă for, în care mi-am scris mai întâi cazul de bază. Apoi mi-am făcut ordinea topologică. Apoi mi-am făcut relația. Apoi, la sfârșit, mi-am făcut... nu cazul de bază. Problema inițială. Și cu condiția să vă scrieți ordinea topologică ca niște bucle for. Aceasta este de fapt o modalitate excelentă de a scrie un dp ca cod. Dacă ar fi să implementez acest algoritm, l- aș scrie așa, pentru că este super rapid. Fără apeluri recursive. Doar unul pentru buclă. De fapt, acesta este aproape un algoritm banal. Este uimitor că asta rezolvă problema bowling-ului. Într-un anumit sens, iau în considerare toate strategiile posibile pe care le-aș putea face pentru bowling-ul acestor ace. Ceea ce folosim este ceea ce ne place să numim forță brută locală, unde atunci când ne gândim la pinul i, ne uităm la toate lucrurile posibile pe care le-aș putea face pentru a fixa i, aici există într-adevăr doar trei opțiuni de ceea ce aș putea face. Acum, în mod normal, dacă aș încerca toate opțiunile pentru pinul i și apoi toate opțiunile pentru i plus 1 și i plus 2 și așa mai departe, asta ar fi exponențial. Ar fi de 3 ori de 3 ori 3. Asta e rău, dar pentru că pot reutiliza aceste subprobleme, se dovedește a fi doar timp liniar. Este aproape ca o magie. dp-- dp este în esență o idee de utilizare a forței brute locale. Și prin definirea unui număr mic de sub-probleme din față - și atâta timp cât rămân în acele subprobleme, atâta timp cât recurg mereu în acest spațiu polinomial, ajung să fac doar muncă polinomială, deși eu' într-un anumit sens, explorez exponențial multe opțiuni. Și se datorează faptului că ceea ce fac cu acest pin nu depinde prea mult de ceea ce fac unui pin mult mai târziu. Există o mulțime de intuiție aici pentru ce... când DP funcționează. Dar vom vedea mai multe exemple în acest sens . Și vreau doar să menționez că intuiția pentru a scrie o recurență ca aceasta este să te gândești la -- în cazul sufixelor, vrei să te gândești întotdeauna la primul element, sau poate la primele două elemente. În cazul prefixelor, te gândești mereu la ultimul element. Și pentru subșiruri, ar putea fi orice articol - poate în mijloc. Dacă elimin un element din mijlocul unui subșir, primesc două subșiruri, așa că pot recurge. Aici sau în general, ceea ce vrem să facem este să identificăm o caracteristică a soluției pe care dacă am ști acea caracteristică am fi terminat. Ne-am reduce la o sub problemă mai mică. În acest caz, spunem doar, ei bine, care sunt lucrurile posibile pe care le-aș putea face primului pin? Există trei opțiuni. Dacă aș ști ce opțiune este, aș fi terminat. Aș putea recurge și să-mi fac adăugarea. Acum, nu știu ce lucru vreau să fac. Așa că le încerc pe toate și iau maxim. Și dacă maximizezi, iei maxim. Dacă minimizați, luați min. Uneori iei un sau sau un și. Ar putea exista o funcție de combinație. Pentru probleme de optimizare în care încercați să maximizați sau să minimizați ceva, cum ar fi cele mai scurte căi pe care încercați să le minimizați, le punem aici. Deci, de obicei, este min sau max. Și acest lucru este extrem de puternic. Tot ce trebuie să faci... partea grea este această parte de design inspirat în care spui, ce trebuie să știu care să mă permită să-mi rezolv problema? Și dacă puteți identifica asta și numărul de opțiuni pentru ceea ce trebuie să știți este polinom, atunci veți putea obține un program dinamic polinom. Asta e intuiția. Veți vedea mult mai multe exemple în următoarele trei prelegeri.