Bine ați venit la marea finală a programării dinamice din 6006 patru din patru astăzi, ne vom concentra pe un anumit tip de sub- problemă pe care am văzut-o la început cu Fibonacci, adică atunci când aveți o intrare întregă și un lucru natural. de a face cu acel număr întreg este să ne uităm la versiuni mai mici ale acelui întreg și acest lucru ne va conduce la o nouă noțiune numită timp pseudo-polinom, am vorbit mult în această clasă despre timpul polinom fiind un timp bun de rulare, dar pseudopolinom este un timp de rulare destul de bun și vom vorbi despre asta și se referă la aceste numere întregi, ne vom uita doar la două exemple noi de examen tăierea tijei și suma subsetelor, dar apoi vom revizui toate exemplele pe care le-am văzut de la fel de perspectivă diagonală, așa că uh, ca de obicei, aplicăm cadrul nostru swordbot cu subprobleme relații ordine topologică cazuri de bază problema originală și timp revizuire rapidă uh am văzut, așa că cea mai grea parte este să obținem setul potrivit de subprobleme uh și există câteva alegeri naturale pentru secvențe încercăm prefixe sufixe subșiruri pentru numere întregi, cum ar fi în Fibonacci, există un număr dat și doriți să calculați că la al-lea număr Fibonacci ceea ce am ajuns să facem a fost să rezolvăm numerele Fibonacci pentru toate numerele de intrare introduse numere întregi între 0 și acel număr n sau în acest majusculul k și aceasta este o tehnică generală și vom mai vedea două exemple în acest sens astăzi, altfel luăm produse din acestea și adesea este suficient, dar uneori trebuie să adăugăm mai multe subprobleme în ceea ce numim extinderea sub-problemei, adesea cu constrângeri suplimentare care haideți să ne amintim o stare din trecut, exemplul meu canonic, care este degetarea pianului, în care a trebuit să ne amintim care a fost sarcina noastră de degetare, într-un anumit sens, de la pasul anterior, pentru a calcula costul de tranziție și aceasta este o tehnică foarte puternică pe care o puteți folosi. să-ți placă să joci în mod optim Super Mario Brothers dacă ai un ecran de dimensiune constantă și tot ce trebuie să-ți amintești este ce este în ecranul de dimensiune constantă, dacă tot ce se resetează în afara acelui ecran, poți doar să adaugi acea stare ca parametru la problema ta secundară și tu" Oricum, voi putea rezolva rezolvarea fraților super mario foarte util și acesta a fost un fel de punctul central al ultimei prelegeri, nu vom vorbi prea mult despre asta astăzi și apoi vom raporta aceste subprobleme în mod recursiv și acesta este practic testul dacă dvs. Definiția sub-problemei a fost corectă este puteți scrie o relație de recurență care este doar un algoritm recursiv și există o procedură generală bună pentru cum să veniți cu aceste relații, care este să vă gândiți doar la o întrebare despre soluția sub-problemei pe care dacă o aveți știam că răspunsul s-a redus la sub-probleme mai mici și apoi ai forțat la nivel local toate răspunsurile la acea întrebare, la care îmi place să cred că ghicesc răspunsul corect și apoi apelezi direct lucrurile recursive, dar la sfârșit trebuie să plătești pentru acea ghicire, parcurgând toate ipotezele posibile pentru a garanta că o găsiți pe cea potrivită, așa că, odată ce ați identificat această întrebare, este foarte ușor dp este doar despre forța brută orice doriți și, de obicei, aceasta duce la un timp de rulare destul de bun, ca Atâta timp cât numărul de răspunsuri posibile la acea întrebare este polinom, atunci trebuie să verificăm că această relație este aciclică și apoi se reduce adesea la găsirea unei căi, cum ar fi calea cea mai scurtă sau ceva într-un dag, subproblema dag uh avem nevoie de niște cazuri de bază. trebuie să ne asigurăm că putem rezolva problema inițială folosind una sau mai multe subprobleme și apoi analizăm timpul de rulare ca de obicei un număr de subprobleme ori mai mult decât cantitatea de muncă nerecursivă din relație plus oricât de mult timp ne-a luat pentru a rezolva problema. problema inițială bine, așa că acesta a fost cadrul nostru, l-am văzut acum de patru ori ușor rafinat de fiecare dată când am adăugat în mare parte câteva tehnici generale pentru definirea subproblemei și cum să scriem relații, așa că hai să facem un nou exemplu, care este tăierea tijei, aceasta va fi destul de simplu, dar va servi ca un contrast cu următorul exemplu despre care am vorbit despre suma subsetului, deci care este problema cu numele tijei vine din cartea clrs, dar este de fapt o problemă destul de practică, poate nu pentru tăierea tijelor, dar vă puteți imagina că sunteți am o resursă de o anumită lungime Îmi place să cred pentru că am fost la uh la rafturi din lemn de esență tare recent, îmi place să mă gândesc că ai o scândură mare de lemn de esență tare și primești un preț pentru a vinde acea lungime, dar ai putea, de asemenea, să tai acea scândură în mai multe bucăți de diferite lungimi care se însumează la l și le-ați putea vinde individual, poate veți câștiga mai mulți bani așa, despre asta este problema, așa că vi se oferă valoarea fiecărei lungimi posibile pe care o puteți tăia, vom presupune că toate legăturile trebuie să fie numere întregi și scară, astfel încât să fie adevărat, deci majuscul l aici este lungimea originală little l este lungimea candidată a unei piese pe care ați putea să o tăiați și v din l este valoarea pentru tăierea unei lungimi uh l tija secundară și noi Vom presupune că, atunci când tăiem, nu pierdem niciun material, uh, probabil că ați putea să vă adaptați pentru asta, dar nu este îngrozitor de interesant și vrem să știm care este cea mai bună modalitate de a împărți lanseta noastră mare de lungime capitală l în diferite lansete. de lungime mică l diferite lungimi potențial diferite, așa că o voi numi partiția valorii maxime în matematică, aceasta se numește partiție a unui grup de numere care însumează un anumit număr și dorim să maximizăm valoarea totală în mod natural, așa că iată un exemplu, să spunem că lungimea inițială este șapte și avem acest tabel pentru lungimile unu doi trei patru cinci șase șapte toate lungimile diferite pe care o voi scrie o valoare care este un număr întreg care decupează o rută de acea lungime și o vinde selectați prețul de vânzare este probabil monoton dar nu trebuie să fie, poate oamenilor le place foarte mult puteri de cumpărare de două lungimi sau ceva de genul acesta și astfel acelea se vând mai mult, așa că nu trebuie să fie monoton, dar în acest exemplu este și așa am această rută de lungime șapte și aș putea îl vând direct cu 32 de dolari, să zicem, dar l-aș putea împărți și în: uh, o lungime, o lansetă și o lungime șase sau o lungime, o lansetă și două lungime, trei sau o lungime trei și patru, orice însumează șapte și probabil Cel mai firesc lucru de făcut pentru această problemă este ca o euristică, aceasta ar fi un lucru lacom pentru bani. maximizez că asta ar fi dacă ar trebui să aleg un singur articol și să vând multe din acel tip, care ar fi lucrul optim de făcut, astfel încât acesta are un raport de unul care este rău, are un raport de cinci care este mai bun și te uiți la este suficient de lung, cred că șase este cel mai bun are cel mai mare raport puțin mai mult decât uh, nu pot împărți um puțin mai bine decât um hai să vedem puțin puțin mai rău decât patru sau a fost al patrulea cel mai bun puțin mai rău decât patru ce vrei să spui, oh, puțin i vezi că raportul este puțin mai mic de patru, mulțumesc, da, uh, care toate acestea sunt oarecum mai rele, de exemplu doi, dacă dublez valoarea lui 3, obțin 26, ceea ce este cu mult mai puțin de 31 și cred că este cel mai apropiat concurent. este 2 pentru că dacă înmulțiți acest lucru cu 3 obțineți 30. deci, dacă am vândut trei doi, primesc 30, dar dacă vând unul șase, care este aceeași cantitate, primesc 31, deci o ușoară îmbunătățire și astfel acest articol maximizează raportul dintre bani și dolari. și deci o pereție naturală este șase plus unu, vand o tijă de lungime șase și asta lasă o tijă de lungime unu și asta îmi va da uh 31 pentru șase și un dolar care îmi oferă 32 de dolari uh, dar asta se dovedește a nu fi. cel mai bun, care este de fapt același ca și cum tocmai l-ați vândut, dar de fapt, puteți face mai bine vânzând acest lucru, nu este evident, uitați-vă la el pentru o vreme, trei și patru, de asemenea, însumează 7, apoi obținem 13 plus 18, care este sper că mai mare 33 30 să înțeleg bine, nu, nu am înțeles bine, uh, e prea mic, o să le luăm pe acestea două și să le vindem 3 plus 2 plus 2. apoi primesc 13 plus 10 plus 10 ține minte că doi au fost mai întâi un concurent apropiat pentru raportul pentru șase, deci este puțin mai bine să vindem doi doi doi și apoi trei pentru că atunci obținem treizeci și trei de dolari și se dovedește a fi cel mai bun pentru această problemă și pare foarte dificil să ne dăm seama, în general, există exponențial, multe partiții diferite nu își pot permite să le încerc pe toate întrebarea pot avea valori negative pot avea valori negative aici, cred că va funcționa bine, nu am voie să am lungimi negative sau lungimi zero, nu vreau zero lungime să- ți dau ceva pentru că atunci am tăiat infinit de zerouri, dar v-ul lui l cred că ar putea fi negativ, da, trebuie să folosesc o bară întreagă, uh, în această problemă, da, cred că nu s-ar schimba prea mult dacă ai face-o Nu trebuie să folosim întreaga bară, ne putem gândi la acelea după ce scriem dp, deci hai să rezolvăm asta cu sort bot, deci care este intrarea la această problemă, bine avem, uh, nu am menționat că aceasta este o lungime întreagă, lungime întreagă pozitivă, deci avem o intrare care este un întreg l și avem o altă intrare care este, cred că este ca o matrice de numere întregi, deci aceasta este o secvență și acesta este un întreg, așa că dacă ne uităm la lista noastră de subprobleme frumoase, am putea încerca prefixe sau sufixe sau subșiruri ale structurii de valori sau am putea încerca pentru acel întreg numere întregi mai mici, asta este de fapt ceea ce prefer, cred că modul de a gândi la asta este să trecem înainte la ce vrem la ce caracteristică a soluției vrem să ghicim și probabil că ar trebui să ne gândim care este o lungime de lansetă pe care o vom tăia și vinde, bine, așa că am această lansetă mare, poate o vând toată, poate am tăiat un lucru de mărimea unu și o vând, poate am tăiat un lucru de dimensiunea doi și să-l vând, dar trebuie să vând ceva dacă nu vând nimic și deci nu sunt decât n diferite sau există doar l opțiuni diferite pentru ce lungimi de tijă să tăiem mai întâi și astfel putem doar cu forța brută. comandă l timp, deci ce problemă avem dacă tăiem un întreg de o lungime mică l, ei bine, avem aceeași problemă cu o tijă de lungime majusculă l minus mic l valorile nu se schimbă se întâmplă că nu voi face Folosește valorile mari dacă elimin o parte din problemă, dar îmi place să mă gândesc la asta, deoarece tot ceea ce facem este să scădem l mare și astfel problemele mele secundare vor fi mai puține pentru fiecare l mică. decât sau egal cu mare l rezolvă acea problemă, deci x din l este partiția de valoare maximă de lungimea uh l mic l pentru l mic este egal cu zero unu până la mare l bine, deci aceeași problemă, dar cu opțiuni diferite pentru l mare, deci se folosește asta Problemă sub întreg acum, în acest exemplu, care se întâmplă să corespundă cu prefixele matricei v, deoarece dacă am doar lungime de până la mic l, chiar am nevoie doar de prefixul matricei de valori până la mic l, așa că ați putea să vă gândiți la asta. este, de asemenea, în regulă, dar cred că acest fel este puțin mai generalizabil, bine, așa că susțin că acesta este un set bun de subprobleme pentru că pot scrie o relație de recurență care este de fapt destul de simplă, așa cum am spus, uh, vrem să alegem o piesă, așa că am" Mi-a dat o lansetă de lungime mică. Vreau să aleg cât de mult din acea lansetă să vând în bucata următoare, astfel încât să pot tăia ceva mai lung sau să pot vinde totul sau să tai orice dimensiune a piesei între ele și banii pe care i-am va obține pentru că este oricare ar fi valoarea acelei piese plus recursiv maximul pe care îl pot obține de la toate piesele rămase. Îmi pare rău de la lungimea rămasă, care este puțin l minus p bine, așa că foarte simplu în cadrul formulei, doar valoarea pentru prima piesă. ghicim care este prima piesă pe care o vom tăia și o vom vinde, obținem valoarea piesei respective și apoi, recursiv, vedem ce este mai bine să facem cu restul, acum nu știm ce dimensiune ar trebui să aibă prima piesă, așa că pur și simplu încercăm toate opțiunile posibile pentru p și luăm maximul pe care îl ieșim din această formulă peste acea alegere și este garantat să găsim cel mai bun în general, deoarece trebuie să tăiem o bucată acum dacă ați vrut să permiteți să nu vindeți nimic în cazul numerelor negative, ați putea adăuga un zero la acest maxim și apoi s-ar putea să vă opriți mai devreme dacă nu a mai rămas nimic care să merite să vindeți bine, ordinea topologică este foarte simplă, avem doar aceste majuscule l diferite probleme și dacă vă uitați la oh uh da deci ne uităm la l minus p p este întotdeauna cel puțin unu, așa că întotdeauna scădem strict l în acest apel recursiv și atâta timp cât rezolv problemele în ordinea creșterii mici, voi garanta că oricând voi fi Rezolvând x din mica l Voi fi deja rezolvat toate lucrurile pe care trebuie să le apelez, așa că, dacă scrieți un dp de jos în sus, acesta ar fi doar bucla for l egală cu zero până la mare l în această ordine, aceasta este echivalentă cu afirmație, dar cheia este să verificăm că acesta este aciclic, deoarece ne referim întotdeauna la l mai mic și, prin urmare, creșterea l este o ordine topologică validă în această sub-problemă uh dag definită aici, unde există o margine de la un lucru anterior de evaluat la un Mai târziu, lucrul de evaluat, în regulă, cazul de bază ar fi x de zero, acesta este primul lucru pe care vom dori să-l calculăm aici și, într-adevăr, această formulă nu are prea mult sens dacă am x de 0 pentru că nu pot alege un număr p între 1 și 0. chiar și non-strict și deci ce înseamnă bine dacă am o lansetă de lungime 0, nu pot scoate bani din ea, așa că asta este, este un 0. asta este o presupunere, dar o presupunere rezonabilă pe care nu o faci Obțineți ceva pentru nimic, bine, atunci avem problema inițială, care este doar lungimea l tijei și apoi timpul de a calcula acest lucru câte subprobleme există capital l plus unu, așa că vom spune subprobleme theta l și vom înmulți cu uh cantitatea de timp pentru a evalua acest maxim, doar un număr constant de lucruri aici, fără a număra apelul recursiv, și așa a petrecut durează puțin l timp mic l este cu siguranță cel mult l mare și așa că vom spune mare o de mare l timpul este de fapt un număr triunghiular, dar va afecta lucrurile doar printr-un factor constant, așa că obținem l pătrat timp și am terminat atât de simplu, direct dp în acest moment, am văzut exemple mult mai complicate decât acesta, dar evidențiază o întrebare care este uh theta l pătrat timpul polinom, deci acesta este un timp de rulare rezonabil și susțin că răspunsul este da, acesta este un timp de rulare polinom rezonabil, ați putea spune bine, desigur, este un aspect polinom, acesta este un polinom l pătrat care este un polinom pătratic dar este un polinom pătratic în l și nu ne-am gândit prea mult la asta, dar ce înseamnă să fii timp polinomial um și aceasta este o noțiune care se numește în mod corespunzător timp puternic polinom, nu ne vom îngrijora prea mult în această privință. această clasă, dar dacă căutați asta online, veți vedea diferența timp polinom înseamnă că timpul de rulare este polinomial în dimensiunea intrării și dimensiunea intrării este pentru modelul nostru măsurată în cuvinte cuvinte mașină amintiți-vă cuvântul nostru vechi bun ram w biți cuvinte a fost foarte util, deoarece ne permite să presupunem lucruri precum adăugarea a două numere este un timp constant, atâta timp cât aceste numere se potrivesc într-un cuvânt, atâta timp cât sunt de cel mult w biți și, în general, presupunem toate lucrurile pe care le avem manipularea potrivirii într-un cuvânt de mașină, deoarece acesta este cazul în care lucrăm în mod normal și deci modalitatea naturală de a măsura dimensiunea unei intrări, așa că, în acest exemplu, această problemă, tija de tăiere a intrării este un singur număr l și această matrice de valori v de l care sunt numere majuscule l, așa că aș spune n numere întregi și am presupus, în general, că nu am menționat valoarea întregului aici, deoarece în această clasă presupunem că toate numerele întregi, dacă nu este specificat altfel, se potrivesc într-un cuvânt, așa că avem un cuvânt aici și l cuvinte aici, deci dimensiunea totală a intrării în această problemă este l plus un numere întregi în această problemă dimensiunea intrării este l plus unu, la care ne putem gândi doar l, ceea ce înseamnă că este bine, așa că nu am vrut în mod explicit să o fac folosiți n în această problemă, deoarece, de obicei, folosim litera n pentru dimensiunea problemei nu întotdeauna, dar dimensiunea de intrare înseamnă întotdeauna dimensiunea de intrare și, astfel, aici o putem calcula în termeni de specificație, care implică intrări l plus un cuvânt și, astfel, timpul polinomial ar trebui să fi polinom în acea dimensiune de intrare în l plus unu în exemplul nostru, deci, desigur, l pătratul este polinom și l plus unu atât de bun da bine, următorul exemplu pe care îl voi arăta va fi foarte asemănător, dar răspunsul va fi nu face este mai interesant, dar încă va părea destul de rezonabil, așa că vom reveni la acea problemă într-un moment, permiteți-mi să vă arăt mai întâi cum arată subproblema dp pentru această problemă, mi-a luat din nou ceva timp să desenez, așa că vă rog să admirați asta. este același exemplu al acestor valori 1 10 13 18 20 31 32 desenat aici pe un grafic este graficul complet orientat uh în acest mod crescător, cred că asta se numește un turneu în teoria grafurilor uh, așa că avem cazul de bază aici uh aceasta corespunde unei lansete de lungime zero în care nu primim bani și aici avem lanseta noastră completă de lungime șapte și susțin că tot ce putem face este 33 și ceea ce se întâmplă aici este pentru fiecare valoare ca trei pe care aș putea să-l vând. tija de lungime trei pentru 13 există o margine care merge de la fiecare vârf la 13 mai sus și toate au o greutate de 13 pe ele și apoi ceea ce încercăm în esență să facem este să găsim calea cea mai lungă de aici până aici, pentru că noi Dorim să maximizăm suma valorilor pe care le obținem și știm dacă anulăm toate greutățile, care este cea mai scurtă problemă a căii, astfel încât să putem rezolva asta cu cele mai scurte căi într- un dag, dar am desenat aici arborele cu cea mai scurtă cale din cazul de bază um așa că de fapt ne spune că, dacă am avea o lansetă cu lungimea șapte, cel mai bun lucru de făcut este să o vindem direct cu treizeci și unu, liniile îndrăznețe aici sunt arborele cu calea cea mai scurtă sau arborele cu calea cea mai lungă, cred și dacă am avea ceva în lungime. 10 ar trebui să-l vindem direct dacă avem ceva de lungime 20 ar trebui să vindem un lucru de lungime 2 și altul de stânga scuze un lucru de lungime 4 atunci ar trebui să vindem un lucru de lungime 10 din 2 și unul de lungime doi obținem de două ori zece puncte și pentru cazul 33 vindem un lucru cu lungimea doi un lucru cu lungimea doi și apoi unul cu lungimea trei este optim, astfel încât să puteți citi o mulțime de informații din aceasta și dacă notați codul dp acest lucru este eficient ce calculează de la stânga la dreapta, bine, să trecem la a doua problemă de astăzi, care este suma subsetelor, așa că aici ni se oferă, să spunem că un multi-set multiplu înseamnă că pot repeta numere, deci aceasta este doar o secvență de numere, dar aș Îmi place să folosesc notația set pentru că vreau să folosesc subseturi pentru că este o sumă de subseturi, deci aceasta este de n numere întregi și ni se dă, de asemenea, o sumă țintă și vrem să știm dacă vreo sumă de subseturi la suma țintă, aceasta este de fapt o problemă similară la tăierea tijei, deoarece tăierea tijei, a trebuit să împărțim numărul nostru l în diferite valori care însumau la l majuscul, deci capitalul joaca rolul capitalului l, dar înainte ni s-a permis să tăiem în orice lungime, așa că a fost ușor în în special, l însumează la l aici, probabil că t nu este în acest multiset și trebuie să găsim aici o combinație de numere care să adună exact cu t uneori, asta este posibil, uneori, nu, avem voie să folosim fiecare număr doar o dată sau de câte ori Apare în submult bine, așa că iată un exemplu să spunem a este egal cu doi cinci șapte opt nouă uh și două exemple sunt t egal cu 21 și t este egal cu 25 pentru același set, așa că pot obține 21 din acestea bine, asta implică aritmetică, ceea ce cred că este greu hai să vedem dacă adaug 7 și 8, obțin 15 nu este exact ceea ce vreau triș, uită-te la răspunsul meu uh da aproape, văd cinci șapte nouă uh, deci acesta este un răspuns da la întrebare există vreun subset pentru că uh 5 7 și 9 suma exact 21 și t este 25. Nu știu o modalitate bună de a vă demonstra că nu există nicio modalitate de a scrie 25 cu aceste numere, în afară de faptul că am scris un program care a încercat toate submulțile și sau ați putea scrie un program care rulează dp că suntem pe cale să-l dăm și va scoate nu, nu există o modalitate succintă, din câte știm, de a demonstra cuiva că răspunsul este nu pentru o anumită sumă țintă, există o modalitate succintă și drăguță de a demonstra că răspunsul este da, doar vă oferim un subset, vom vorbi mai multe despre următoarea prelegere, dar acestea sunt câteva exemple de întrebare pe care ați putea să o puneți și răspunsul pe care îl căutăm este ceea ce numim o problemă de decizie în forma sa originală, ne interesează doar într-un răspuns da sau nu, este un pic, desigur, în cazul da, am putea dori de fapt să găsim setul și putem face asta, ca de obicei, cu indicatorii părinte, la fel ca în liniile aldine de aici, vom ajunge la asta în un moment um, dar acesta este puțin diferit de cele mai multe probleme pe care le-am văzut cu programarea dinamică sunt probleme de optimizare și încercăm să minimizăm sau să maximizăm ceva și așa că întotdeauna punem un min sau un maxim în exterior. relația aici va trebui să facem ceva care implică valori booleene da sau nu, adevărat sau fals, bine, așa că haideți să o rezolvăm și asta va fi, de fapt, destul de simplu, în sensul că putem folosi seturile noastre standard de subprobleme, așa că doar ca și problema anterioară, avem pe de o parte o succesiune de numere întregi și, pe de altă parte, ni se dă un singur întreg t și ceea ce se dovedește a fi corect este să folosim prefixe sau sufixe pe această secvență și uh numere întregi mai mici decât sau egal cu t, hai să ne gândim de ce, așa că a fost sort bot pentru tăierea tijei, acesta este swordbot pentru suma subsetului din nou, voi căuta să văd ce caracteristică a soluției ar trebui să cred că am aceste n numere fiecare dintre ele ar putea fi în subsetul meu sau nu, așa că am această alegere binară pentru fiecare ai este în s sau nu, la multe întrebări la care trebuie să răspund, nu pot să le răspund la toate odată, dar aș putea începe cu prima și să spun bine este 0 și da sau nu există două răspunsuri la nivel local, forța brută, dacă fac asta, ce se întâmplă cu problema mea ce probleme secundare noi întâlnesc cu ce vreau să recurg bine, am eliminat un zero care va lăsa un sufix dintre sufixele ai, deci sufixele pe majuscule a par a fi o idee bună și ce zici de suma mea țintă depinde dacă pun un zero în setul meu s, atunci suma țintă pentru restul este t minus a0, așa că t a scăzut și deci am nevoie Am nevoie în subproblemele mele să reprezinte și sume țintă mai mici, așa că așa îți dai seama ce subprobleme ar trebui să folosești, nu, adică ai putea încerca doar prefixe pe aceste sufixe pe aceste subșiruri și da sau nu fac includeți versiuni mai mici ale lui t aici, dar vă puteți gândi, de asemenea, să încercați să scrieți o relație de recurență mai întâi să vedeți la ce lucruri recurgeți în mod natural și apoi să formulați subproblemele astfel, așa că asta îmi place să fac, așa că voi avea o problemă secundară pentru fiecare sufix uh, deci este x din i și pentru fiecare sumă țintă și folosesc aceste litere majuscule pentru suma țintă reală, astfel încât să pot folosi litere mici pentru versiuni mai mici ale acestora, așa că asta va fi uh Amintiți-vă orice subset nu trebuie să vă amintiți, cel mai important lucru este să definiți care sunt problemele dvs. secundare, nu spuneți doar că este aceeași problemă, dar acolo unde înlocuiesc bla, bla, foarte, poate fi foarte ambiguu și la fel face orice subset al sufixului a de la i încolo unele până la t mic și vom avea această problemă secundară, celălalt lucru important este să spunem câte probleme secundare există și pe ce indici pot varia, așa că i va fi între 0 și n și t va fi între 0 și mare, în regulă, deci numărul de subprobleme este de n plus unu ori t plus unu sau theta n ori t cool acum susțin că pot scrie o relație așa cum am spus, așa că avem acest sufix de la a de la i mai departe în a și deci mă duc doar pentru că mă uit la sufixe vreau să păstrez cu sufixe, așa că ar trebui să încerc să ghicesc ce se întâmplă cu a din i pentru că atunci ceea ce va rămâne este a din i plus 1 în continuare și a of i poate fi fie în submulțimea mea s, fie nu, deci există două opțiuni, așa că x din i t va implica două lucruri, așa că există un operator aici și apoi am un set de două elemente care este uh, aș putea alege să nu pun un de i din subsetul meu, în acest caz, am eliminat a din i și ceea ce rămâne este uh a de i plus 1 și nu mi-am schimbat suma țintă. Nu am pus nimic în s, așa că încă vreau să ating aceeași sumă, deci acesta este cazul în care un i nu este în s și apoi celălalt caz este că pun a din i în s în acel caz din nou am eliminat a din i și deci ceea ce rămâne de aflat este ce se întâmplă cu a din i plus 1 în continuare, dar acum suma mea țintă este diferită pentru că am pus un număr în setul meu și, astfel, printre aceste elemente ar trebui să însumeze nu mai puțin t, ci acum mic t minus ceea ce tocmai am adăugat, care este un i, atunci dacă în această problemă secundară primesc ceva care însumează t minus un i și apoi adaug un i la acel set, voi obține ceva care însumează exact t și deci este o soluție validă pentru această problemă și pentru că am forțat toate posibilitățile, au existat doar două uh, dacă le combinăm în mod adecvat, atunci vom fi luat în considerare toate opțiunile acum, ce vrem aici, așa că în mod normal, aș scrie max sau min, dar aceasta este o problemă de decizie, rezultatul este doar da sau nu, deci acesta este un răspunsul da sau nu, acesta este un răspuns da sau nu, acesta este un răspuns da sau nu și, deci, ceea ce vreau este sau în python, acesta s-ar numi orice, pur și simplu, oricare dintre aceste lucruri este adevărat, deoarece, dacă există vreo modalitate de a construi un set care însumează atunci răspunsul la acest lucru este da, foarte simplu, de fapt, aceasta este una dintre cele mai simple recurențe, dar rezolvăm ceea ce cred că este o problemă cu adevărat impresionantă, ne întrebăm dacă există vreun subset sunt exact două la cele n subseturi ale unui aici um și într-un fel le luăm în considerare pe toate două la n dintre ele, dar pentru că le-am împărțit în n opțiuni locale care sunt binare și le facem doar una câte una, un fel de asta este local forța brută versus forța brută globală forța brută globală ar fi subseturi de încercare, însumați-le vedeți care dintre ele se adună, dar într-un fel prăbușim multe dintre aceste opțiuni să fie în reutilizarea problemelor secundare, acesta este scopul programării dinamice la care ne uităm uh, pentru restul secvenței de la i plus unu încoace, nu-mi pasă exact ce subset pe care îl alegi, îmi pasă doar la ce însumează și asta combină o mulțime de opțiuni diferite în același lucru pe care chiar vreau să îl fac Știu că există vreo modalitate de a face acest lucru cu exact această sumă, așa că nu trebuie să cred că nu cred că nu trebuie să țin evidența dacă dacă aș spune să-mi dai toate submulțile diferite care însumează la t care ar fi timp exponențial, dar pentru că pun doar o întrebare da sau nu, această alegere necesită doar timp constant și ajungem să le însumăm în loc de produs, atunci pentru că folosim memorarea care este frumusețea programării dinamice și regula de analiză a timpului care trebuie doar să însumăm problemele secundare pentru că calculăm fiecare sub problemă o singură dată, așa că fără memorare, acest lucru ar dura un timp exponențial, la fel ca Fibonacci cu magia de memorare, cred că este frumos, deci, deși este unul dintre dps-ul nostru mai simplu, cred că este impresionant. o ordine topologică bine, hai să ne uităm la aceste apeluri de funcții, așa că aici trebuie să fim puțin atenți când apelăm x recursiv, întotdeauna creștem i, dar uneori nu decrementăm t uneori t nu scade, așa că dacă am scris scăderea t aici ar fi rău pentru că uneori sun cu aceeași valoare a lui t și nu vreau să intru, vreau să mă asigur că aceasta a fost deja calculată atunci când încerc să calculez asta, așa că sunt lucrul potrivit și noi ar trebui să spun că descrește i nu contează de fapt modul în care comandăm în ceea ce privește orice ordine care este în scădere, voi fi bine pentru că aceste apeluri de funcție cresc întotdeauna, bine, avem nevoie de un caz de bază, cazuri de bază, să vedem ce este firesc având în vedere acest aspect. cred că lucrul natural este să ai un caz de bază atunci când sufixul meu este gol, adică atunci când i este egal cu n, deci acesta este x din uh n virgulă pentru orice t mic, deoarece nu avem prea mult control asupra modului în care t se schimbă, dar acest lucru este ușor, așa că asta înseamnă că dacă nu vă dau numere ce sume puteți reprezenta singura sumă pe care o pot reprezenta este 0. Bine, dacă t este egal cu 0, atunci răspunsul este da și în caz contrar răspunsul este nu, așa că acesta este cazul meu de bază și este suficient și aveam nevoie de acest caz de bază pentru că dacă am scrie x din n virgulă t, aceasta ar încerca să se numească x din n plus 1, care nu are sens, dar x din n apelează ca sufix natural pe care i-am permis doar să merg până la n și acesta este sufixul gol, așa că este suficient, avem nevoie de problema inițială uh, care este întregul șir de la zero încolo și t capitală pentru t mic, aceasta este suma noastră țintă și apoi timpul de rulare după cum am spus, există de n ori t sub probleme theta și cantitatea de muncă pe care o cheltuim pentru fiecare care nu este recursivitate este constantă, facem doar câteva scăderi adunări facem un sau și apeluri recursive, deci timp constant, deci de n ori t este timpul de rulare al acestui algoritm, permiteți-mi să vă arăt un exemplu ca etichetă de subproblemă foarte utilă pentru a vedea cât de greu de desenat acestea, dar sunt ușor de citit, cred că sunt utile pentru a arăta ce se întâmplă cu adevărat în acest dp. Amintiți-vă că fiecare nod de aici corespunde unei posibile subprobleme pe care am putea-o avea avem, deci avem opțiuni pentru t mic în partea de sus opțiuni pentru i mic în stânga, deci problema inițială care ne interesează este i este egal cu 0 t este egal cu 6. Acesta este același exemplu pe care ți l-am arătat înainte, unde avem trei sau nu, este un exemplu diferit Îmi pare rău, noul meu set a este trei patru trei unul patru numere aici valoarea țintă este șase, este cu siguranță posibil, pot adăuga trei și trei, asta arată că a nu trebuie sortat, nu presupunem nimic despre ordinea lui a și ni se permit valori duplicate și vedem într-adevăr că există un y aici pentru că da, este posibil și cum am calculat bine, tocmai am desenat o grămadă de săgeți, așa că aici există săgeți verticale care merg mereu de la fiecare problemă la următorul deasupra, deoarece avem această dependență x i din t apelurile x din i plus 1 virgulă t, așa că apelurile merg în această direcție, așa că ordinea dependenței este că trebuie să calculați lucrurile mai jos înainte de a calcula lucrurile aici sus și într-adevăr aici este cazul de bază în care scriem da pentru prima problemă și nu pentru toate celelalte, deoarece nu avem numere, nu putem reprezenta nimic peste zero, bine și apoi avem aceste linii albastre, le-am desenat altfel. culoare, astfel încât să iasă în evidență sperăm și să corespundă numerelor de aici, așa că prima noastră alegere este să includem un zero care este trei, astfel încât acest lucru este posibil numai dacă încercăm să reprezentăm un număr uh care este mai mare sau egal cu trei care îmi amintește Am uitat să notez în acest dp. Trebuie să spun că această opțiune este doar o opțiune dacă un i este mai mic sau egal cu t, doar mutați comentariile mele aici, acestea sunt aceleași, așa că această notație înseamnă că am pus acest element în acest set pe care îl luăm an sau of numai dacă această condiție este în regulă, altfel o recunosc pentru că nu este o alegere de ce este atât de important pentru că nu vreau să sun pe x la o valoare negativă a t, avem voie să-l numim pe x aici doar când t este între zero și t majuscul, deci este subtilitate, dar important pentru un dp corect, de aceea nu există nicio margine de aici, de exemplu, care merge trei spre stânga, pentru că nu există vârfuri acolo, nu există nicio problemă secundară, așa că doar pentru uh mic t de la trei încolo avem asta marginea care merge cu trei înapoi și este doar același model iar și iar, apoi următorul nostru număr este patru și astfel avem aceste margini care merg patru la dreapta, apoi următorul nostru număr este trei, așa că avem din nou margini care merg trei la dreapta și apoi următorul nostru număr este unul, așa că avem aceste margini diagonale frumoase care merg una spre dreapta și apoi ceea ce se întâmplă aici la fiecare etapă, să luăm unul interesant, poate că acest vârf este să ne uităm la fiecare dintre vecinii care intră și luăm sau așa vecinul care vine aici are un vecin care vine aici are un da și așa că scriem un da aici, ceea ce înseamnă că, având în vedere doar aceste numere trei și unu, putem reprezenta numărul trei și anume luând această margine a greutății trei scuze de lungimea trei și apoi mergând direct la un caz de bază care este da, care reprezintă 0. deci, în acest caz, în acest exemplu, nu am desenat pointerii părinte aici, dar sunt în note, acest da este posibil nu din mers în acest fel, ci de la mergând în acest fel, așa că luăm numărul trei, apoi coborâm, ceea ce înseamnă sărim peste numărul patru și apoi mergem la stânga, ceea ce înseamnă că luăm numărul trei și apoi coborâm, ceea ce înseamnă că sărim numărul unu, bine, astfel încât să putem reprezenta șase ca trei plus trei este grozav, deci suma subsetului nu numai că putem rezolva problema deciziei, dar urmând indicatorii părinte în cazurile da, putem găsi de fapt o întrebare de subset validă, ați adăugat acea condiție la relația întrebare bună, așa că este o întrebare generală. tehnică utilă pentru a adăuga dacă condițiile la cazuri doar atunci când se aplică, puteți scrie o mulțime de dps astfel și de aceea am vrut să subliniez, ați putea în loc să adăugați această condiție să permiteți cazul că puțin t este negativ, dar trebuie să Gândește-te cât de negativ ar fi ai putea spune că poate t între minus t mare și plus t mare este suficient. cum este ai în comparație cu t mare, probabil că sunt mai mici sau egale cu t mare, deoarece nu sunt utile dacă sunt mai mari decât t mare, așa că ai putea mai întâi tăia ais pentru a garanta că toate ais sunt mai mici decât t mare atunci minus t mare la t mare ar funcționa, altfel este ca minus maximul ai până la t mare ar fi suficient. Cred că da, acest lucru se limitează doar la numerele întregi pozitive din intrare, ah, presupun implicit aici că toate ai sunt pozitive uh Cred că o poți rezolva cu numere negative, dar nu este uh și poate o vom face în recitare, nu este, deoarece nu este o schimbare banală la acest dp, cu siguranță m-am gândit la asta înainte, da, așa că ar fi trebuit să spun numere întregi pozitive mulțumesc bine, așa că asta este suma subsetului, dar ne întoarcem la această întrebare dacă acesta este un algoritm bun este timpul polinomial, așa că avem acest timp de rulare de n ori t, deci o nouă întrebare este polinomul t de n ori mare și răspunsul nu este motivul pentru că, pentru această problemă, care este dimensiunea de intrare, câte cuvinte de intrare am bine, am aceste n numere întregi și apoi am, de asemenea, suma țintă atât de asemănătoare cu cea de deasupra dimensiunii noastre de intrare este n plus unu bine, dar acum etichetele contează cu adevărat înainte de a fi l plus unu și și timpul nostru de rulare era o funcție de l acum dimensiunea noastră de intrare este doar n plus unu, dar timpul nostru de rulare este o funcție a ambelor n și t nu polinom în dimensiunea de intrare n plus unu, nu puteți scrieți că de n n ori capitalul t este mai mic sau egal cu n plus 1 la a 27-a putere pentru că pur și simplu nu știți cum se leagă n și t, poate t este cel mult n, atunci suntem fericiți, dar poate că nu este poate t este 2 la n de ce ar putea fi 2 la n uh pentru că ce știm despre t majusculă presupunem implicit pe tot parcursul cursului că t se potrivește într-un cuvânt care înseamnă că este un număr de biți w, deci înseamnă că este cel mult două la w și tu s-ar putea gândi bine că știm despre o relație între w și n, așa că știm că t este cel mult 2 la w dacă este w biți și știm că presupunerea noastră este întotdeauna că w este cel puțin log n, acesta este cuvântul ram presupunere transdihotomică dar observați că nu știm nimic despre o limită superioară pe w pentru a limita superioară t în termeni de n, ar trebui să spun că w este cel mult log n, atunci acesta ar fi cel mult n și am terminat dar asta nu este foarte interesant și, în general, permitem ca w să fie arbitrar mare în ceea ce privește log n, trebuie să fie cel puțin log n doar pentru a putea indexa lucruri, deci, dar w ar putea fi cu adevărat mare mult mai mare decât log n, de exemplu w egal cu n nu este o idee nebunească, vreau să spun, dacă am o mașină care poate reprezenta n numere, de ce să nu reprezinți n numere, fiecare dintre ele având lungime de n biți și poate că este nevoie de puțin mai mult timp pentru a le calcula pe acelea pe care ați dori să le scalați. timpi de rulare, dar este destul de rezonabil să ne gândim la numere de n biți și atunci acesta este ca de n ori 2 la n, deci acesta ar fi de fapt timp exponențial și dacă w este 2 la n n ori t este exponențial în dimensiunea problemei care este n plus 1. și acesta este doar un exemplu w ar putea fi mai mare, bine, deci nu este ceea ce numim un algoritm polinom sau un algoritm puternic polinomial, dar este încă destul de bun atâta timp cât știm că t majusculul nu este mare, atunci acesta este un algoritm grozav deci este și surprindem acea noțiune cu un concept numit pseudo-polinom, nu este cel mai bun termen, dar este termenul stabilit, este ca un polinom, dar nu chiar și definiția acestui termen, așa că avem definiția timpului puternic polinom uh acum uh pseudo- timp polinom, voi scrie timpul aici, astfel încât să puteți măsura alte lucruri pseudopolinom uh este că suntem polinom uh în dimensiunea de intrare la fel ca înainte și numerele de intrare introduc numere întregi bine, așa că în această problemă numerele întregi de intrare sunt t majuscule și a0 a1 până la un n minus 1. deci vrem acum este un polinom sau ceea ce unii oameni numesc un multinom în care variabilele noastre sunt toate aceste numere întregi și vrem să fim polinom în ele, așa că avem voie să luăm o putere constantă a capitalului t și un număr constant al ais, nu putem doar să luăm produsul tuturor care ar fi mare, așa că ar trebui să spun un polinom de grad constant și, într-adevăr, acesta este un polinom pătratic în dimensiunea de intrare și și unul dintre numere, deci acesta este timpul de rulare este pseudo- poli, dar nu poli și așa că, în timp ce în mod normal ne gândim la timpul polinom este bun, timpul exponențial este rău pseudo-polinom este ceea ce în mod normal numim destul de bun pentru a fi informal, da, deci în special pseudopolinom implică polinom în cazul special, deci dacă numerele întregi de intrare sunt toate cel mult polinomale în dimensiunea de intrare, acest lucru ar trebui să sune familiar, aceasta este o constrângere pe care am văzut-o înainte, aceasta este condiția când sortarea radix rulează în timp liniar sortarea gata rulează în liniar momentul exact în care toate numerele întregi de intrare sunt mărginite polinomial în n, care este dimensiunea matricei, care este dimensiunea de intrare, bine, așa că aceeași condiție apare din nou, așa că aceasta este un fel de setare fundamentală la care să ne gândim și să vedem, în special, alte structurile pe care le-am văzut, cum ar fi sortarea de numărare și matricele de acces direct sunt, de asemenea, pseudopolinom orice altele Fibonacci scuze rata exportului da tehnic, de asemenea, rata de sortare sunt toate uh, nu sunt puternic polinomiale, dar sunt pseudo-polinom uh aici ne-am gândit la asta ca un dependența de tine de care am scăpat de folosirea hashingului, dar dacă folosești doar ordinea u timpul de rulare pentru a spune build uh că u este ca și cum ar fi legat de numerele întregi de intrare și asta este bine numai când acesta este polinom în general, este pseudo-polinom la fel cu sortarea de numărare am avut o comandă u acum am îmbunătățit acest lucru în sortarea radix la acest timp de rulare care a fost uh de n ori baza de log n de u plus n dacă doriți să fiți atenți, um, sau puneți un plafon uh acum acesta este un timp de rulare este puțin mai bine și de obicei se numește polinom săptămânal. Nu vreau să petrec mult timp cu asta, dar polinomul săptămânal este la fel ca pseudo-polinomul, dar în loc să fie polinom, dimensiunea de intrare și intrarea numere întregi polinomul dvs. în jurnalul numere întregi, deci este mai bine și este aproape la fel de bun ca polinom ca și puternic polinom, bine, nu vom folosi cu adevărat această noțiune, singurul loc care apare în această clasă este în sortarea de evaluare, dar clasele viitoare de care s-ar putea să vă pese, astfel încât imbricarea este cea mai bună ceea ce poți fi este puternic polinom, numim acest polinom în această clasă, uh, atunci avem polinom săptămânal, care este aproape la fel de bun, dar ai această dependență logaritmică de numere și apoi următorul nivel este pseudopolinom, nu este la fel de bun aici. funcționează bine doar dacă numerele sunt mici. dependența logaritmică este destul de bună, deoarece, chiar dacă sunt exponențiale, acesta este un polinom sună amuzant, dar logul unui exponențial este suficient de polinom despre pseudopoli Ultimul lucru despre care vreau să vorbesc este să reflectez asupra tuturor programele dinamice pe care le-am văzut până acum și caracterizarea lor în funcție de tehnicile mari pe care le-am folosit în botul de sortare prima tehnică mare a fost cum ne definim subproblemele am luat prefixe și sufixe sau subșiruri ale unei secvențe am avut secvențe multiple și trebuie să luăm produse ale acelor spații, am avut numere întregi și trebuie să luăm versiuni mai mici ale acelor numere întregi, uneori, ceea ce duce la algoritmi pseudo-polinomi, uneori nu și uneori am avut și subprobleme care au fost definite în termeni de vârfuri, asta tocmai sa întâmplat în probleme cu calea cea mai scurtă, deoarece aceasta este singura setare în care am văzut dp peste grafice, așa că permiteți-mi să caracterizez toate dps-urile pe care le-am văzut în prelegere nu pe cele recitate deocamdată în roșu, deci, de exemplu, cu problema de bowling cu ace de bowling, a trebuit doar să să ne ocupăm de prefixe sau sufixe pentru că da, eram doar că ne puteam gândi la ce s-a întâmplat pentru primii doi pini, de exemplu, și pentru lcs, a trebuit să luăm două secvențe diferite, dar apoi am ghicit ce sa întâmplat la interior cu primele două elemente. din fiecare uh din fiecare secvență și astfel încât ne-au lăsat doar sufixe uh cu cea mai lungă subsecvență crescătoare am ghicit din nou dacă primul articol sau poate am presupus că primul articol se află în cea mai lungă subsecvență crescătoare și apoi am încercat să ghicim care este următorul element a fost, dar a eliminat din nou tot ce se afla între ele, așa că am rămas doar cu un sufix, ceea ce mă duce la o altă caracterizare a tipului de tehnici de programare dinamică, pentru că, pe lângă aceste sub-probleme de bază, am adăugat adesea constrângeri și extindere și este un exemplu de ceea ce numim constrângere non-expansivă în care tocmai am adăugat o constrângere la problemă, care a fost că aș dori ca acest prim articol să fie în cea mai lungă secvență crescătoare, dar asta nu a schimbat de fapt numărul de sub-probleme, așa că nu a făcut-o. Nu extindeți numărul de subprobleme, acesta este, cred că singurul exemplu pe care l-am văzut cu această caracteristică de cele mai multe ori, când am adăugat o constrângere, am crescut și numărul de subprobleme pe care le vom rezolva și într-un anumit sens Există mai multe moduri de a ne gândi la acest lucru, floyd warshall este o problemă sau definim subprobleme pe baza prefixelor nodurilor chiar dacă am avut vârfuri de la 1 la n am spus că este calea lor cea mai scurtă folosind vârfurile doar de la 1 la i, deci acesta este un prefix al setului de vârfuri într-o anumită ordine, astfel încât să vă puteți gândi la Floyd Warshall ca fiind ca implicând un prefix, vă puteți gândi și la el deoarece vi se dă un număr întreg i și aveți voie să utilizați numai vârfuri mai mici sau egale cu i și deci este, de asemenea, un fel de problemă sub numere întregi, dar o voi lăsa acolo și cele două exemple pe care le-am văzut astăzi de tăiere a tijei într- un fel, uh, ați putea să vă gândiți fie la un prefix al valorilor, fie aș prefera să mă gândesc la asta aici, acolo unde am avut un întreg și ne-am gândit și la numere întregi mai mici, dar suma subsetului a avut cu siguranță un sufix în plus față de o subproblemă întreg, așa că tăierea tijei o puteți pune aici, deoarece ne-am uitat la numere întregi mai mici sau aici sus, dar suma subsetului este într-adevăr aici și în jos aici, pentru că amândoi ne-am uitat la sufixe și la valori mai mici ale lui t bine uh, Fibonacci se potrivește și aici. subșiruri am văzut două dintre ele, unul era jocul de monede alternante pentru că luam din stânga sau din dreapta și așa că a trebuit să ne uităm la subșiruri între ele, iar celălalt este parantezele în care trebuia să ghicim ceva la mijloc și care a lăsat prefixul înainte. el și sufixul după ambele sunt moduri tipice în care întâmpinați probleme cu subșiruri, bine, deci pseudo-poli ambele sunt pseudo-poli și acelea sunt cele pe care le-am văzut că sunt programe dinamice pseudopoli și apoi cu vârfuri sunt tot cea mai scurtă cale uh probleme în care am avut și un parametru care a fost un vârf, acestea sunt naturale, deoarece în scopul unui fel de căi unice cele mai scurte cele mai scurte este distanța până la fiecare vârf și, deci, în mod natural, am avut o problemă secundară pentru fiecare vârf pentru dag cele mai scurte căi pentru bellman ford și pentru floyd warshall bine înapoi la expansiunea subproblemei am văzut câteva exemple care alternau jocul cu monede și parantezele, scuze, nu parantezele, uh da, parantezele scuze parantezele aritmetice, așa că aici luăm în considerare două versiuni diferite ale fiecărei subprobleme, una unde merg eu primul și una unde mergi tu mai întâi și asta a fost foarte util, deși nu era necesar pentru paranteză, s-a dovedit că avem nevoie de atât min, cât și max pentru a rezolva max, așa că ne-a păsat doar de max, așa că am dublat numărul de subprobleme pentru a le face rezolvabile pentru pian și chitară. creștem numărul de subprobleme cu o constantă sau f sau ceva f la f sau ceva uh pentru cinci degete aceasta este o constantă rezonabilă um pentru o anumită cantitate de stare pe care am vrut să ținem evidența trecutului și un exemplu în care am a avut o expansiune liniară un fel de bellman ford, așa că aici am extins cu câte muchii sunt pe calea cea mai scurtă, așa că ne-a păsat doar să găsim cele mai scurte căi am spus oh, ce zici de cel mult marginile ochilor, așa că te poți gândi la asta ca la adăugarea unei constrângeri și apoi există n variații diferite ale acestor subprobleme care duc la extindere, ceea ce ați putea crede, de asemenea, ca fiind doar adăugarea unei singure constrângeri, care este că îmi pasă de numărul de margini și acea intrare este un întreg și apoi ne uităm la subproblema naturală pentru numerele întregi, care ne pasă până la lungimea n minus 1 și acum să luăm în considerare toate lungimile mai mici decât n minus 1. bine și, în sfârșit, cealaltă caracteristică principală pe care o aveam este relația de recurență și toate aceste etichete de calea cea mai scurtă câte marginile de intrare am avut câte ramuri diferite a trebuit să luăm în considerare și apoi să combinăm într-un fel, așa că am văzut o mulțime de exemple cu Fibonacci cu ramificare constantă în care doar eram bowling-ul evident cu ramificare în două sensuri în care aveam câteva opțiuni la început lcs cea mai lungă secvență comună în care am avut câteva opțiuni ce să facem la începutul jocului alternativ de monede, în mod similar, luăm din stânga sau din dreapta, așa că doar două opțiuni Floyd Warshall există două opțiuni dacă folosim acel vârf sau nu sumă submulțială includem acest articol în submult sau nu este în regulă, așa că a fost o ramificare constantă în multe dintre problemele de grafic, am primit ramificarea de grad ordonată, ceea ce duce la un termen de ordine în timpul final de rulare și anume dag cele mai scurte căi și bellman ford și apoi o mulțime de exemple au avut ramificare liniară, în special cea mai lungă secvență de creștere în care nu știam care este următorul element în creștere, așa că există n opțiuni posibile pentru paranteză în care a trebuit să alegem pe oricine din mijloc ca ultimul operator și tăierea tijei am văzut astăzi, am putea tăia prima lansetă pe care am tăiat-o ar putea avea orice lungime și apoi, în cele din urmă, odată ce ați considerat că toate aceste probleme secundare sunt recurente, trebuie să le combinați cumva și în multe dintre probleme, de fapt, luăm doar una cea mai bună alegere și aceasta este soluția noastră finală și în acele probleme, soluția finală ajunge să fie găsirea unui fel de cale cea mai scurtă într-un dag, dar există câteva cazuri în care de fapt am luat mai multe soluții și le-am combinat împreună pentru a obține soluția generală și aceasta include Fibonacci, care este că le-am adăugat nu prea interesante Floyd Warsam concatenat două căi și parantezele este poate cea mai interesantă, unde a trebuit să luăm două părți prefixul și sufixul cum să le rezolvăm și apoi să le înmulțim sau să le adunăm împreună și astfel acestea problemele nu sunt bine reprezentate de calea cea mai scurtă și un dag este încă un dag implicat, dar este ca o chestie cu mai multe căi și apoi, în sfârșit, la problema inițială, adesea este doar o singură sub-problemă este problema inițială și există câteva exemple și anume dag cele mai scurte căi și cea mai lungă secvență crescătoare și bellman ford și floyd warshall acestea au fost ordinea în care le-am parcurs, deci cele trei căi cele mai scurte și apoi cea mai lungă succesiune crescătoare unde uh aici, deoarece am adăugat această condiție, a trebuit să încercăm toate alegerile posibile pentru această condiție Cred că avem și astăzi unul aici, nu bine, așa că, în retrospectivă sau vreau să spun asta, știam asta de la început, dar pentru tine, în retrospectivă, aceste patru prelegeri dp au fost toate despre a- ți arăta aceste tehnici principale de programare dinamică din modul în care pentru a configura subprobleme simple la diferite tipuri de subprobleme de bază pentru a limita sau extinde acele subprobleme și având inițial o ramificare foarte simplă și apoi să ajungem la o ramificare mai mare și diferite tipuri de combinații, am vrut să vă arătăm toate aceste idei într-o anumită ordine și dacă te uiți înapoi la secvența în care am acoperit problemele, adăugăm încet aceste tehnici principale diferite la dp și de aceea am ales exemplele pe care le-am făcut acolo, desigur, multe alte exemple de tehnică dp foarte puternică, dar acesta este sfârșitul