[SCRÂȘIT] [FOSȘIT] [DĂ CLIC] JASON KU: Hei, tuturor. Bine ai revenit. Aceasta este ultima noastră revizuire a testului pentru trimestrul, testul 3, despre care vom vorbi , care va fi ultimul test până la finală. Este vorba despre programarea dinamică, pe care voi ați studiat-o în prelegeri și recitări și pe seturile voastre de probleme 7 și 8 și cursurile de la 15 la 18, deci patru prelegeri. Materialul testului 1 și testului 2, în esență, cu privire la structurile de date și algoritmii grafici, nu vor fi testați în mod explicit sau nu încercăm să îl testăm în mod explicit, acel material, la testul 3. Dar este un joc corect. Materialul este cumulat. Și deci, dacă trebuie să stocați unele lucruri în structura de date, este un joc corect. Dar nu încercăm în mod special să vă testăm pe acel material. Bine, și într-adevăr, nu am învățat atât de mult material nou în ultimele patru prelegeri din această unitate. Deci acesta este domeniul de aplicare. Avem, în mare parte ne ocupăm de programare dinamică pentru aceste patru prelegeri și recitări și aceste două seturi de probleme. Dar, într-adevăr, accentul se va pune pe acest cadru recursiv de rezolvare a problemelor, cu accent pe programarea dinamică, în special. Acum, cadrul recursiv pe care îl avem, cred, în slide-urile anterioare, am folosit această notație SRTBOT. Și cred că ar putea exista un spațiu acolo în versiunile anterioare. Le concatenez aici. Dar într-adevăr, este un cadru pentru rezolvarea defalcării problemei dvs. într-un set de subprobleme care pot fi apoi legate recursiv. Și dacă acea relație depinde de probleme într-un sens descrescător sau mai mic, există o direcționalitate la care subprobleme mă reduc de fiecare dată când fac un apel recursiv. Și acel grafic de dependență este ciclic. Apoi putem rezolva prin programare dinamică prin memorare de jos în sus sau apelând lucruri și amintindu-ne apelurile pe care le-am apelat înainte prin memorare. Și ideea de bază aici este aceasta cadru recursiv SRT BOT pe care l-am stabilit este bun pentru orice algoritm recursiv. Dar în cazul special în care subproblemele pot fi folosite de mai multe ori, pot fi folosite atunci când se calculează alte subprobleme, atunci obținem această viteză foarte bună recunoscând că nu trebuie să facem această muncă de mai multe ori. Și, în esență, în loc să-l privim ca pe un arbore de apeluri recursive care pot apela aceleași probleme de mai multe ori, îl privim prin prăbușirea acelor noduri de aceeași valoare într-unul singur. Primim un DAG. Și programarea dinamică este atunci când acele subprobleme se suprapun. OK, deci haideți să aruncăm o privire la cadrul nostru recursiv aici, SRT BOT. Avem S-R-T B-O-T. Mi-am amintit de această dată spațiul. Subproblemă, vei defini câteva subprobleme. Le vei relata recursiv. Veți specifica o ordine topologică a acelor subprobleme pe care le îndeplinește relația. Veți enumera câteva cazuri de bază, practic oriunde ați putea rezolva această problemă în timp constant, fără a face nicio muncă recursivă. A afirma modul în care rezolvați problema inițială, care ar putea implica combinarea mai multor subprobleme, dar în mod frecvent, este doar găsirea unei subprobleme și, eventual, amintirea-- stocarea indicatorilor părinte pentru a returna o secvență optimă, sau ceva de genul acesta. Și apoi, analizează timpul. Acum, ultimul nu este cu adevărat important pentru rezolvarea unei probleme în mod recursiv. Dar în această clasă, este foarte important, pentru că vrem să spunem dacă algoritmii pe care îi facem sunt eficienți. Deci haideți să ne aprofundăm puțin în fiecare dintre aceste lucruri. Deci, atunci când abordăm o subproblemă, într-adevăr, ceea ce vă cer este să descrieți -- practic, să stabiliți un set de probleme. Practic, îmi place să folosesc variabila x. Dar puteți folosi orice variabilă doriți. Dar, practic, ne spui ce este în nota ta și cât de mare este nota ta. Deci avem de obicei x ca o funcție a unor variabile. Și vrei să-mi descrii care este sensul acelei subprobleme în ceea ce privește parametrii. Acum, dacă aveți parametri în subproblemă care nu apar în definiția subproblemei, o faceți greșit. Și probabil că nu vei primi puncte pentru problemă. Pentru că acum nu știu ce înseamnă problema ta. Chiar dacă este o problemă corectă, iar restul o faci corect, o parte a acestui curs este despre comunicare. Și dacă nu ne comunicați ce face acest lucru, este foarte dificil pentru noi -- să ne convingeți că algoritmul dvs. este corect. Deci chiar vrei să descrii, în cuvinte, care este rezultatul subproblemei tale. Ce îmi va întoarce nota? Și modul în care aceste valori returnate depind de intrări, de parametrii subproblemei tale. Deci, asta este ceea ce, în cuvinte, descrie ce înseamnă o subproblemă. Deci, acesta va fi un lucru foarte important pentru tine să nu uiți la un test. Apoi, atunci când facem subprobleme, de multe ori, ceea ce facem este să repetăm ​​diferite valori ale indicilor dintr-o secvență sau numere din problema ta. Cam la asta am ajuns în ultima -- în prelegerea 18, cred, când vorbeam despre extinderea subproblemelor bazate pe un număr întreg dintr-o problemă. Acum, de fapt, un număr întreg din problema noastră este numărul de lucruri dintr-o secvență. Și deci, într-adevăr, acești indici sunt numere întregi în problema noastră pe care le trecem în buclă. Cu excepția faptului că acele numere întregi se întâmplă să fie de dimensiunea subproblemei noastre. În timp ce, alte numere întregi ar putea fi mai mari, motiv pentru care ați putea obține o legătură temporală pseudopolinom. Dar, în general, atunci când am o secvență de lucruri pe care aș dori să le programez dinamic, alegerile comune pentru subprobleme sunt prefixele sau sufixele dacă pot să-mi dau seama la nivel local să fac cu unul ce să fac cu un articol și apoi să recurg. Sau dacă nu o pot localiza printr-o singură alegere pe o parte, dacă trebuie să fac o alegere la mijloc sau trebuie să fac o alegere la ambele capete, atunci s-ar putea să doriți să utilizați sub-- practic contiguu subsecvențe ale secvenței dvs. Pentru că s-ar putea să ai nevoie de această flexibilitate atunci când mergi înapoi în jos, dacă trebuie să iei ceva atât din față, cât și din spate, de exemplu. Și într-adevăr, care este diferența dintre prefixe și sufixe? Nu prea mult. OK, ne-am concentrat asupra sufixelor din această clasă. Pentru că, într-un anumit sens, este mai ușor să te gândești. Ce fac cu primul lucru din secvența mea sau cu sufixul meu? Și apoi pot recurge la ceea ce se întâmplă mai târziu. Acum, în realitate, când faci asta, să zicem, de jos în sus, calculul real care este evaluat primul este unde în acea secvență? S-ar putea să spun, la nivel superior, ce se întâmplă cu primul meu element. Dar de fapt mă voi ocupa de primul element ultima. Pentru că voi rezolva recursiv totul sub mine, în fața mea, înainte de a-mi da seama ce să fac cu chestia asta. Deci, de fapt, când îmi rezolv recursiunea, voi începe de la sfârșit, de jos în sus, pentru că acesta este cazul meu de bază. Și apoi mă voi întoarce înapoi în față. În timp ce, cu prefixe, te uiți la asta în alt mod. Ce fac cu ultimul meu element? Dacă mă uit la ceea ce fac la ultimul element, recurg la un prefix, la lucrurile care sunt înaintea mea. Și apoi, când fac de jos în sus, încep din față și merg în sus. sunt două fețe diferite ale aceleiași monede. Și, de obicei, acestea sunt interschimbabile. Am făcut-o din punct de vedere al sufixelor, pentru că atunci când începem să învățăm programarea dinamică, este mult-- citim lucruri de la stânga la dreapta și lucruri de genul acesta. Este mult mai ușor să-ți dai seama ce se întâmplă cu primul lucru și să mergi mai departe, conceptual. Este de fapt exact același lucru. Mi- aș putea întoarce secvența, să fac exact același lucru cu prefixele. Ar fi exact același program dinamic. Deci aceste lucruri sunt interschimbabile. Este foarte util, atunci când învățați să programați dinamic, să puteți comuta între aceste lucruri. Vom lucra la sufixe astăzi la problemele pe care le facem. Dar acestea sunt interschimbabile. Și uneori este util să poți gândi conceptual la asta în ambele direcții. Deci, pe lângă faptul că ne ocupăm de subsecvențele de secvențe, în special de cele învecinate, adesea ne înmulțim subseturile pe mai multe intrări. Ca dacă avem mai multe secvențe, am putea lua indici în fiecare dintre ele pentru a reprezenta prefixe sau sufixe. Și atunci ar putea fi necesar să ne amintim informații suplimentare prin menținerea unor informații auxiliare, cum ar fi încerc să maximizez sau să minimizez suma mea în a-- sau o expresie evaluată într- o paranteză aritmetică. Sau este rândul jucătorului 1 sau al 2-lea? Sau care deget... unde era degetul meu când cântam la pian sau ceva de genul ăsta? Acestea sunt genul de lucruri pe care ne-am putea extinde starea. Și în special, ne- am putea extinde starea pe baza numerelor din problema noastră dacă încercăm, de exemplu, să ținem evidența cât spațiu rămâne într-un rucsac sau ceva de genul acesta. Dar, în general, dacă încerc, să zicem, să împachetez un set de lucruri, este util să știu cât spațiu îmi rămâne să împachetez. Deci sunt subprobleme. Aceasta este într-adevăr partea cheie despre programarea dinamică este partea recursivă. Acesta este ceea ce face dificilă alegerea unui set de subprobleme. Și de multe ori construiești subprobleme care să se potrivească bine cu relațiile. Deci, de obicei, construirea care sunt aceste subprobleme este de obicei strâns cuplată cu următorul pas, care este relaționarea recursiv a subproblemelor. Și relaționați recursiv, eu-- de obicei ceea ce vreau este o expresie, o expresie matematică, relaționând definiția unei subprobleme pe care ai avut-o în secțiunea anterioară, relaționându-le, în termeni matematici, cu celelalte lucruri. Acesta este... este foarte important să scrii asta la matematică, pentru că trebuie să fie precis, să comunici bine acest lucru. Acum, o poți scrie în cuvinte. Dar ți-aș sugera să o scrii ca o expresie matematică, pentru că este mult mai concis pentru noi să vedem ce se întâmplă în recursiunea ta. Așa că relaționați-le recursiv. Practic, voi scrie, să zicem, că x al unui set de parametri este egal cu o anumită funcție, de obicei o maximizare, sau o minimizare, sau o însumare, sau și sau, sau un și, sau un alt combinator al unui grup de alegeri pe care le-ați putea face, deci... sau o grămadă de subprobleme la care ați putea recurge. Practic, vei depinde de alte subprobleme care sunt mai mici într-un anumit sens. Acum, de fapt încorporată în asta, ideea unei subprobleme mai mici nu este încă bine definită. Nu v-am spus că o ordonare a acestor subprobleme să fie mai mică. Dar asta va urma în a treia etapă. Deci, un fel de strategie pentru a afla care ar putea fi aceste relații recursive este de a identifica o întrebare despre soluția subproblemei. Ce fac cu primul caracter din acest șir? Sau in ce cusca pun acest tigru? Pentru a-mi da seama ce subproblemă ar trebui să recurg mai târziu? Nu știu răspunsul la acea întrebare. Dar dacă aș ști răspunsul la acea întrebare, atunci aș putea recurge la o subproblemă mai mică, pentru că mi-am dat seama ce să fac cu acel tigru. Și așa mă va permite să mă reduc la subprobleme mai mici. Și apoi, ceea ce face programarea dinamică este pentru că am doar un număr polinomial de subprobleme și am presupus că am calculat deja care sunt acestea, am memorat deja care sunt soluțiile la acele probleme, apoi pot doar forța brută local. peste toate răspunsurile posibile la această întrebare. Și acesta este o modalitate de a privi programarea dinamică. Bine, deci atunci când vorbeam despre ordinea topologică, argumentând că relația este aciclică. În esență, definirea a ceea ce înseamnă mai mic atunci când spunem că recurgem la subprobleme mai mici. Ce înseamnă mai mic? De obicei, spui că un indice sau un parametru al subproblema mea scade sau crește întotdeauna. Uneori, nu este întotdeauna cazul. Uneori, trebuie , poate, să adaugi câțiva indici și să vezi că asta crește întotdeauna, pentru că unul poate rămâne același în timp ce celălalt crește sau ceva de genul ăsta. Dar, în general, atâta timp cât susțineți că relațiile sunt aciclice, atunci graficul subproblemei este un DAG. Și puteți calcula într-o manieră de jos în sus. Și nu obțineți bucle infinite în recursiunea dvs. OK, ultimul lucru, ultimele două lucruri sunt un fel de contabilitate. Dar dacă nu le scrieți la examen, nu vă putem oferi puncte pentru ele. Așa că scrieți astea. Cazuri de bază, dacă nu ne spuneți cazuri de bază, atunci algoritmul dvs. nu poate fi timp polinomial. Nici măcar nu poate fi un timp finit, pentru că algoritmul tău nu se oprește niciodată. Pur și simplu continuă să recurgă pentru totdeauna și pentru totdeauna. Și deci este greu să ne dai puncte-- Adică, îți vom oferi câteva puncte dacă subproblemele și relația ta sunt corecte. Dar într-adevăr, dacă scrieți cod fără un caz de bază, va fi greșit. Deci cazurile de bază sunt cu adevărat importante. Practic, pentru orice se află la limitele calculului dvs., oriunde relația dvs. recursivă ar ieși, în esență, în afara limitelor notei dvs., să presupunem că am de-a face cu o subsecvență. Și la un moment dat, încerc să indice o stare în care am zero sau elemente negative în secvența mea, probabil că este un lucru rău. Și așa vreau să definesc cum să calculez acele lucruri în timp constant. Astfel încât algoritmul meu să se poată termina când ajunge la unul dintre acele cazuri de bază. Prin urmare, este foarte important să acoperiți toate acele posibile locații ale frunzelor unde doriți să vă puteți întoarce în timp constant. Și vom face o parte din asta astăzi. Prezentați soluții pentru toate subproblemele independente accesibile, în care relația se întrerupe. În esență, aș ieși în afara limitelor lucrurilor mele. Sau orice în care, poate dacă mai aveți un articol, ați putea spune, ei bine, nu am de ales ce să fac cu acel articol. Trebuie să-l aleg sau ceva de genul ăsta. OK, atunci pentru problema inițială, arătați cum să calculați soluția problemei inițiale din soluțiile subproblemelor dvs. Deci, de obicei, aceasta este doar o subproblemă. Este cel care a folosit toate lucrurile și acesta va fi răspunsul meu. Dar nu este întotdeauna cazul. Uneori, ca într-o secvență de creștere cea mai lungă, trebuia să luăm un maxim peste toate problemele noastre pe care le-am calculat, sau suma maximă subbary, a trebuit să facem și asta. Dar, în general, rezultatul pentru subproblemele noastre vrea să fie o valoare scalară pe care încercăm să o optimizăm, sau o booleană, sau ceva de genul ăsta. Acesta este modul în care maximizăm sau minimizăm ceea ce facem. Nu stocăm întreaga secvență a modului în care am ajuns acolo. Pentru că ar putea exista un număr exponențial de subsecvențe posibile care au ajuns acolo. Acesta este scopul programării dinamice. Izolăm complexitatea unei subprobleme la un singur număr. Dar în multe probleme, am putea dori să reconstruim, să zicem, plasarea tigrilor în cuști și nu doar cum... care este disconfortul minim pentru toți tigrii sau ceva de genul acesta, așa cum ați avut în setul dvs. de probleme. Deci chiar vreau să știu unde să pun tigrii în cuști. Și pentru a face asta, de fiecare dată când am maximizat o subproblemă, îmi pot aminti de care subproblemă sau subprobleme am depins, la fel ca în stocarea indicatorilor părinte pe căile cele mai scurte. Și apoi, folosind acești indicatori părinte, pot doar să mă întorc în graficul subproblemei și să îmi dau seama care cale către un caz de bază m-a condus la o soluție optimă. Și apoi ultimul lucru este analiza timpului de rulare. În general, doar însumați munca făcută de fiecare subproblemă. Pentru că presupunerea este că calculezi toate subproblemele pe care mi le-ai descris. Dar dacă munca pe subproblemă este delimitată de aceeași valoare, o puteți înmulți. Deci, aceasta este în general o limită mai slabă, dar de obicei echivalentă asimptotic cu noțiunea mai puternică din stânga. Și practic așa faci timpul de rulare. De obicei, este suficient să... cum determin câte subprobleme am? Ei bine, mă uit la valorile posibile ale fiecăruia dintre parametrii mei. Și apoi înmulțesc acele numere împreună. Mulți oameni vor spune poate, o, le adun împreună. Nu, pentru că pot să aleg fiecare dintre acestea în mod independent. Și așa am înmulțit aceste lucruri împreună. Și apoi munca făcută de fiecare subproblemă este, de obicei, de dimensiunea lucrului pe care îl maximizez, sau îl minimizez sau îl însumez în relația mea. Va fi dimensiunea asta, ramificarea pe care o am, numărul de subprobleme de care depind. Și astfel numărul de subprobleme, probabil că vă uitați la definiția declarației subproblemei . Pentru a găsi munca făcută de fiecare subproblemă, te uiți la relația ta recursivă. Bine, deci cu asta, avem acest cadru foarte frumos. Și o vom folosi pentru a rezolva unele probleme de antrenament, zile fericite. Și acestea sunt puțin mai lungi în ceea ce privește descrierea decât recenzia noastră anterioară a testului 2. Așa că am de gând să le citesc pentru tine. Acesta este un pic mai scurt. Tiffany Bannen dă peste o diagramă de loterie lăsată de un călător în timp din viitor, care listează numerele câștigătoare la loterie și plățile întregi pozitive în numerar pentru următoarele n zile. Are cineva referința aici, Tiffany Bannen? Biff Tannen dintr-o chestie Înapoi în viitor. Deci, acesta a fost de fapt... Cred că este al doilea film Înapoi în viitor în care se întâmplă asta. Oricum, Tiffany vrea să folosească aceste informații pentru a face bani, pentru că știe viitorul despre loterie. Dar este îngrijorat că, dacă joacă numere câștigătoare în fiecare zi, organizatorii loteriei vor deveni suspicioși și o vor închide. Deci ideea de aici este că poate este încă suspect, dar decide să joace la loterie rar, cel mult, de două ori în orice perioadă de șapte zile. Ea va câștiga, dar este destul de rar încât poate să fie întâmplător, poate nu. Descrieți un algoritm de timp liniar pentru a determina cantitatea maximă de câștiguri la loterie pe care Tiff, Tiffany, le poate câștiga în următoarele 10 zile jucând la loterie rar. Acum, acesta a fost un tip deosebit de dificil de p-set, sau primul p-set pe problema de programare dinamică. Dar să încercăm să o facem împreună. Deci aceasta este problema 1. O voi numi doar Lotto. OK, deci cum putem face față subproblemelor aici? Ei bine, s-ar putea să vreau să mă gândesc ce fac în prima zi. O să joc la loterie sau nu? Și apoi recurge la restul. Sună bine, nu? S- ar putea să am ceva de genul... ei bine, să spunem că L din i sunt câștigurile din ziua i. Acesta este un fel ca... asta nu definește notarea de utilizare a plăților în numerar. Și deci fac o variabilă pentru a face asta. Și de dragul a ceea ce este scris pe foaia mea, o să presupun că acesta este 1 index, nu știu de ce. Deci am zilele de la 1 la n. Știu care sunt plățile lor la loterie. Așa că s-ar putea să am subprobleme când îmi fac lucrurile SRT BOT . Ceea ce aș vrea să fac este să văd ce se întâmplă în prima zi și să recurg la ceea ce va fi mai târziu. Așa că s-ar putea să am ceva de genul x din i este câștigurile maxime pentru, cred, posibil pentru zilele de la i la n. Are cineva o problemă cu acest tip de subproblemă? Să vedem la ce m-ar duce acest tip de subproblemă. Pot fie, în pasul meu de relație , care sunt alegerile mele? Pot juca fie în ziua i, fie nu pot juca în ziua i. Dacă încerc să maximizez acest lucru, maximizează. Fie dacă joc în ziua, primesc Li. Și apoi pot recurge la restul. Sau nu-l plănuiesc pe Li și recurg la restul. Cuiva îi place această recurență? De ce nu ne place această recurență? Pur și simplu o să aleg chestia asta. Aceste lucruri sunt întotdeauna pozitive. Cred că sunt întotdeauna plăți întregi pozitive, da. Și așa o voi alege mereu pe Li și problema aici este că nu mă supunem sau nu mă confrunt cu această condiție pe care o am, și anume că am voie să joc doar de două ori pe săptămână, sau nu chiar de două ori pe săptămână. Nu este o perioadă fixă ​​de o săptămână. Este în orice perioadă consecutivă de șapte zile, ceea ce este puțin confuz. Cum îmi pot aminti ce zile am voie să aleg mai târziu? Pare puțin descurajantă. Într-un fel, pentru ca eu să știu -- acesta este un câștig maxim posibil pentru zilele de la I la n. Dar, într-un anumit sens, depinde de zilele pe care le-am ales înainte. Pentru că dacă am ales i minus 1, nu mai pot alege o altă zi pentru încă șase zile. Dacă am... corect, deci am... hai să facem asta exact. Acesta este i minus 1. Am o perioadă de șapte zile, 1, 2, 3, 4, 5, 6, 7. Dacă am jucat la loterie aici și am jucat la loterie aici, atunci nu am voie să joc la loterie aici , Nu am voie să joc aici, nu am voie să joc aici, nu am voie să joc aici, nu am voie să joc aici. Am voie să joc aici. Deci acesta este i plus 1, plus 2, plus 3, plus 4, plus 5, plus 6, i plus 6. Deci, în funcție de ceea ce s-a întâmplat înaintea mea, s- ar putea să nu pot juca până în ziua i plus 6. Dar dacă eu nu am jucat până când... de când încoace, aș putea să joc următorul tip. De fapt, nu știu pe care dintre acestea pot juca în continuare. Într-un anumit sens, trebuie să-mi amintesc în ce zile am voie să joc în continuare. Și vreau să pot... la început, nu am restricții. Mai pot juca pe tipul ăsta, chiar dacă am jucat acolo. Dar, în general, voi fi limitat într-un fel între a putea juca cu acest tip și a putea juca cu acest tip. Și așadar, ceea ce voi face este să-mi generalizez problemele prin stocarea de informații suplimentare, astfel încât să mă pot baza pe acele informații atunci când mă uit în viitor și recurg. Deci, în loc de... , într-un fel, trebuie să-mi amintesc două zile. Unde au fost ultimele două locuri în care am jucat? O să simplific puțin asta spunând că această subproblemă, câștiguri maxime posibile pentru zilele i până la n, voi spune că trebuie să joc în ziua i, restricție similară ca cea mai lungă secvență de creștere, sunt cu siguranță includ asta în următorul meu. Asta îmi va face mai ușor să fiu ca, oh, știu cu siguranță că am jucat în această zi. Va fi... mi-ar fi mai ușor de gândit. Deci, presupunând că joc în ziua I, și de fapt, trebuie să-mi amintesc ce este a doua zi în care pot juca. Așa că voi extinde această subproblemă cu o altă... Cred că acesta este un j. Bine, presupunând că joc în ziua i și mi se permite să joc, cred, și următoarea joacă permisă în ziua i plus j pentru, care sunt intervalul meu posibil de zile pentru j? Pot să joc fie a doua zi, dar nu sunt niciodată restricţionat în ziua trecută i plus 6. Pentru că lucrurile dinaintea mea [AUDIO OUT] sunt mai în dreapta, pentru că încă nu m-am ocupat de ele. Așa că trebuie să mă ocup doar de asta de la 1 la 6. Ei bine, acest lucru este frumos, pentru că mi- a extins subproblemele cu un număr constant. Deci, de fapt, nu am pierdut nimic asimptotic aici amintindu-mi aceste informații. Dar sunt oarecum... îmi pot aminti toate lucrurile care s-ar fi putut întâmpla înaintea mea. Îl comprim în acest număr. OK, deci acum hai să rescriem relația noastră. De fapt, voi merge mai departe și voi folosi mai mult spațiu pe placă, pentru că cred că este mai ușor decât ștergerea. Bine, deci ne uităm la relația mea. Aceasta este o relație destul de complicată. Dar ce se întâmplă acum? Acum, presupun că joc în ziua I. Asta de fapt simplifică puțin lucrurile. Pentru că indiferent de ce, obțin câștigurile în ziua I. Acum, când numesc această subproblemă, mai bine mă asigur că este în regulă că am jucat în ziua i. Dar asta e în apelantul meu. Am permisiunea locală să joc în ziua I. Mă joc în ziua I. Aceasta este definiția subproblemei mele. x din i este că voi maximiza o alegere. Max de... Presupun că o am pe Li, indiferent de ce. Deci asta ar putea ieși din maximul meu. Și apoi o să aleg... ce aleg aici? Nu aleg dacă joc în ziua I. Aleg care este ziua următoare în care joc, astfel încât să pot recurge la această subproblema. Deci, în ce zi pot juca? Ei bine, sunt oarecum restricționat de acest parametru j pe care nu l-am adăugat în subproblema mea în ce zile posibile pot juca în continuare. Am de gând să împart asta în... să comprim asta într-un singur lucru. Deci, x, pot juca pe... Am de ales între a doua zi când joc, undeva între j, care este următorul meu joc permis și cândva în viitor. Deci i plus k, aceasta va fi bucla mea pe care o fac în buclă în termeni de max. Și atunci, la ce sunt restricționat în jocul meu? Depinde cat de departe sunt de eu. Deci, dacă sunt aici, acesta sunt eu. Dacă aleg k să fie a doua zi, nu pot juca de multe, de multe ori. Deci subproblema la care voi recurge este -- acesta este i plus k. Voi recurge pe i plus k. Dar nu sunt în stare să... j trebuie să fie maxim. Pentru că nu pot juca până la i plus 6. Deci acest i plus k plus 6 va fi lucrul meu. Deci, să vedem. Așa că o să pun... să vedem dacă pot despacheta ceea ce am scris aici. Max de 1, 7 minus k. naiba. Oh, o voi pune aici. 1, 7 minus k. OK, dacă aleg k, nu sunt agresiv față de aceste plăci așa cum este Justin. Așa că dacă aleg un k drum jos, nu sunt deloc restricționat. Și, deci, cea mai permisivă opțiune pe care o am aici este 1. Deci, cu siguranță, nu pot fi mai rău decât 1. Dar dacă aleg... și atunci acesta trebuie să fie un număr între 6 și 1. Și așa pot doar să verific celălalt legat. Dacă acesta este cel mai productiv, atunci acesta ar trebui să fie 6. Deci, când k este egal cu 1, acesta ar trebui să fie 6. Și scade de fiecare dată când mai înapoi sau mai înainte aleg acest k. Deci asta va fi subproblema mea. Și aleg peste k in-- de la j, scuze i plus j, scuze, j, mulțumesc, până ce? Asta e întrebarea, până ce? Trebuie să fac bucla peste n? Dacă fac bucla peste n, voi obține un timp de rulare pătratic , care este mai rău decât ceea ce mi se permite să fac. Presupunerea este că trebuie doar să verific numărul constant al acestora. Și de ce ar putea fi asta? Vreo idee? Să presupunem că am... am subproblema mea, recurg. Eu am. Da, nu știu unde este j. j este undeva pe aici, Unu, doi, trei, poate sunt patru, sau ceva de genul ăsta. Să presupunem că aleg niște k aici jos. Ce este asta? Acesta este i plus-- deci acesta este j este 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 , 15, aici, două săptămâni mai târziu. Este vreodată optim pentru mine să fac asta? De ce nu? PUBLIC: Ai putea juca la loto la mijloc și nu l-ar afecta. JASON KU: Da, aș putea juca la loto la mijloc aici, nu? În... de aici până acolo, asta e o perioadă de șapte zile în care am jucat o singură dată. Și de aici până aici, aceasta este o perioadă de șapte zile în care am jucat o singură dată. Deci va fi... acestea sunt valori pozitive. Deci va fi mai optim pentru mine să aleg ceva aici pentru a juca. Deci, cât de departe... Adică, aș putea folosi doar 15 și asta m-ar mulțumi. Pentru că ți-am argumentat deja că nu este niciodată optim. Pot verifica asta. Nu va fi optim. Va fi mai optim să joci ceva timp aici. Dar cât de departe trebuie să verific? Ei bine, poate trebuie să verific până la 7. Funcționează? Nu chiar. Deci, să presupunem că am jucat aici, și am jucat aici, și am jucat aici, și am jucat aici, de fapt nu pot juca aici, aici, aici, aici, aici. Nu am voie să le joc. Bănuiesc că acestea ar trebui să fie O. Am jucat acolo. Și nu am voie să joc aici, 1, 2, 3, 4, 5. Dar am voie să joc oriunde aici. Deci, practic, vreau să micșorez asta până când aceste X-uri se ciocnesc între ele. Pentru că atunci este posibil ca o soluție optimă să solicite să le aleg pe acestea două și apoi să le aleg pe acestea două de acolo. Deci acestea sunt 10 lucruri la mijloc. Trebuie doar să merg până la, cel mult, 11. Este 11. Acum, puteți muta orice constantă peste 11 și puteți obține același timp de rulare. Dar asta e analiza mea. OK, deci avem relația noastră recursivă. Și deci ce fac? Mă uit doar la alegerile mele de a doua zi pentru a juca. Repet la chestia asta în care chiar cânt în ziua aceea. Dar îmi amintesc informațiile despre ceea ce mi se permite să joc în continuare limitând, în funcție de valoarea mea anterioară. Deci ăsta e genul de lucru cheie. Îmi amintesc ceva mai în avans sau îmi amintesc ce sa întâmplat în trecut, descriindu-l ca o restricție a ceva în viitor. Deci aceasta a fost o problemă destul de dificilă. Cred că a fost una dintre primele noastre probleme de programare dinamică la acel termen. Probabil a fost puțin ambițios. PUBLIC: Vrei să spui că această recurență crește până la 11? JASON KU: Da, recurența crește până la 11, nu 10, 11. Deci avem tipul nostru topologic. Care este un gând topologic pentru aceste subprobleme? Cineva? k va fi întotdeauna un număr pozitiv. Pentru că j trece de la 1 la 6. Deci voi crește mereu în această primă cantitate. Deci, pentru x din i, j, i întotdeauna-- îmi pare rău, depinde de i strict mai mare. Deci, acest i, când numesc subprobleme, el numește întotdeauna subprobleme cu un i mai mare. Acum, asta e puțin ciudat, pentru că am vrut să depind de subprobleme mai mici, mai mici. Acum, este mai mic, pentru că iau un sufix mai mic. Dar corespunde folosirii unui număr mai mare. Pentru mine, este puțin confuz, dar este în regulă. Pentru că folosim lucruri care merg mereu monoton într-o anumită direcție. Deci, aceasta corespunde într-o oarecare măsură unei subprobleme mai mici . Este numărul de elemente la care recurgem de fapt. Într-un anumit sens, dacă am scrie asta ca prefix, ne-am face să depindem de un i strict mai mic. Și asta ar fi mai natural în ceea ce privește recurgerea la subprobleme mai mici. Dar mă abat. Bine, atunci avem subproblema noastră inițială. O să... Nu pot muta această placă. Voi continua, pentru că avem o mulțime de panouri. OK, subproblema noastră inițială, acum, ce aș putea face? Trebuie să încep de undeva. Aici, subproblema mea presupune că încep de la i. Dar nu știu de unde încep. Aș putea începe prin a lua primul element, dar s-ar putea să nu. Așa că aș putea lua maximul peste tot i, peste tot i din x ce? Primul, nu sunt limitat la ceea ce aleg în continuare. Deci, care este cea mai permisivă versiune a lui j? Unu, am voie să iau următorul j. Deci, dacă iau maximul peste toate aceste subprobleme, voi obține soluția. Acum, de fapt, aceasta este puțin mai multă muncă decât am nevoie. Aceasta este în buclă peste toate n. Cu siguranță este corect, pentru că trebuie să încep de undeva. Dar voi începe vreodată după primul, nu știu, 7? Nu, așa că aș putea să iau acest maxim peste primul număr constant. Și asta ar fi bine. Dar este in regula. Acesta este încă mai mic decât numărul de subprobleme pe care le avem. PUBLIC: Dacă aș fi leneș în timpul examenului și aș fi trecut peste j, ar fi corect? JASON KU: Dacă aș trece peste j pentru? PUBLIC: [INAUDIBIL] peste orice lucru posibil. JASON KU: A luat bucla peste asta și j? Da, tot ar fi bine. De ce nu? Este doar mai puțin... este mai restrictiv pentru subprobleme. Nu va fi niciodată mai bine să faci asta. Dar ai putea face asta, pentru că nu ți-ar schimba timpul de funcționare. PUBLIC: Ar putea să- mi schimbe timpul de rulare dacă j-ul meu s-ar fi făcut din greșeală prea departe? JASON KU: Ei bine, j este limitat să fie de la 1 la 6. Deci nu sunt... Nu cred. Dar într-o problemă diferită, într- un context diferit, s-ar putea. OK, deci acesta este originalul. Și în timp aici, ce avem? Avem un număr liniar de subprobleme, număr de subprobleme. Avem... De fapt îmi place, de obicei, să spun exact câte subprobleme am. Oh, nu am făcut caz de bază. Mi-a ratat BOT, mi-a ratat B. Vom face mai întâi originalul. Și apoi cazul de bază. OK, caz de bază, ce avem aici ca caz de bază? Ei bine, când nu am ce face. Dacă sunt... și de fapt, dacă am această situație pentru i egal, să zicem, n, am primit ultimul meu lucru. Aș putea începe să fac bucla peste probleme care sunt negative în ceea ce privește indicele meu. Nu o să vreau să fac asta. Există câteva moduri în care mă pot descurca cu asta. Aș putea seta o valoare pentru toate problemele mele pentru i negativ. Ăsta e un lucru pe care l-aș putea face. Dar apoi trebuie să-mi amintesc, sau trebuie să-mi dau seama cât de departe merg în negativ. Ăsta e un lucru pe care l-aș putea face. Și dau un caz de bază pentru fiecare dintre aceste cazuri. Nu am nimic. Așa că primesc o... nu știu, valoare zero pentru a juca în viitor, pentru că am lucruri negative. Nu pot face nimic cu asta. Un alt mod de a gestiona asta, pe care cred că l-am făcut în soluțiile mele, a fost să restricționez că k doar să fie-- Presupun și restricționez că i plus k este mai mic sau egal cu n. Și apoi, nu voi merge niciodată la probleme negative. Nu voi recurge niciodată la aceste lucruri. Dar asta înseamnă că atunci când apelez la asta pe n, când mai am o singură zi la loterie, acest set va fi gol. Deci care este maximul peste chestia aia? Max peste un set gol? Nu știu. Adică, aș putea adăuga 0 aici, acesta este un mod în care aș putea face asta. Sau aș putea spune doar când sunt la n, și acel lucru este gol, sau ori de câte ori este gol, putem spune cazul de bază x i, j, cred că am putea pune acest lucru la n egal cu 0, sau scuze, este egal cu L de i, L din n, mulțumesc. Pentru că la ultimul tip, trebuie să folosesc Ln. Deci iată. Acum, de fapt, dacă scrieți corect acest lucru, am pus Li-ul în afară și îl unesc cu 0, de fapt pot scăpa doar cu relația și fără caz ​​de bază. Pentru că relația mea se reduce de fapt la un caz de bază, din cauza modului în care mi-am scris relația. Dar, în general, veți dori să scrieți un fel de caz de bază aici fie pentru a recunoaște că relația dvs. se ocupă de asta, fie pentru a fi specific cu privire la ceea ce se întâmplă atunci când nu mai pot lucra. Și ultimul lucru, timpul, avem n subprobleme exact ori mai mult decât munca constantă per subproblemă. Pentru că fac bucla peste 11 valori posibile, de fapt, este până la 11, pentru că j ar putea fi 6. Deci, acesta este ordinul n total de lucru. Deci aceasta este o primă problemă destul de descurajantă. Dar în ceea ce privește ceea ce a vorbit Erik, profesorul Demaine, ultima prelegere, în ceea ce privește clasificarea subproblemei sau categorizarea programelor dinamice, ce avem? Avem o subproblemă de sufix în care ne-am extins cu câteva informații locale, amintindu-ne când mă pot juca data viitoare. Deci asta este un fel de clasificare a acestor subprobleme. Relația de recurență are ramificare constantă, dar mai mult de două ramificații. Și combin o grămadă de subprobleme în evaluarea mea inițială. Și dacă am vrut să aflu în ce zile ar trebui să joace Tiff la loterie, puteți stoca indicații pentru părinți când evaluez acest maxim. Îmi dau seama ce subproblemă x recurg - asta mi-a dat maxim. Și pot să mă întorc să văd ce alegeri am făcut pentru a afla în ce zile am jucat la loterie. Are sens? Deci vreo întrebare despre problema 1? Asta e cel mai... Am vrut să am mai întâi cel mai complicat. Ca să putem avea un drum mai ușor de parcurs. Într-un fel, aceasta este cea mai complicată versiune a acestui tip de configurare de programare dinamică destul de simplă . De ce spun configurare simplă de programare dinamică? Sunt doar sufixe. Și fac doar o cantitate constantă de muncă locală pentru mine. Este doar o configurație locală foarte complicată. Dar asta vreau să spun prin simplu. Când proiectăm subprobleme, aceasta este una pe care am putea-- Adică, atunci când proiectăm probleme pentru această configurație de programare dinamică, este una dintre cele mai dificile din a-- este una dintre cele mai ușoare din punct de vedere conceptual, dar unul dintre cele mai greu de implementat. OK, deci problema 2, aceasta este una lungă. O familie bogată, Alice, Bob și tânărul lor fiu Charlie navighează în jurul lumii. Când se confruntă cu o furtună masivă, Charlie este aruncat peste bord, presupus că s-a înecat. Acesta este un limbaj foarte colorat pentru acești scriitori de seturi de probleme. 20 de ani mai târziu, un bărbat vine la Alice și Bob, pretinzând că este Charlie, fiind probabil părăsit pe o insulă atât de mult timp. Alice și Bob sunt entuziasmați, dar sceptici. Și au comandat teste de potrivire de la compania de teste genetice 46 și Thee. Având în vedere Alice și Bob... scuze, având în vedere trei lungime n secvențe de ADN, practic șiruri de CGTA, sau ceva de genul acesta, din fiecare dintre Alice, Bob și Charlie, centrul de testare va determina trei... ascendența lor, după cum urmează. Dacă lui Charlie poate fi împărțit în două subsecvențe, nu neapărat adiacente, de lungime egală, deci, practic, pot lua-- dacă am n este lungimea 5 sau lungimea 6, ar fi mai bine să fie par. Trebuie să găsesc trei personaje în ordine. Și apoi celelalte trei personaje trebuie să se potrivească pentru a face niște subșiruri - niște subsecvențe în ADN-ul lui Alice și Bob. Deci este puțin greu de analizat. Deci haideți să vedem un exemplu aici. De exemplu. Alice este AATT. ADN-ul lui Bob este CCGG. Dacă Charlie ar fi CATG, ar fi potriviți, deoarece CG este o subsecvență a ADN-ului lui Charlie și este o subsecvență a ADN-ului lui Bob. Și AT este o consecință a ADN-ului lui Charlie. Și este, de asemenea, o consecință a ADN-ului lui Alice. Și astfel le-am împărțit în două subsecvențe de lungime egală . Acestea nu sunt neapărat subsecvențe consecutive, ci orice subsecvențe, astfel încât să apară în Alice și Bob. Dar dacă Charlie ar fi găsit a fi un impostor, dacă secvența lui ar fi AGTC, în esență, este ușor de realizat asta, deoarece G și C sunt schimbate în ceea ce privește ordinea lor. Și GC, literele GC apar doar în ADN-ul lui Bob și nu apar în această ordine. Așa că este ușor de înțeles că e un impostor cu aceste șiruri. Dar vă puteți imagina, cu șiruri mai lungi, acest lucru ar putea fi dificil de rezolvat. Așa că vrem un algoritm de la n la a 4-a timp pentru a determina dacă Charlie este o fraudă. OK, așa că de fapt am scurtat-o ​​aseară. Acest lucru a fost de două ori mai lung pe setul de probleme. Deci da, oricum, deci cum abordăm această problemă? PUBLIC: [INAUDIBIL]. JASON KU: Nu, nu trebuie să fie învecinate. Ca și în exemplu, ar fi potrivit dacă C și G sunt o subsecvență, nu contiguă, a CATG. Da, deci asta este o parte importantă a acestei probleme. Doar că... nu încerc să-mi dau seama dacă există... practic, există doar două subsecvențe contigue de lungime 2n în care acest lucru poate fi împărțit. Mă uit doar în mijloc. Nu, căutăm subsecvențe, nu subșiruri. Deci se cam intercalează așa într-un fel. Și există, de fapt, o serie de moduri diferite în care pot partiziona asta. Există de fapt un număr exponențial de moduri. Deci asta este o problemă, potențial. Da. PUBLIC: Există o bază biologică? JASON KU: Nu, nu există nicio bază biologică pentru acest lucru pe care eu îl cunosc. Bine, bine, deci cum rezolvăm această problemă? Ce problemă arată asta? Adică, pare o potrivire a șirurilor. Așa că aș vrea să cred că este ceva de genul cea mai lungă secvență comună. Dar aici, am trei secvențe în loc de două secvențe. Și avem această altă stare ciudată în care avem nevoie de o partiție exactă a lui Charlie. Trebuie să folosesc toate literele din Charlie, dar nu trebuie să folosesc toate literele din Alice și Bob. Deci, să obținem o notație aici A, B și C sunt n șiruri de lungime. Deci ce as putea face? Să definim câteva subprobleme. Dacă ar fi să trec prin cea mai lungă subsecvență comună, aș putea urmări un index al unui sufix sau prefix al fiecăruia dintre aceste șiruri. Asa are sens. Ceva de genul i, j, k, unde vorbim despre sufixe-- îmi pare rău, sunt prefixe, i, B, j și C, k. Asta pare rezonabil, cel puțin. Este ceea ce am face pentru cea mai lungă secvență comună. Care este problema aici? Adică, aș putea să pot potrivi tipul ăsta cu unul dintre acești tipi, sau să decid să-l omit și să pot potrivi cu unul dintre acești tipi și să decid să-l omit. Dar dacă fac asta, s- ar putea să primesc o consecință. Dar, de fapt, întotdeauna trebuie să potrivesc tot C. Are sens? Întotdeauna trebuie să potrivesc tot C. Deci, într-un sens... Să vedem, cum pot face asta? Trebuie să potrivesc tot C. Dar trebuie, de asemenea, să mă asigur că folosesc exact n peste 2 caractere din C în B. Și exact n peste 2 caractere din C în A? Are sens? Deci, cum pot îndeplini această condiție? Acum înțeleg de ce am folosit prefixele înainte. Și l-am schimbat la sufixe aici. Dar o vom face să funcționeze. Cum îmi pot aminti câte personaje am atribuit de la Alice versus Bob? Pe măsură ce potrivesc personaje din Alice și Bob, trebuie să-mi amintesc unde indică ele sau câte le-am folosit deja în Charlie. Ca să pot împărți restul aici. Oh, de fapt, asta funcționează într-un sens diferit. Există 18 moduri diferite în care am putea face asta. Deci, OK, așa că trebuie să-mi amintesc câte am consumat deja, astfel încât să fiu sigur că voi aloca exact atâtea caractere în viitor fie lui Alice, fie lui Bob. Deci, cum îmi pot aminti asta? Îmi amintesc doar. Câți am... Voi face așa cum am făcut-o înainte, adică îmi pot aminti... Îmi amintesc două lucruri diferite aici. Îmi amintesc câte lucruri mi-au mai rămas pentru a se potrivi cu Alice, în C, sau îmi pot aminti câte lucruri le-am potrivit deja în C cu Alice. Dacă vorbesc despre câte lucruri am potrivit deja, atunci pot indexa acest lucru după suma acelor lucruri. Dacă vorbesc despre câte lucruri mai am de egalat, trebuie să fac n minus lucrurile. Deci, aceștia sunt diferiții parametri pe care îi putem face. Vom face ceea ce este în notele mele. Și voi încerca să o repar. Deci ceea ce vom face este să ne amintim... sau să ne dăm seama câte lucruri mai am nevoie să potrivesc în C cu Alice și Bob. Așa că o să numesc asta k-- îmi pare rău, ki. i este asociat cu A. Iar B este asociat cu j. Și kj, acesta va fi... Trebuie să notez asta. Deci, acesta va fi ce fel de ieșire vreau pentru subproblema mea? Vreau doar să știu dacă aceste lucruri sunt... dacă este un fraudator sau nu. Deci acesta va fi un boolean. Adevărat dacă poate potrivi lungimea ki subsecvența sufixului A, sufixul este acest tip și lungimea kj, presupun, kj lungime subsecvența sufixului B, ji sau Bj sufixului, la toate caracterele în. Și acum în ce este aceasta? Aceasta este partea grea. Am nevoie de un index separat pentru C ca să știu unde sunt în C? Într-un fel, da, trebuie să știu unde sunt în C, cât de mult trebuie să egalez. Dar dacă trebuie să potrivesc ki la kj cu toate, atunci mai bine să rămână lucruri ki plus j în C. Deci, într-un fel, nu trebuie să-mi amintesc din nou acea informație. Nu este independent de ceilalți parametri ai mei. O pot calcula. Aș putea să-l arunc, dar îl pot determina din ceilalți parametri. Și așa vreau să- l potrivesc cu sufixul lui C de lungime ki plus kj. Deci cred că aceasta este singura parte care va fi enervantă pentru mine. Deci, acesta ar trebui să fie sufixul tuturor lucrurilor minus ki minus kj minus 1. Este doar asta. De ce, mă rog? Dacă m-am potrivit cu totul, ki și kj sunt ambele 0. Și nu ar trebui să am nimic în C, care ar trebui să n două puncte. Suntem la indice 0, da suntem. Ori de câte ori folosesc notația Python, ar fi mai bine să fiu 0 index. Are sens asta ca subproblemă? Adică, este confuz. Dar sperăm că are sens. Ceea ce voi încerca să fac este să potrivesc un anumit număr de caractere din acest sufix, care, sperăm, este mai lung decât ki. În caz contrar, este... Voi fi într-un caz de bază în care acest lucru este imposibil. Și o parte din aceasta s-a potrivit complet cu aceasta. Deci astea sunt subproblemele mele. Am să încerc să le relatez acum. Avem x, i, j, ki, kj, cu ce va egal? Ei bine, avem booleeni. Deci asta este și fals în rest. Acesta este un boolean. Așa că am nevoie doar de o subproblemă la care recurg să fie adevărată. Deci, care este comutatorul pentru unele dintre o grămadă de opțiuni, alegeri booleene, dintre care oricare ar putea fi adevărată? Vreau să combin o grămadă de ele. Vreau doar să văd dacă vreuna dintre ele este adevărată. Mă duc la sau peste ei. Mă duc la sau peste patru variante. Care sunt alegerile mele? Ori primul lucru din A se potrivește cu C, primul lucru din B se potrivește cu C, ori eu nu potrivesc cu niciunul. Deci astea sunt cele patru alegeri ale mele. Deci, dacă potrivesc cu A, i plus 1, recurg la un sufix mai mic de A și a-- prin adăugarea-- oh, totul funcționează, grozav. Kj, acesta este i, dacă Ai este egal cu Ci și Ai este mai mare decât 0. Deci, dacă ki este mai mare decât 0, trebuie să potrivesc un i. Deci, acest condițional nici măcar nu are sens decât dacă am evaluat acest ki ca fiind mai mare decât 0. În caz contrar, încerc să accesez i din n. Așa că pun această condiție acolo. La fel și cu potrivirea B, ij plus 1, ki, kj, plus 1 dacă-- îmi pare rău, acesta ar trebui să fie minus 1. Am mai puține caractere pe care trebuie să recurg. Deci asta e o greșeală de tipar în notele mele. Bj este egal cu C. Oh, acesta nu este Ci. Ce este asta? Este orice ar fi acel lucru. Deci voi spune doar semnul întrebării și kj este mai mare decât 0. Așa că îl voi completa în note. Va fi o expresie complicată care arată așa. Este exact acea expresie. Da, așa este. Deci este chestia aia. Bine, atunci mai avem două opțiuni. Ori eu... dacă nu m-am potrivit cu Ai, s- ar putea să-l potrivesc pe Bj pe viitor. Deci vreau doar să reduc Ai. Deci xi plus 1, las totul la fel. Presupunând că i mai mic decât n, nu vreau să trec de la sfârșitul acestui lucru, sau x, i, j plus 1, ki, kj dacă j este mai mic decât n. Deci astea sunt cele patru alegeri ale mele. Dacă potrivesc litera n, grozav. În caz contrar, scad dimensiunea subproblemei mele și recurg. Deci recursive amuzante, sortare topologică, aceste subprobleme depind doar de ce? eu mai mare? Nu chiar. j mai mare? Nu chiar. Schimbarea k sau... acestea nici măcar nu se schimbă aici. Așa că o să folosim depinde de mai mare, cred, strict... ăsta e un lucru important, i plus j. Pentru că cel puțin unul dintre aceste două lucruri crește. Și apoi lucrul frumos este că ne spune când ar trebui să ne oprim. Ar trebui să ne oprim atunci când fie i, fie j ajung la n. Ar trebui să știm suficient, în acel moment, pentru a putea determina dacă am reușit sau nu, eventual. Deci avem cazul nostru de bază. Care este cazul de bază ușor? Când am reușit. Când am reușit? Dacă nu mai avem nimic în A și B Și nu mai avem nimic în C. Nu mai am nimic de egalat. Deci am nn. Și nu am nevoie de un chibrit de nimic altceva. Asta va fi adevărat. Toate drumurile indică această subproblemă pentru a ajunge la o soluție adevărată. În caz contrar, avem câteva cazuri de bază false. Dacă ai configurat așa ceva și ne dai doar un caz de bază care este adevărat și te gândești la lucruri, răspunsul tău va fi întotdeauna adevărat. Deci nu ai deloc putere discriminatorie. Dacă ne oferiți un caz de bază adevărat, mai bine ne oferiți niște cazuri de bază false , sau cel puțin unul. Deci, în cazul în care primul este n Și avem niște i, kj, acesta va fi fals dacă ce? Dacă nu mai avem nimic în Ai sau A, dar tipul ăsta este pozitiv, avem probleme. În caz contrar, acest lucru este 0. Și vom încerca doar să potrivim totul aici. Și în cele din urmă, vom ajunge la acest caz de bază sau ceva în care acest lucru ajunge la 0 și avem o problemă. Și același lucru este valabil și pentru cealaltă parte. Dacă rămânem fără lucruri în B, atunci când numărul de lucruri pe care trebuie să le potrivim în B este mai mare decât 0. Deci acestea sunt cazurile noastre de bază. Problema initiala este care? Da, va fi doar una dintre subproblemele noastre, nn, și apoi n peste 2 și n peste 2, încercând să potrivim jumătate din lucrurile din C cu jumătate dintre lucruri. PUBLIC: Primele două argumente ar trebui să fie 0. JASON KU: 0, mulțumesc, pentru că suntem 0 index, da. Din nou, asta e... trecerea de la prefix la sufix la mijloc este distractiv. Și mai bine ar fi cazul că n este 2, sau altfel este evident fals - sau este par, sau altfel este evident fals. Și apoi, ultimul lucru, pe care nu îl voi scrie, este că avem o muncă constantă aici. Pentru că doar verific valoarea a patru subprobleme și un condiționat pentru fiecare. Și am câte subprobleme? i bucle peste n, j bucle peste n, k și kj bucla peste n peste 2. Așa că am un număr quartic de subprobleme, timpul de rulare quartic așa cum este proiectat. Deci nu am de gând să scriu asta , pentru că am întârziat destul de mult . Probabil că o să fac... doar mai fac o problemă, ceea ce este trist, pentru că ultima este despre Gokemon Po, care este o problemă distractivă. Gokemon Po se bazează practic pe că încerc să prind o grămadă de monștri de buzunar, doar monștri, cred că este în asta. Și poți fie să mergi într-o locație și să prinzi acel monstru gratis, dar asta costă bani, pentru că trebuie să merg acolo. Sau nu trebuie să merg în acea locație și o cumpăr din achiziția în aplicație, dar asta mă costă o sumă diferită de bani. Dar cumpărând-o din achiziția în aplicație m- a ținut în locația în care eram anterior, oriunde m-aș afla. Și deci ideea acestei probleme este că trebuie să-mi amintesc unde am fost ultima dată. Ca să știu cât de departe trebuie să călătoresc pentru a ajunge la următorul meu monstru. Deci asta va fi ultimul la care nu voi putea ajunge. Numărul 3 este o problemă legată de tapas. Deci toate acestea vin din primăvara lui '18. Primele două au venit dintr-un set de probleme. Următoarele două provin de la examenul final din acel an. Obert Ratkins este la dietă. Dar ia o cina la un bar de tapas de lux , de unde a luat multe-- va comanda multe farfurii mici. În meniu sunt n farfurii cu mâncare , unde fiecare farfurie are o anumită informație, are un volum, numărul de calorii din acel fel de mâncare. Și o etichetă de dulceață, practic 0 sau 1, indiferent dacă este dulce sau nu. Dar e la dietă. Și vrea să mănânce nu mai mult de k calorii în timpul mesei, dar vrea să-și umple stomacul cât mai mult, pentru că vrea să se simtă sătul. Așa că vrea să maximizeze volumul pe care îl umple, chiar dacă vrea să reducă numărul de calorii - să restrângă numărul de calorii. De asemenea, vrea să comande exact farfuriile dulci. Deci avem această altă condiție în care trebuie să mă asigur că mănânc un anumit număr de farfurii dulci. Ar putea fi util pentru mine să-mi amintesc câte farfurii dulci am mâncat deja. Așa că mă asigur că mănânc acel număr, fără să cumpăr același fel de mâncare de două ori. Deci, iată o condiție care este similară cu problema rucsacului 01 , față de o problemă generală de tip rucsac. Am voie să iau mai mult de unul dintre aceste lucruri sau nu? Aici, este o restricție că nu am voie să iau o farfurie de mai multe ori. Și voi încerca să descriu un algoritm de ordin nks pentru a găsi volumul maxim de alimente pe care Obert îl poate mânca având în vedere dieta sa. Deci, primul lucru pe care îl voi remarca aici este unul dintre lucrurile despre care am vorbit la ultima prelegere de programare dinamică a fost că acesta este un timp de rulare polinom pe care mi-l cere. De fapt, pe setul dvs. de probleme 8, vi s-a cerut pentru fiecare problemă să clasificați dacă timpul de rulare al algoritmului dvs. a fost polinom sau nu. Și de fapt, nu trebuie să rezolvați problema pentru a răspunde la acea întrebare dacă vă oferim timpul de funcționare. Dacă vă dăm timpul de rulare, puteți doar să aruncați o privire la acel timp de funcționare și să spuneți, oh, este acel polinom și dimensiunea intrării mele. Și aici este? Toate cele anterior au fost. Acesta a fost ordinul nr. Aceasta a fost ordinea n pătrat, deoarece n a fost numărul de lucruri din intrarea mea, numărul de cuvinte necesare pentru a vă oferi acea intrare. Aici, ce am? Am câte un triplu de numere pentru fiecare farfurie. Sunt n dintre ele. Deci n este polinom. polinomul s deoarece s este mai mic decât n și este un număr pozitiv. Dar k, k este doar un număr din intrarea mea. Este reprezentabil, potențial, într-un singur cuvânt, aceasta este presupunerea. Dar ar putea avea o dimensiune exponențială în funcție de dimensiunea cuvântului meu al mașinii mele. Nu știu cât de mare este k în raport cu n. Și deci acesta este un timp de rulare pseudopolinom. Pentru că k este doar un număr din problema mea, similar cu suma subsetului, similar cu rucsacul, pe care l-ați făcut la prelegere și la recitare. Și așa că, dacă te întrebăm la un examen, ceea ce probabil o vom face, dacă anumiți timpi de rulare sunt polinomii sau nu, asta e logica că te descurci. Cât de mare este intrarea mea? Care este timpul meu de funcționare pe care încerc să îl evaluez? Și pot lega fiecare dintre acești termeni în ceea ce privește dimensiunea intrării mele? Dacă nu, atunci spui că este pseudopolinom. Bine, deci să încercăm să rezolvăm această problemă. Deja, pentru că avem pseudopolinom, vă gândiți că poate acesta va fi asemănător unui rucsac sau al unei sume subset. De ce am nevoie să... Voi merge direct la subprobleme aici. De fapt, probabil că ar trebui să spun care sunt lucrurile mele. Meh, asta e bine. Am renunțat la notație acolo, nu-i așa? Deci vom avea subprobleme. Voi... vreau să maximizez numărul, volumul de alimente. Deci asta ar trebui să fie probabil rezultatul subproblemei mele, volumul maxim pe un subset de vase. Voi alege aici sufixele. i și alte lucruri vor fi volumul maxim de alimente posibil pentru farfuriile de la Pi la Pn. Vom asuma un index aici, pentru că de ce nu? Dar trebuie să-mi amintesc informațiile pe parcurs? Da, la fel ca în cazul sumei subsetului sau al rucsacului, am nevoie de... Am această limită de calorii. Așa că îmi va fi foarte util să știu câte calorii am mâncat deja sau câte calorii mi- au rămas în buget. Deci să zicem j, folosind cel mult j calorii din restul felurilor de mâncare. Și trebuie să mă asigur că mănânc exact un anumit număr de farfurii dulci în viitor. Și trebuie să-mi amintesc, pe măsură ce mănânc o farfurie dulci, numărul de farfurii pe care trebuie să le mănânc scade. Și așa vreau să generalizez asta. Voi pune un prim aici pentru a indica faptul că mănânc exact farfuriile dulci. OK, deci asta e subproblema mea. Am o mulțime de spațiu la bord. O să merg înainte și să-l folosesc. Relație, avem x, i, j, s prim este egal... OK, încerc să maximizez volumul. Probabil, vreau să maximizez ceva. Acest combinator este cam așa cum îmi place să-l numesc. De obicei, ceea ce faci în programarea dinamică este să faci un fel de alegere sau combinare -- combinarea, combinarea, combinarea unui număr de subprobleme și alegerea care este cea mai bună. Dacă doar enumerați o grămadă de opțiuni aici și nu ne spuneți cum să le combinăm, aceasta va fi o problemă. Pentru că nu știm deloc ce face programul tău dinamic . Prin urmare, este foarte util pentru tine să ne poți spune cum îți combini subproblemele. Aici, facem o maximizare a diferitelor volume posibile. Dacă decidem să mâncăm farfuria i, atunci obținem Vi în volum, ne umplem burtica cu Vi în volum. Dar apoi trebuie să recurgem la folosirea unei farfurii mai puțin, pentru că nu putem folosi acea farfurie din nou. Și am scăzut cantitatea de calorii din bugetul nostru. Și am să spun s prim minus si, pentru că si este 1 dacă este dulce și 0 dacă nu este. Așa că este oarecum frumos că ne-au cam dat această notație aici. Pot să o scad dacă este acolo. Nu trebuie să fac acest condițional sau așa ceva. Și nu vreau să merg niciodată sub aceste bugete. Deci voi spune doar dacă Ci este mai mic sau egal cu j și si este mai mic sau egal cu s prim. Deci asta mă va asigura că băieții ăștia nu devin negativi niciodată. Altfel, nu mănânc farfuria. Și acesta este un caz ușor, pentru că merg doar i plus 1, j, s prim. Aceste lucruri nu s-au schimbat. Mai am un lucru mai puțin. Așa că maximizez aceste lucruri. Acesta este întotdeauna. Nu este un dacă. Deci am doar două opțiuni. Și maximizând peste ele, ordinea de sortare topologică, aici, recurg întotdeauna la un lucru cu i mai mare. Depinde de i mai mare, deci aciclic, fericit. Cazuri de bază, care este cazul bun? Ajung la final, am ajuns la capătul meniului, nu mai pot să mă uit la farfurii, sunt umplut. Și mi-am interzis deja să fac negativ calorii. Deci ar trebui să fie totul bine. Dar ce vreau pe al treilea parametru? 0, mai bine am mâncat exact farfurii. Așa că vreau să cobor la x n plus 1, pentru că sunt 1 indice, j, pentru orice j, 0. Va fi 0. Nu am calorii acolo. Dar este un lucru bun. Este un loc bun. Este bine. 0 este bun. S-a făcut, nu știu. OK, există un alt caz de bază. Care este cazul de bază prost. Ajung până la capăt. Întotdeauna cresc i. Și deci mai bine fac ceva pe n plus 1. Am ajuns la final. j din nou, va fi nenegativ. Pentru că vom fi mereu în bugetul caloric. Dar dacă acesta este altceva decât s prim mai mare decât - dacă este altceva decât 0, ce va fi acesta? PUBLIC: Ar fi minus infinitul. JASON KU: Minus infinit. Nu vreau să fiu niciodată în această situație. Dacă îmi fac programul dinamic și primesc un minus infinit în sus, înseamnă că nu există nicio cale către această subproblemă aici, unde sunt fericit. Sunt mereu trist. Și așa revin că volumul maxim de alimente pe care Obert poate să mănânce și să-și mențină dieta nu este posibil. În esență, nu există mâncăruri, mâncăruri dulci în chestia al căror buget caloric este sub limita mea. Și probabil că este un lucru mai ușor de verificat decât în ​​această bandă. Deci avem subproblemele noastre inițiale acum. Soluția este dată de ce? Doar una dintre subproblemele noastre, este doar să vedem care este volumul maxim. Nu trebuie să-mi revin pe pași ca să-mi dau seama. Eu doar... Spun una dintre subproblemele, este folosirea tuturor lucrurilor din meniul meu, folosirea întregului meu buget k și încercarea de a obține exact lucrurile. Aceasta va fi rezultatul meu pentru algoritmul meu. Și asta durează în ce timp? Câte subprobleme am? Am n plus 1 subprobleme pentru acest parametru. Am k plus 1 lucruri posibile pentru acest parametru. Și am s plus 1 lucruri posibile pentru acest parametru. Deci primesc ordine nks subprobleme, subprobleme. Cât de multă muncă pe subproblemă, doar maximum două lucruri, așa că munca constantă pe subproblemă dă ordin nks timp total. Deci, acestea sunt trei probleme practice frumoase pentru tine, două care sunt polinomiale, una care este pseudopolinom. Mai aveți un exemplu acolo, care este problema Gokemon Po , care este o problemă distractivă. Implică amintirea unor informații suplimentare care nu sunt chiar un număr pseudopolinom în problema ta. Dar este locul unde am fost ultima dată sau unde mă duceam. Așa că uită-te la această problemă. Este un alt fel de mod non-trivial de a extinde subproblemele. OK, și cu asta, mult succes la testul 3.