[SCRÂTÂND]
[FOȘTIT]
[CLIC]
ERIK DEMAINE: Bine ați venit
înapoi la 006,
Programare dinamică.
Suntem acum la pasul
doi din patru --
vom vedea o grămadă de
alte exemple -- încă
trei exemple de
programare dinamică -- cea
mai lungă subsecvență comună,
cea mai lungă subsecvență în creștere
și un fel de
problemă inventată de la 006,
joc alternativ cu monede  .
Și prin aceste
exemple,
vom explora
câteva idei noi, lucruri pe care
nu le-am văzut încă în acțiune
până acum -- ocupându-ne
de secvențe multiple,
în loc de doar una;  se
ocupă de subșiruri
de secvențe,
în loc de prefixe
și sufixe;
indicii părinte, astfel încât să
putem recupera soluții,
ca în cele mai scurte căi.
Și una mare, care va
fi dezvoltată în cea mai mare parte
în următoarea prelegere, este
constrângerea
și extinderea subproblemei.
Toate acestea fac parte din
paradigma SRTBOT -
amintiți-vă, subprobleme,
relații, ordine topologică,
caz de bază,
problemă originală și timp.
Aici sunt subprobleme
și relații.
Am scris atât
care sunt aceste lucruri, cât și
lecțiile cheie pe care le-am primit de la
prima prelegere de programare dinamică
.
Și anume, dorim să ne împărțim
problema în mai multe
subprobleme, iar dacă
introducerea dvs. este o secvență --
acesta este cazul principal pe care l-am
văzut până acum --
cum ar fi
problema bowlingului, de exemplu,
atunci
subproblemele naturale de încercat
sunt prefixele  , sufixe
sau subșiruri.
Prefixele și sufixele sunt drăguțe,
pentru că sunt puține.
Există doar un
număr liniar dintre ele.
În general, dorim
un număr polinom.
Uneori poți
scăpa cu unul dintre acestea.  De
obicei sunt cam la fel.
Uneori aveți nevoie de subșiruri.
Există în mod pătratic
multe dintre acestea.
Apoi, odată ce ați configurat
subproblemele, care --
este ușor să
configurați unele probleme,
dar greu să o faceți corect -- pentru a
testa dacă ați
făcut-o corect,
pot scrie o
relație de recurență
care să relaționeze o
soluție de subproblemă cu o soluție mai mică.
solutii subprobleme?
Și
trucul general pentru a face acest lucru
este să identificați o anumită caracteristică
a soluției pe care o
căutați.
Deci încerci să
rezolvi o subproblemă
și încerci să pui o întrebare
al cărei răspuns te-ar permite să
reducă la o subproblemă mai mică.
Deci, dacă vă puteți da seama
care este acea întrebare
și acea întrebare are doar un
număr polinom de răspunsuri,
atunci boom-- și
aveți doar un număr polinom
de subprobleme, atunci veți
obține un timp de rulare polinomial.
Așa că am, cred, un
alt mod de a spune asta.
Pur și simplu
forțăm la nivel local toate răspunsurile posibile
la orice întrebare cu care
venim,
atâta timp cât sunt
multe polinomiale.
Și apoi fiecare dintre ei va
apela recursiv subproblemele mai mici
, dar
pentru că memorizăm,
vom rezolva
fiecare subproblemă o singură dată.
Și așa mai departe,
timpul de rulare
va fi, cel mult,
numărul de subprobleme
înmulțit cu
munca nerecursivă efectuată în acea relație.
Pentru ca acest lucru să funcționeze, desigur,
relațiile dintre subprobleme
trebuie să fie aciclice, așa că
am dori să dăm
o ordine topologică explicită.
De obicei, sunt
câteva bucle for.
Dar aceasta este o
ordine topologică în subproblema
DAG, pe care am definit-o oarecum
informal data trecută.
cel.
Vârfurile sunt
subprobleme și vreau
să trag o margine de la o problemă mai mică
la o problemă mai mare, ceea
ce înseamnă că, dacă evaluarea lui
b în această relație numește a,
atunci voi desena o
săgeată de la a la b,
din lucrurile pe care trebuie să le
fac.  face mai întâi lucrurile pe care le
voi face mai târziu.
Deci
ordinea topologică va fi
gata - până când
voi încerca să calculez b,
voi fi calculat deja a.
Și, desigur, relația are
nevoie și de cazuri de bază.
Și atunci, uneori,
problema inițială pe care vrem să o rezolvăm
este doar una dintre
acele subprobleme.
Uneori trebuie
să combinăm mai multe.
Vom vedea asta astăzi.
Deci, aceasta este o revizuire
a acestui cadru.
Și să ne aruncăm în cea
mai lungă secvență comună.
Aceasta este o
problemă clasică.  Are
chiar
aplicații la lucruri
precum biologia computațională.
Ai două secvențe de ADN.
Vrei să măsori
cât de comune sunt.
O versiune a acesteia -- s-
ar putea vedea alte
versiuni în recitare --
numită distanță de editare -- aceasta este
cea mai simplă și mai curată versiune,
în care vă dau două secvențe --
Am un exemplu aici.
Deci, de exemplu, ar putea
fi o succesiune de litere.
Deci prima mea secvență
vrăjește hieroglifologia -
studiul hieroglifelor.
Și a doua secvență îl
vrăjește pe Michelangelo.
Și ce mi-aș dori
este o succesiune.
Deci, amintiți-vă, subșirul trebuie să
fie un interval continuu,
un interval.
Subsecvență--
puteți lua orice subset
de litere din
secvența dvs. sau orice subset
de elemente din secvența dvs.
Deci, puteți avea
spații libere între ele.
Puteți sări peste articole.
Și deci ceea ce ne dorim este cea
mai lungă secvență
care este o subsecvență
atât a primului șir,
a primei secvențe,
cât și a celui de-al doilea șir.
Și dacă te uiți la
asta suficient de lung, cea
mai lungă secvență comună...
Nu cred că este
unică, dar
există o secvență comună cea mai lungă,
care se ascunde acolo.
Și aceasta este cea mai lungă
secvență comună.
Deci, având în vedere acea intrare,
scopul este să calculăm salut,
sau oricare ar fi cea mai lungă
subsecvență comună.
Așa că ni s-au dat... scrieți
asta cu atenție...
două secvențe.
Permiteți-mi să le numesc
A și B. Vrem
să găsim cea mai lungă
secvență L care este
o subsecvență atât A cât și B. Deci
aceasta este definiția problemei
și vom
vedea cum să
o rezolvăm folosind programarea dinamică.
Și în timp ce, în
problema bowling-ului,
am avut doar o singură
secvență de numere--
valorile pinurilor de bowling--
aici avem două secvențe.
Și deci avem nevoie de un nou truc.
Înainte, am spus, OK, dacă
subproblemele noastre -- sau scuze --
dacă intrarea noastră constă
dintr-o singură secvență,
vom încerca prefixe,
sufixe sau subșiruri.
Acum avem două
secvențe, așa că într-un fel
trebuie să combinăm mai multe
intrări împreună.
Și iată un truc general -
subprobleme pentru intrări multiple.
Este un truc foarte simplu.
Luăm doar produsul,
înmulțim spațiile subproblemei.
BINE.
În sensul produsului încrucișat
al mulțimilor și, în special,
dintr-o perspectivă combinatorie,

deci avem două intrări,
prima secvență
A și a doua secvență
B. Pentru fiecare dintre ele,
există o alegere naturală sau
există trei opțiuni naturale  .
Am putea face una dintre acestea.
Voi alege sufixe
pentru A și sufixe pentru B.
Ai putea face o
altă combinație,
dar asta ar fi
suficient pentru aici.
Și apoi vreau să
înmulțesc aceste spații,
adică numărul
de subprobleme
va fi produsul
dintre numărul de sufixe de
aici cu numărul
de sufixe de aici.
Și cu alte cuvinte,
fiecare subproblemă din LCS
va fi o
pereche de sufixe.
Așa că lasă-mă să scriu asta.
Deci, pentru LCS,
subproblemele noastre sunt L din i, j--
aceasta va fi cea
mai lungă subsecvență comună--
a sufixului lui A începând
de la i și a sufixului lui B
începând de la j.
Și doar pentru a fi clar
câți sunt,
voi da
intervalele pentru i și j --
nu voi presupune că
secvențele
au aceeași lungime,
ca în exemplu.
Deci voi scrie lungimile lui
A și lungimile lui B. Îmi place
să includ sufixul gol.
Deci, atunci când j este egal cu lungimea
lui B, înseamnă 0 elemente,
pentru că asta face
cazuri de bază foarte ușoare.
Așa că aș dori să
le includ în problemele mele.
Deci acesta a fost S în SRTBOT.
Acum susțin că setați subprobleme
este suficient pentru a face o relație--
relație recursivă între ele.
Așa că aș dori să rezolv
toate subproblemele L i, j.
Relația este de fapt
destul de simplă,
dar poate nu este atât de evidentă.
Deci ideea este că, pentru că ne
uităm la sufixe,
ar trebui să ne
gândim întotdeauna la ce
se întâmplă în prima
literă, pentru că dacă
eliminăm prima literă,
atunci obținem un sufix mai mic.
Dacă faci prefixe,
ar trebui să te
uiți întotdeauna la ultima literă.
Oricare ar funcționa
pentru această problemă.
Deci facem sufixe.
Deci ne uităm la A din i
și ne uităm la B din j.
Aceasta este prima literă din
sufixul A care începe cu i
și sufixul B care începe cu j.
Și sunt două cazuri.
Ele pot fi
egale sau diferite.
Cred că cel mai ușor
caz la care să te gândești este
atunci când sunt diferiți.
Deci, ca în hieroglifologie
și Michelangelo,
dacă ne uităm la întregul
șir, să zicem, prima literă
din partea de sus este H. Prima
literă din a doua
este M. Sunt
litere diferite,
așa că în mod clar, una dintre
acele litere este  nu
în subsecvența comună,
pentru că nu se potrivesc.
Nu pot începe cu un H.
Ei bine, pot începe cu un H, aș
putea începe cu un M,
dar nu pot începe cu ambele.
Una dintre aceste litere
nu este în ieșire.
În acest exemplu, este M.
Dar nu știu care,
așa că am această întrebare.
Vreau să identific
o întrebare.
Și întrebarea este, ar trebui să--
știu că H
nu este în răspuns sau
știu că M
nu este în răspuns-- cea
mai lungă
secvență comună finală?
Nu știm care,
așa că le vom încerca pe amândouă.
Și apoi
încercăm să maximizăm
lungimea
subsecvenței noastre comune,
așa că vom lua maximul de L i
plus 1 j și L i, j minus 1.
Deci intuiția
de aici este una dintre--
cel puțin una dintre Ai  iar
Bj nu este în LCS.  Am înțeles
greșit.
j plus 1-- scuze--
mă gândesc
deja la subșiruri.
Da.
Acestea sunt punctele de început,
deci vreau să exclud litera i-a -
deci dacă Ai nu este în, atunci
vreau să mă uit la sufixul care
începe cu i plus 1.
Dacă Bj nu este în, atunci
vreau să mă uit la  sufixul
începând de la j plus 1.
Deci indicii sunt
mereu crescători
în apelurile de funcții.
Și celălalt caz este
că sunt egali.
Așa că pe acesta mă
cert mai greu.
Voi scrie
răspunsul, apoi voi demonstra
că răspunsul este corect.
Aici susțin că nu
trebuie să faci nicio alegere.
Nu există nicio întrebare la care
trebuie să răspunzi.
De fapt, puteți
garanta că Ai și Bj
ar putea fi la fel de bine în cea
mai lungă succesiune comună.
Și așa primesc un punct pentru
asta și apoi recurg
la toate literele rămase -
deci de la i plus 1
și de la j plus 1.
De ce este în regulă?  Ei
bine, avem A, B.
Începem de la poziția i
și pornind de la
poziția j pentru B.
Gândiți-vă la o
soluție optimă, la o
subsecvență comună cea mai lungă.
Deci, împerechează
litere într-un fel.
Aceasta ar fi o
pereche neîncrucișată între litere egale.
Deci, primul caz este
că poate i și j
nu sunt asociate cu nimic.  Ei
bine, asta e o prostie,
pentru că dacă nu sunt
asociate cu nimic,
ai o anumită legătură
cu restul articolelor.
Puteți adăuga această pereche și aceasta
ar fi o succesiune mai lungă.
Deci asta ar fi
o contradicție.
Dacă luăm... ne imaginăm o
soluție optimă ipotetică,
trebuie să asociați una dintre
acestea cu ceva.
Poate că mă împerechează cu
altceva, totuși.  Ei
bine, dacă avem o
subsecvență comună cea mai lungă
care arată așa, pot
doar să împerechez i cu Bj.
Dacă am avut această pereche,
de fapt nu folosesc niciuna
dintre aceste litere, așa că de ce nu
folosesc această literă în schimb?
Așa că puteți argumenta că există cea
mai lungă secvență comună care
se potrivește Ai cu
Bj, și astfel
putem garanta prin
această mică dovadă
că obținem un punct
pentru potrivirea lor -
că nu trebuie să
maximizăm acest lucru cu nimic.
OK, deci două cazuri... o
formulă destul de simplă.
Și apoi am terminat.
Trebuie doar să completăm
restul SRTBOT.
Deci următoarea este ordinea topologică.
Deci asta voi scrie ca pentru bucle.
Deoarece am de-a face
cu sufixe,
vrem să începem cu
sufixele goale
și apoi să mergem spre
sufixe din ce în ce mai mari.
Deci asta ar putea părea invers.
Dacă faci prefixe,
ar fi o ordine în creștere.
Sunt tot felul de comenzi.
Ai putea răsturna i și j.
Este foarte simetric, deci
nu prea contează.
Dar orice este în general în
scădere i și j este bun.
Apoi avem cazuri de bază.
Acestea sunt atunci când una dintre
secvențe este goală.
Nu-mi pasă câte elemente sunt
în B, dar dacă A nu are elemente,
nu există o succesiune comună.
E gol.
Și la fel pentru
cât de mare este A,
dacă am epuizat
șirul B --
încep de la
ultimul element --
atunci ar trebui să obțin 0.
Atunci problema inițială pe care
vrem să o rezolvăm este L 0, 0 --
asta este  doar cea
mai lungă secvență comună
a întregului A
și a întregului B--
și timp.
OK, deci pentru timp, trebuie să știm
câte subprobleme există.
Este A plus 1 ori B plus 1. Îl voi
numi doar theta
A, B. Să presupunem că acestea nu sunt
subsecvențe goale.
Deci acesta este numărul
de subprobleme.
Și atunci ceea ce ne pasă
este, cât timp
petrecem pentru fiecare subproblemă
evaluând această
relație de recurență?
Deci ignorăm costul
de a numi recursiv
aceste L, deoarece
sunt subprobleme mai mici.  S-au
rezolvat deja
când înmulțesc
cu numărul de subprobleme.
Așa că îmi pasă doar de acest
calcul maxim și de această
verificare a egalității și le vom spune
fiecare cost constant timp.
Deci acesta este timpul patratic.
Dacă cele două șiruri au
dimensiunea n, acesta este n pătrat.
În general, este produsul celor
două mărimi de șir.
Și acesta este cel mai lung
subșir comun --
atât de simplu.
În afară de acest mic
argument pentru a înțelege
cazul când sunt
egali, cazul ușor în care
sunt inegale, încercăm doar
singurele două lucruri pe care le-am putea face.
Unul dintre Ai și Bj nu este în cea
mai lungă subsecvență comună,
așa că ceea ce îmi place să spun este că
ghicim care dintre acestea
este cea corectă care
nu este în cea mai lungă
subsecvență comună.
Și dacă ghicim că
este în A, atunci vom
recurge pe acea parte.
Dacă ghicim că este în
j, atunci vom recurge la -
prin creșterea j.  Aș
vrea să presupun --
nu chiar -- că întotdeauna
facem presupunerea corectă,
că am făcut
alegerea corectă, indiferent dacă este i sau j.
Acum, de fapt, nu
știm cum să facem asta,
așa că, în schimb, folosim forța brută.  Le
încercăm pe amândouă și
apoi, pentru că încercăm
să maximizăm, luăm maximul...
doar un alt mod de a
gândi.
Dar, în general, foarte
simplu -- singura
complicație adăugată aici este că a
trebuit să ne ocupăm de două secvențe
simultan și
doar am luat produsul
acestora -- destul de ușor.
În general, dacă aveți un
număr constant de secvențe,
vă puteți permite să faceți acest lucru.
Veți obține în continuare polinom.
Dar, desigur, odată ce
treci la n secvențe,
nu-ți poți permite asta.  Ai
face un comportament n la
n,
deci aceasta este o limită pentru
cât de departe ai putea merge.
Două secvențe sunt
bine, trei secvențe
sunt bine, dar n secvențe -
probabil că nu există un
algoritm de timp polinomial
pentru această problemă.
Cool... vreau să-
ți arăt un exemplu.
Am un exemplu aici.
Nu am vrut să
încerc hieroglifologia
versus Michelangelo, așa că am
venit cu un alt exemplu.
Obiceiul lor este să spună salut.
Deci cea mai lungă
secvență comună de acolo și obicei
este HI.
Și este un gigant... ei
bine, nu acel uriaș... arată un fel
ca un grafic grilă.
Cazurile de bază sunt aici,
deoarece acestea corespund -
fiecare dintre aceste noduri
este o subproblemă
și aceasta corespunde cu care este cea
mai lungă subsecvență comună
dintre EIR și ABIT?
Și ar trebui să fie I. Este
singura literă pe care o au
în comun și de
aceea există un 1 aici
pentru a spune că cea mai lungă
subsecvență comună are
un 1-- are dimensiunea 1.
Cazurile de bază sunt atunci când
fie lor a fost golită,
fie când  obiceiul a fost
golit, așa că toate au 0
pe exterior.
Și atunci problema de care ne
pasă este aceasta.
Este vorba despre obiceiul lor.
Pretenția este că lungimea este 2.
Și ceea ce am desenat aici sunt
ceea ce voi numi indicatori părinte,
așa cum am vorbit cu BFS,
și cele mai scurte căi și așa mai departe.
Deci am avut această alegere -
uneori aveam de ales -
dacă am recurs
aici sau am recurs aici
a fost cel mai bun lucru de făcut.
Voi desena cu roșu săgeata
de la L i, j-- scuze-- la L
i, j de la unul dintre
acestea în acest caz.
Și în acest caz,
nu a fost de ales,
dar tot voi desena
cu roșu acea săgeată.
Deci aceste margini diagonale
sunt exact cazurile în care
literele se potrivesc.
Aici H este egal cu H.
I este egal cu I aici,
așa că desenez această margine diagonală.
Acesta este primul caz,
în care literele sunt egale,
așa că recurg prin
creșterea i și j.  De
aceea primesc
o margine diagonală.
Există, de asemenea, unul
aici, unde T este egal cu T.
Deci, pentru aceștia,
obținem un plus 1.
Vedeți că acest 1 este cu 1
mai mare decât 0. Acest
2 este cu 1 mai mare decât 1.
Acest 1 este unul mai mare decât 0.
Și pentru fiecare alt
vârf, repetăm ​​în
acest fel și în felul acesta.
Vedem care sunt acele două numere
și luăm max.
Deci întreaga diagramă
este doar completată de...
pentru fiecare poziție,
unde nu sunt egale.  Ne
uităm la tipul de mai jos.
Ne uităm la tipul din dreapta.
Acestea sunt
subșirurile puțin mai mici.  Ne
uităm la acele valori.
Luăm max.
Atâta timp cât calculezi
acest lucru într-un mod în general de la
dreapta la stânga și de jos în sus
, ori de câte ori
încerci să calculezi
un tip, vei
avea
deja calculați predecesorii săi.
Aceasta este
ordinea topologică a acestui grafic.
Și apoi, la sfârșit,
obținem răspunsul nostru, care este 2.
Și acum, dacă acordăm atenție
de unde venim --
de exemplu, acest vârf
trebuia să vină din această direcție --
2 este maximul de 2 și  1,
așa că evidențiez marginea 2.
Și dacă urmez această cale, ar
trebui să existe o cale unică
către un caz de bază.
Nu știm care.
Și în acest caz,
marginile diagonale
corespund
literelor mele potrivite.
Deci aici este H,
urmat de I aici.
Și astfel HI este cel mai lung
subșir comun al nostru.
În general,
urmăm acești indicatori
înapoi - indicatorii roșii -
și obținem răspunsul nostru.
Deci nu numai că calculăm
lungimea LCS,
dar de fapt putem găsi
LCS folosind pointerii părinte.
Și acesta este un concept pe care îl puteți
utiliza în majoritatea programelor dinamice,
inclusiv în toate cele
de astăzi.
OK, aveți întrebări despre LCS?  În
regulă... perfect clar
pentru toată lumea din audiență.
Acum trecem la cea mai lungă
secvență în creștere, care... am
pierdut o pagină aici?
Pur și simplu le-am dezordonat.
OK, această problemă are
aproape același nume,
dar este destul de diferită
și comportament --
cea mai lungă succesiune în creștere --
LIS, în loc de LCS --
ambele probleme celebre, exemple
de programare dinamică.
Aici ni se oferă doar o
secvență, cum ar fi carbohidrații.
Deci aceasta este o
secvență de litere
și vreau să găsesc cea mai lungă
subsecvență a acestei secvențe
care crește --
strict crescând, să
spunem -- deci în acest
caz, alfabetic.
Aș putea include CR, de
exemplu, dar nu CB.
Asta ar fi o
succesiune descendentă.
În acest exemplu,
răspunsul corect
sau un răspuns corect este anularea.
Nu sunt foarte multe
cuvinte în engleză care să crească,
dar sunt unele și le-am
căutat pe toate.  Pe măsură
ce tocmai am implementat
acest program dinamic pe care urmează să-l
notăm,
mi-a luat vreo două minute
să notez
DP și apoi mai multă
muncă pentru a citi dicționarul
și a căuta exemple interesante.
Deci, în general, ni se
dă o secvență A
și dorim să găsim cea mai lungă
secvență crescătoare a lui A - cea
mai lungă secvență care
crește, strict.
Am putea folosi același lucru pentru a
rezolva nu strict creșterea,
dar...
așa că aici lucrurile vor
fi puțin mai complicate.
Este ușor, prin faptul că avem doar
o singură secvență.
Deci, din nou, ne gândim, OK, să ne
uităm la diagrama noastră aici.
Am putea încerca prefixe,
sufixe sau subșiruri.
Eu personal prefer sufixele.
Jason preferă prefixele.
Orice preferi este bine, dar
întotdeauna, în general, începeți de acolo,
pentru că nu există nimic
în această problemă care să
mă facă să cred că trebuie să
șterg lucrurile de la ambele capete.
PUBLIC: Am o întrebare.
ERIK DEMAINE: Da... întrebare?
PUBLIC: Răspunsul
la această problemă nu este întotdeauna 26?
ERIK DEMAINE: Răspunsul este
întotdeauna, cel mult, 26 de ani?
Da, dacă ai de-a face
cu cuvinte englezești,
deci când spun secvență aici,
aceasta este o secvență de
numere întregi arbitrare -
numere întregi de mărimea cuvintelor.
Deci acolo puteți avea
o mulțime de varietate.
Acesta este doar pentru distracția
exemplelor, am desenat asta.
Dar chiar dacă răspunsul este
26, găsirea celei mai lungi
subsecvențe comune este--
algoritmul evident ar fi
să luăm toate subșirurile de dimensiunea
26, care este n la 26.
Vom face mult
mai repede decât atât aici.
N timp la pătrat.
Și apoi, dacă eliminați
strict creșterea,
atunci poate fi
arbitrar de mare.
OK, deci hai să încercăm să facem asta.
Poate că nu voi fi atât de pesimist
să încerc să scriu aici.
Să mergem doar pentru asta.
Așa că vreau niște subprobleme și o să
aleg sufixe.
Deci, voi defini L din i
ca fiind cea mai lungă
subsecvență crescătoare a sufixului lui
A începând cu i.
Acesta este lucrul evident de făcut.
Și acum o să-
mi las puțin spațiu
și apoi aș dori o
relație pe acestea.
Așa că aș vrea să spun
ce este L din i.
Și cu ce trebuie să lucrez?  Ei
bine, am
lucruri vii mai mari decât mine.
Acestea ar fi sufixe mai mici.
Dar să revenim la, care
este o întrebare pe care aș putea să o
pun despre această subproblemă
care m-ar putea ajuta să îmi dau seama
cum arată cea mai lungă
subsecvență care crește?
Deci ne uităm la un...
iată A de la început.
Cea mai lungă subsecvență în creștere
este o anumită subsecvență.
Și am dori să
eliminăm litera i.
Acum, când facem asta,
există două opțiuni.
Poate că i se află în cea mai lungă
subsecvență crescătoare,
sau nu este în.
Deci întrebarea la care aș
dori să răspund
este: i se află în cea mai lungă
subsecvență crescătoare a lui A--
a lui A de la i încolo?
Aceasta este o întrebare binară.
Există două opțiuni,
așa că din nou, la fel ca înainte.
Și astfel pot
forța brută cele două opțiuni.
Și apoi o vreau pe cea mai lungă,
așa că o să iau maxim.
Așa că aș dori să iau maximul
a ceva de genul Li plus 1.
Deci, în cazul în care nu pun
i în soluție, este în regulă.
Apoi mă uit doar la i plus 1 pe
și calculez recursiv asta,
iar acesta ar fi răspunsul meu.
Și cealaltă
opțiune este că
pun i în cea mai lungă
secvență crescătoare, deci fac 1
plus restul L i plus 1.
Dacă închid această
breteză, aceasta ar
fi o recurență foarte ciudată,
deoarece aceasta este întotdeauna
mai mare decât aceasta.  .
E ceva în neregulă
aici, iar ceva în neregulă
este că nu am impus
deloc creșterea.
Nu există constrângeri aici.
Spune doar, ei bine, voi
pune, apoi voi face
tot ce rămâne, și mă voi
ruga ca asta să crească -
probabil că nu va fi, pentru că
într-adevăr, dacă i este o scrisoare -
sau este  un număr care este
strict mai mare decât i plus 1,
atunci acest lucru va fi greșit.
Deci chiar nu pot
face asta întotdeauna.
Aș putea verifica dacă i plus
1 sunt în răspuns, dar unii--
dar nu.
Pot verifica dacă litera
i este mai mică decât litera i plus 1.
Dar poate am pus asta în cea
mai lungă subsecvență crescătoare
și apoi am pus aceasta în cea
mai lungă subsecvență crescătoare,
așa că trebuie să
compar aceste două elemente.
Dar nu știu când se va
întâmpla asta.
Lucrurile par foarte grele.
Și într-adevăr, nu există nicio modalitate,
din definiția acestei subprobleme,
de a scrie o relație.
Dar există o ușoară
modificare a acestei definiții
care o face să funcționeze.
Deci problema pe care o avem
aici - și aceasta este ideea
constrângerilor
sau condițiilor subproblemei -
problema pe care o avem
este că, atunci când
calculăm recursiv cea mai lungă
subsecvență în creștere pe restul,
nu cunoaștem primul
element din acel răspuns.
Poate sunt eu plus 1.
Poate e vreun tip de aici.
Dacă am ști cine
este, atunci am putea
compara acel articol cu ​​articolul i.
Și, așadar, ceea ce ne-am dori să
facem este să adăugăm o constrângere
subproblemei care
ne lasă cumva să știm unde începe cea mai lungă
subsecvență care crește.
Deci ceea ce aș dori să spun este
lung ca subsecvență crescătoare
a acelui sufix care
începe cu A din i.
Deci, cu alte cuvinte,
include A din i.
Aceasta a fost o întrebare separată.
OK, aceasta este o
constrângere puțin amuzantă.
Schimbă problema.
Nu mai este ceea ce
vrem să rezolvăm.
Dacă vă gândiți la
problema inițială,
înainte, aceasta a fost rezolvarea L de 0.
Vrem doar cea mai lungă
succesiune crescătoare
a întregului lucru.
Acum nu este neapărat L de 0.
L de 0 înseamnă, care este cea
mai lungă subsecvență crescătoare
a întregii secvențe A care
include prima literă a lui A?
Și poate includem
prima literă a lui A,
poate nu știm, nu
știm unde începe cea mai lungă
secvență crescătoare.
Aici, de exemplu, nu a fost.  A
început la a doua scrisoare.
Dar convenabil, este în
regulă că nu știm,
pentru că aceasta este doar o
altă întrebare pe care ne-am putea
pune este, de unde începem?  De
unde ar putea începe LIS-ul?
Ar putea începe cu prima
literă, a doua literă, a
treia literă - există
doar n opțiuni
și să luăm
maximul tuturor.
Deci, înainte de a ajunge la relație, să
rezolvăm această problemă.
Vreau doar maximul
de L din i pentru tot i.
Cred că am
scris dimensiunea A aici.
OK, maximul va
fi cea mai lungă
secvență de creștere generală.
Deci, dacă aș putea găsi cea mai lungă
subsecvență crescătoare care
include prima literă, sau cea
mai lungă care include a
doua literă și așa mai departe -
deci începe cu
prima literă,
începe cu a doua
literă - atunci acest maxim
va fi  cel mai lung total.
Această subproblemă nu este
ceea ce mi-am dorit cu adevărat,
dar este totuși
suficient de bună, pentru că îmi permite să-mi
rezolv problema inițială.
Și asta adaugă o
constrângere suplimentară problemei mele.
Și a face asta este o provocare.  Să
te gândești la ce
constrângere corectă care te-ar permite să-ți
rezolvi problema este dificil,
mai ales la început.
Dar deocamdată, să considerăm
asta ca pe un lucru care funcționează.
De ce funcționează?
Pentru că acum pot spune-- ei
bine, acest termen a fost bine, max--
așa că încerc să scriu cea mai lungă
secvență crescătoare, începând
cu litera i-a, versus--
da, de fapt, nu.
Acest lucru va
fi diferit.
OK, deci acum ajung la
problema centrală, care este că
știu, prin definiția lui L
din i, că includ litera i.
Aceasta va fi în cea
mai lungă succesiune a mea în creștere.
Asta
caut, aceasta definitie.
Dar nu știu care
este a doua literă -
ar putea fi i plus 1,
ar putea fi i plus 2,
ar putea fi ceva mai mare.
Ori de câte ori există
ceva ce nu știu,
îl voi forța pur și simplu.
Nu-mi pasă că nu știu.
Voi lua un maxim peste
toate alegerile posibile.
Să presupunem că următoarea
literă inclusă în cea mai lungă
secvență crescătoare i este j.
Apoi aș vrea
să mă uit la L din j.
Acum, nu știu ce este j,
dar voi folosi forța brută
toate opțiunile posibile pentru j.
Deci, acesta va fi
i strict mai mic decât j,
pentru că nu vreau să includ din
nou aceeași literă i.
Și altfel, aș obține
o buclă recursivă infinită,
dacă aș pune mai puțin
sau egal cu aici.
Și poate nu-i fac
altceva lui n.
OK, nu gata--
acum-- aceasta este
partea interesantă--
Pot impune creșterea,
pentru că nu pot alege
orice litera j la dreapta lui i.
De asemenea, numărul sau litera
care este scrisă aici
trebuie să fie mai mare decât
numărul care este scris aici.
Aceasta este
proprietatea în creștere strictă.
Deci, pot adăuga ca o constrângere
în acest max pentru a spune A din i
sunt strict mai mici decât A din j.
Și dacă ai vrea să
nu crească strict,
ai adăuga un egal acolo.
Aceasta este notație matematică.
În Python, ați spune
parente maxim deschis al acestui lucru pentru j
în acest interval, dacă este valabil.
Așa că fac doar
bucla for, dar fac doar...
Mă uit doar la
opțiunile posibile pentru j
atunci când este
valabilă proprietatea strict crescătoare.
Și apoi, când asta e
valabil, pun... verific asta.
Acum, acest set ar putea fi gol.
Trebuie să definesc care
este valoarea maximă când este gol.
Oh, am nevoie și de un
plus 1, nu-i așa?
Lasă-mă să fac doar 1 plus.
Așa că ni se spune că i este în
răspuns, deci obținem întotdeauna 1.
Și apoi restul
este acesta sau 0.
Dacă nu există Aj
mai mari decât Ai,
atunci vom fi implicit la 0 și vom
spune că i este singurul  element
în succesiunea mea crescătoare.
OK, deci sunt câteva
detalii de corectat,
dar, în general, odată ce vă dați seama cum
arată aceste recidive
, sunt foarte simple.
Aceasta este o linie de cod, iar
apoi tot ce aveți nevoie în plus față
de aceasta este
subproblema originală
și alte câteva lucruri.
Avem nevoie de cazurile de bază, dar ar
trebui să le fac în ordine.
Ordinea topologică este
doar bucla obișnuită,
pentru că fac sufixe.  Va
fi i egal cu
lungimea lui A până la 0.
Cazul de bază va
fi L de lungimea lui
A, care este 0,
deoarece
nu există litere în acel sufix.
Și am făcut deja
O, iar apoi timpul...
este puțin diferit
de exemplele trecute.
Deci numărul de subprobleme, la fel
ca de obicei,
este lungimea liniară
a subproblemelor A.
Este o singură secvență la care ne
gândim acum,
spre deosebire de exemplul anterior.
Dar munca pe care o
facem în această relație
acum este o muncă netrivială.
Înainte doar ghicim
între două opțiuni diferite.
Acum ghicim între până
la n opțiuni diferite.
Acest n aici este lungimea lui A.
Și astfel avem
lungimea teta a lui A,
lucru nerecursiv pe care îl
facem în fiecare subproblemă.
Sau ați putea crede că acestea sunt
alegeri pe care le luăm în considerare.
Și pentru fiecare alegere,
doar cheltuim...
Adică, luăm un număr
maxim de articole, adăugând 1.
Deci, aceasta este o suprasarcină constantă.
Și deci primim acest
produs, care este A pătrat--
cool.
Deci aceasta este cea mai lungă
secvență de creștere.
Asigurați-vă că nu am
ratat nimic altceva,
așa că folosim ideea
de a pune o întrebare
și de a ghici sau de a
forța răspunsul
la acea întrebare în două locuri.
Un loc este că
promitem--
cerem ca subsecvența cea mai lungă
crescătoare să înceapă
la i, așa că
întrebarea este, ei bine,
care este chiar al
doilea element care se află
în subsecvența cea mai lungă crescătoare
care începe cu i?
Numim asta
j și forțăm brutal
toate
alegerile posibile care ar putea fi j,
ceea ce
ne permite să verificăm, să
confirmăm că este de fapt o
subsecvență crescândă la nivel local
de la i la j.
Și apoi L din j se va
ocupa de restul.
Prin inducție, restul celei
mai lungi creșteri
a subsecvenței începând de la
j va crește și el.
Și astfel, aceasta garantează, prin
inducție, că totul
va crește.
Apoi folosim și această
forță brută locală
pentru a rezolva problema inițială.
Așa că am adăugat această constrângere
de a începe de la i,
dar nu știam de fapt de
unde să începem.
Dar asta e în regulă, pentru că
există doar opțiuni A.
Așa că ar trebui să menționez, în
analiza timpului de rulare,
așa că rezolvă
subproblemele.
Este în regulă, dar
apoi există și
un plus, indiferent de cost, pentru a
rezolva problema inițială.
Dar este in regula.
Aceasta este lungimea lui A.
Toate acestea plus lungimea lui A
sunt încă lungimea lui A la pătrat.
Dar dacă faci o
muncă exponențială aici, ar fi rău.
Trebuie să facem o
cantitate rezonabilă de muncă
pentru a rezolva problema inițială
în ceea ce privește toate subproblemele.
Am un exemplu ascuns aici.
Este puțin mai
greu de privit.
Aici am empatie.
Și acest exemplu nu este...
nu are prea multă empatie,
pentru că cea mai lungă
succesiune a empatiei
este goală.
Gol este unul dintre puținele
cuvinte englezești care crește.
Iar partea grea aici
este tragerea DAG.
Este aproape
graficul complet, dar desenăm doar
margini de la litere mai mici
la litere mai mari.
Deci tragem de la E
la M, de la E la P,
de la E nu la A-- nu există
margine de la E la A-- de la E
la T, nu de la E la H, dar
da de la E la Y.
Și apoi noi  de asemenea, trageți
de la E la
cazul de bază, adică
nu mai există litere.
Acea margine a cazului de bază este --
corespunde acestui 0, sau
cred că acest n, unde spunem,
oh, să recurgem doar.
Să aruncăm -
de fapt, poate că nu avem nevoie de
uniunea 0 acolo, de fapt,
pentru că includem L din n,
care este subșirul gol.
Atunci definiția lui
L este puțin amuzantă.
Ce înseamnă să spui că
începi cu A din n?
Hm?
PUBLIC: Dacă definim A din n.
ERIK DEMAINE: Corect,
A din n nu este definit,
deci nu e chiar atât de frumos.
Deci poate repara asta.
n este egal cu majuscule.
Bine, dar tot o să
trag o margine
acolo -- spun conceptual, oh,
tocmai am terminat în acel moment.
Acesta este cazul de bază, în care
nu mai avem nici un șir --
cool.
Și când am spus de la până la de
fapt, am vrut să spun invers.
Toate marginile merg
de la dreapta la stânga.
Și atunci ceea ce facem
este să căutăm cea mai lungă
cale în acest DAG.
Cea mai lungă cale este poate o problemă
despre care am vorbit în
sesiunea cu probleme, pentru că este un DAG -- ei
bine, cea mai lungă cale este
același lucru cu cea mai scurtă cale,
dacă doar anulați
toate ponderile.
Nu există greutăți
în această imagine,
așa că dacă puneți doar negativul
1 pe toate aceste margini
și cereți cea mai scurtă cale
de la bază până oriunde -
deci cele mai scurte
căi de la această bază cu o singură sursă -
atunci am ajunge să
obținem această cale  , care,
dacă te uiți la el,
este E-M-P-T-Y, gol.
Și astfel că cea mai scurtă cale
este într-adevăr răspunsul corect.
Ceea ce am desenat aici este
arborele cu calea cea mai scurtă.  La fel, de
asemenea, dacă ați vrut cea
mai lungă subsecvență crescătoare
începând cu A, atunci este
A-T-Y, doar urmând
săgețile roșii de aici.
Și cum obții asta?
Doar desenați
indicatoarele părinte, la fel
cum am făcut înainte.
Nu am menționat, dar
acest exemplu poate
fi rezolvat și cu cele mai scurte căi.
Odată ce am construit acest grafic,
poți face calea cea mai scurtă
de la o bază--
nu știu care--
până aici.
Dacă puneți negativ 1 pe
toate marginile diagonale
și puneți greutatea
0 peste tot,
atunci aceasta corespunde cu --
calea cea mai scurtă
din acel grafic va
corespunde cu cea mai lungă --
calea cu cele
mai multe margini diagonale.
Și asta are sens, deoarece
diagonala este locul în care
obținem de fapt literele în comun.
Și, în acest caz, este 2.
Deci, ambele aceste
programe dinamice ar putea, în schimb, în
loc să le scrieți
ca un lucru recursiv
cu memorare sau să
le scrieți de jos în sus ca buclă for
și apoi să faceți
calculul, ați
putea construi
un  grafic și apoi
rulați DAG cele mai scurte căi pe el.
Dar ideea este că acestea
sunt același lucru.
De fapt, este mult
mai simplu să scrieți codul de
programare dinamică
, deoarece este
doar o buclă for și
apoi o recurență.
Deci doar
actualizați o matrice.
Deoarece știți deja care
este ordinea topologică,
nu trebuie să scrieți o
adâncime generică pentru
algoritmul de căutare, să luați
ordinea de finisare, să
o inversați și apoi să rulați aceasta--
rulați DAG cele mai scurte căi
cu relaxare--
mult mai simplu de simplu
notează recurența,
odată ce ți-ai dat seama.
Dar sunt aceleași
în aceste exemple.
În Fibonacci, de exemplu,
nu puteți scrie Fibonacci
ca o singură sursă
problemă cu cele mai scurte căi,
dar multe DP-uri puteți scrie
ca probleme cu cele mai scurte căi -
doar o conexiune cu
lucrurile pe care le-am văzut.
Bine, ultimul exemplu,
ultima problemă pentru azi... vom
face mai multe săptămâna viitoare.
Joc alternativ cu monede -
acesta este un joc cu doi jucători.
Vom găsi
strategia optimă în acest joc.
În general, aveți
o secvență de monede,
iar noi avem doi jucători.
Ei fac pe rând.
Deci date monede de valoare de la
v0 la v n minus 1--
deci este o secvență.
Sunt date în ordine--
într-o anumită ordine-- de
exemplu, 5, 10, 100,
25-- nu neapărat
ordine sortată.
Și regulile jocului sunt că
ne vom lua pe rând.
O să fac
pe rând cu tine.  O să
folosesc eu și tu
pentru a mă referi la cei doi jucători.
Și așa, la fiecare tură, fie
unul-- oricui îi vine rândul,
eu ajung să-- putem
alege fie
prima monedă, fie ultima monedă
dintre monedele care rămân.
Deci, la început,
pot alege 5 sau 25.
Și s-ar putea să cred că,
oh, 25 e foarte bun.
Este mai bine decât 5. Ar
trebui să aleg asta.
Dar apoi, desigur, vei
merge următorul,
și vei alege
100 și vei câștiga jocul.
Veți primi mai mult din
valoarea totală a monedelor.
Deci, în acest exemplu,
o strategie mai bună
este să luați 5, pentru că atunci
100 este încă la mijloc.
Și așa că, odată ce iau 5,
poți să alegi 10 sau 25.
În acest moment,
probabil ai prefera 25,
pentru că este mai bine decât 10.
Dar orice ai alege,
pot lua 100.
Și așa am 105 de puncte,  și vei
primi 35 de puncte.
OK, un exemplu bun pentru mine.
Deci, este ușor pentru
un exemplu simplu,
dar, în general, există
exponențial multe strategii
aici.
La fiecare pas, oricare dintre noi
ar putea merge la stânga sau la dreapta -
alege este cea mai stângă
sau cea mai dreaptă.
Și vom oferi un
algoritm de programare dinamică
care rezolvă acest lucru rapid.
Nu am menționat-- deci acest
algoritm este timp pătratic,
dar poate fi făcut n log n timp.
Este un exercițiu distractiv.
Folosind o mulțime de
lucruri de mărire a structurii de date pe care le-am
făcut, puteți
face acest n log n.
Acest algoritm, cred,
va fi n timp la pătrat.
Deci nu voi corecta
problema exact,
dar cred că știți regulile.
Alegeți moneda cea mai din stânga sau cea din dreapta
, alternând mișcările.
Așa că aș dori să definesc
câteva subprobleme.
Și aceasta este o problemă care este
foarte firesc o
problemă de subșiruri.
Dacă m-aș uita doar la sufixe, s-
ar descurca foarte bine cu --
dacă șterg monede din
stânga, dar de îndată ce șterg --
și dacă șterg monede
doar din dreapta,
asta mi-ar da prefixe.
Dar vă spun acum,
nu există o programare dinamică
în care răspunsul este
sufixe și prefixe.
Puteți face sufixe sau
prefixe, dar dacă aveți nevoie de amândouă,
aproape sigur aveți nevoie de
subșir, pentru că de îndată
ce șterg prima
monedă, și apoi poate
luați a doua monedă --
asta este exact
strategia optimă aici -- acum
aveți  un
subșir arbitrar în mijloc.
Dar subșirurile sunt
suficiente, pentru că conducem doar
de la capete.
Ne vom uita la subșiruri.
Deci, mai precis -- aceasta
este doar intuiția --
vom defini
un x generic al lui i,
j va fi
valoarea maximă totală pe care o
pot obține din acest joc, dacă
îl jucăm pe monede de valoare  Vi
la Vj.
Deci, acesta este un subșir.
Deci, aceasta este o modalitate de a
scrie subproblemele
și este, de asemenea, o modalitate bună.
Ați putea scrie o
relație pe această definiție
a subproblemelor.
Dar am puțin timp.
Există două moduri de a
rezolva această problemă.
Acesta este un
mod rezonabil, exploatând faptul
că jocul este cu sumă zero.
Dar aș dori să mă schimb
puțin pentru a vă oferi,
cred, care este o modalitate mai curată
de a rezolva problema, și anume să
adăugați o a treia coordonată
la subproblemele mele.
Deci acum este parametrizat
de trei lucruri.
P aici este... are doar
două opțiuni.
Sunt eu sau tu.
Și acest lucru ajunge într-un punct
care poate nu este complet
clar din această definiție -
valoarea totală maximă pe care o pot obține
din acestea - acest subșir
de monede.
Dar nu este
evident ceea ce am nevoie.
Deci, evident, la început,
vreau întregul șir
și vreau să știu care
este valoarea mea maximă... bine.
Și eu merg primul în acest joc.
Nu am specificat, dar o fac.
[INAUDIBIL]
Dar de îndată ce fac o mișcare-- de
îndată ce iau prima monedă,
de exemplu--
acum e rândul tău.
Și așa că nu vreau să
știu valoarea totală maximă pe
care aș obține dacă merg primul.
Aș dori să spun, dacă
jucătorul P merge primul.
Aș dori foarte mult să
știu ce se întâmplă
în cazul în care mergi primul.
Așa că pentru unele
subșiruri vreau
să știu ce se întâmplă când
mergi tu primul, iar pentru unele dintre ele
vreau să știu ce se
întâmplă când merg primul,
pentru că de îndată ce fac
o mișcare, e rândul tău.
Și așa o să ne întoarcem
între P să fiu eu
și P să fii tu...
P-U.  Deci nu
trebuie să parametrizați.
Există o modalitate de a scrie
recurența altfel,
dar aceasta este, cred,
mult mai intuitivă,
pentru că acum putem face o
relație foarte simplă, care
este după cum urmează.
Așa că voi
împărți în două cazuri.
Unul este x din i, j, eu și
celălalt este x din i, j, tu.
Deci x din i, j, me--
deci am un
subșir de la i la j.  Ce as
putea sa fac?
Aș putea lua prima monedă sau
aș putea lua a doua monedă.
Ce ar trebui să fac?
Asta e întrebarea mea.
Care este prima mea mișcare?
Ar trebui să iau prima
monedă sau a doua monedă?
Deci aceasta este întrebarea mea.
Care este prima mișcare?
Există exact două
răspunsuri posibile la această întrebare,
așa că ne putem permite să
le forțăm și să luăm maximum.
Dacă ne mișcăm,
vrem numărul maxim
de puncte pe care le putem obține -
valoarea totală maximă a celor două opțiuni.
Deci, dacă iau din
partea i, partea stângă,
ar fi x sub i plus 1, j.
Îmi pare rău.
Și acum, în mod crucial,
răsturnăm jucătorii,
pentru că atunci e rândul tău.
Și dacă iau din partea j,
asta va face j minus 1.
Acesta este ceea ce am
scris accidental
la începutul prelegerii.
De asemenea, jucătorii flip.
Deci fie mă micșorez pe
partea i, fie mă micșorez pe partea j.
Oh, ar trebui să adaug aici
valoarea monedei pe care o primesc
și să adaug la valoarea
monedei pe care am luat-o.
Aceasta este o expresie
în interiorul max.
Suma aceea.
Și dacă iau maximum acele
două opțiuni, asta va da --
asta este forța mea brută locală
cea mai bună alegere dintre câte --
care este
valoarea totală a monedelor pe care le
voi obține din
restul, având în vedere că începi,
plus  această monedă pe care am luat-o
chiar acum la primul pas
și pentru cele două posibile
alegeri ce este acea monedă?
OK, ce rămâne este cum
definim acest x din i, j, tu.
Acest lucru este puțin mai amuzant,
dar este similar din punct de vedere conceptual.  O să
scriu practic
același lucru aici, dar cu mine,
în loc de tine,
pentru că din nou, se răstoarnă.
Asta înseamnă că dacă tu mergi primul, atunci
următoarea mișcare voi fi eu.
Deci aceasta este doar
formula simetrică aici.
Pot chiar să pun bretele în... până
acum, la fel.
Acum, nu pun plus Vi
și nu pun plus Vj
aici, pentru că dacă te miști,
nu primesc acele puncte.
Deci există o asimetrie
în această definiție.  L-ai
putea defini
în diferite moduri,
dar aceasta este
valoarea totală maximă
pe care aș obține-o dacă ai începe.
Deci, în prima ta mișcare,
primești câteva puncte,
dar eu nu primesc niciun
punct din asta.
Deci nu are plus Vi.
Nu are plus Vj.
Doar că fie
alegi moneda i-a, fie
alegi moneda j-a
, iar apoi monedele
care rămân pentru mine se
micșorează în consecință.
Acum, ești
un fel de durere în fund.
Ești un adversar și
încerci
să-mi minimizezi scorul
potențial pentru că
încerci să-ți maximizezi scorul.
Acesta este un joc cu sumă 0.
Deci, orice
primești, eu nu primesc.
Dacă doriți să
vă maximizați scorul,
încercați să-mi
minimizați scorul.
Acestea sunt lucruri simetrice.
Și așa că, dacă stai pe gânduri un timp,
lucrul potrivit de pus aici
este min.
Din perspectiva noastră,
ne imaginăm
care este cel mai rău caz care s-
ar putea întâmpla, indiferent de
ceea ce faci.
Și nu avem
control asupra a ceea ce faci,
așa că ne-am dori foarte mult
să vedem, ce punctaj aș
obține dacă ai alege moneda i-a?
Ce punctaj obțineți dacă
alegeți moneda j-a?
Și atunci ceea ce vom obține va
fi cea mai proastă dintre cele două
posibilități.
Deci, când ajungem să
alegem, maximizăm.
Și acesta este un
fenomen general de doi jucători
pe care, atunci când alegeți,
ajungem să-l minimizăm,
pentru că acesta este cel mai trist
lucru care ni s-ar putea întâmpla.
OK, aceasta este o modalitate de a
scrie o relație de recurență.
Avem, desigur,
tot SRTBOT de făcut,
așa că ordinea topologică
aici este în lungime crescândă
a substanței.
Deci T
crește j minus i.
Începeți cu șiruri goale.
Deci, cazul de bază este că
x din i, i, me este Vi.
Deci aici sunt incluziv la
ambele capete în această definiție.
Deci există o monedă pe care o
pot lua la sfârșit.
Dar dacă te miști ultimul și a mai
rămas o monedă,
atunci nu o înțeleg, deci este 0.
Atunci avem
problema inițială care este x i, j, me--
scuze-- x 0, n.
Acesta este întregul
set de monede, începând cu mine.
Asta era problema pe care am
vrut s-o fac.
Și apoi timpul de rulare pe care îl obținem
este numărul de subprobleme -
adică teta n pătrat, pentru că
facem subșiruri --
ori cantitatea de
muncă nerecursivă pe care o fac aici.
Este doar un maxim
de două numere.
Foarte simplu.
Timp constant.
Deci, acesta este pătratic.
Permiteți-mi să vă arăt un exemplu.
Este greu de desenat, dar
ceea ce am descris aici
se numește soluția
2 în note.
Deci, iată secvența noastră --
5, 10, 100, 25 --
în ambele direcții.
Și ceea ce ne interesează
sunt toate subșirurile.
Deci aici am
scris alegerea pentru i.
Așa că începem de la una dintre acestea,
iar dacă începi aici,
nu poți termina
mai devreme decât acolo.
Deci, de aceea ne aflăm în
diagonala superioară a acestei matrice.
Și apoi există două
versiuni ale fiecărei probleme -
versiunea albă
și versiunea albastră
chiar în jos și în
dreapta acesteia.
Dacă nu puteți vedea
ce este albastrul, aceasta
este versiunea de unde începeți.
Aceasta este versiunea de
unde încep.
Și am etichetat aici toate
numerele diferite.
Vă rugăm să admirați, pentru că a
durat mult timp pentru a desena.
Dar, în special,
avem 105 aici, ceea ce
înseamnă că
punctele maxime pe care le pot obține 105.
Și acesta este cazul pentru că,
dacă ne uităm acolo,
este maximul acestor
două valori primite
plus Vi-ul pe care îl obțin.  Așa că
fie merg la stânga și
iau acel obiect, fie cobor
și iau acel obiect.
Deci, opțiunea aici este că am
mers la stânga și am luat-- ei
bine, asta va
fi dificil de făcut la timp.
Pretenția este că cel
mai bun răspuns aici
este să mergi aici cu 100 și să
iei 5, deoarece coborârea
corespunde cu
eliminarea ultimului element.
Dacă m-am dus la stânga,
asta corespunde...
scuze... primul articol.
Dacă m-am dus la
stânga, asta corespunde
cu eliminarea ultimului
element, deci opțiunile mele
sunt 10 plus 25, adică
35, față de 100 plus 5.
105 victorii, de aceea
există o margine roșie aici care arată
că a fost alegerea mea mai bună.
Și, în general, dacă urmați
aceste indicații ale părinților înapoi,
vă oferă
strategia optimă în ceea ce ar trebui să faceți.  În
primul rând, ar trebui să luați 5 este
ceea ce spune asta, pentru că
tocmai am tăiat 5.
Obișnuiam să începem
aici, iar acum
începem aici în acest subinterval.
Apoi, adversarii noștri, ca să fie
enervant, vor lua 25--
nu
contează, cred.
Apoi vom lua
100, apoi ei
iau 10, și jocul s-a terminat.
OK, toate numerele de
aici sunt câte puncte
obținem -- nu spune câte
puncte primește adversarul.
Desigur, ai putea
adăuga și asta.
Este doar
suma totală minus ceea ce primim.
Acum, lasă-mă să revin
la nivel înalt aici.
Ceea ce facem cu adevărat
este extinderea subproblemei,
iar aceasta este o idee pe care o
vom extinde la următoarea prelegere.
Și ideea este
că uneori
începeți cu
subproblemele evidente ale prefixelor,
sufixelor sau subșirurilor.
Aici,
versiunea evidentă era subșiruri,
pentru că ne
mutam de la ambele capete.
Dacă nu știți, probabil
sufixele sau prefixele
sunt suficiente.
Așa că începem de acolo,
dar uneori
încă nu sunt suficiente subprobleme.
Aici, de îndată ce am făcut
o mișcare, problema noastră aproape s-
a întors pe dos,
pentru că acum e
rândul tău, în loc de rândul meu.
Și a fost pur și simplu
enervant să ne ocupăm,
așa că am putut... ori de câte ori te
confrunți cu un nou tip de problemă, să
construim mai multe subprobleme.
Atâta timp cât rămâne un
număr polinom,
vom obține timpul polinom.  Așa că
aici am dublat
numărul de subprobleme
doar la cazul meu
și cazul tu,
iar asta a făcut această recurență
foarte ușor de scris.
În note, veți vedea
un mod mai dezordonat de a o scrie,
dacă nu faceți asta.
În exemplele pe care le vom
vedea următoarea prelegere,
vom face
mult mai multă expansiune,
poate înmulțind numărul
de probleme cu n sau n pătrat.
Și acest lucru ne va oferi... ne
va permite să adăugăm mai multe
constrângeri subproblemelor noastre,
așa cum am făcut în cea mai lungă
succesiune.  Am
adăugat această constrângere că
începem cu un anumit articol.
Cu cât avem mai multe subprobleme,
putem lua în considerare mai multe constrângeri,
pentru că doar vom folosi forța brută
toate constrângerile posibile
care s-ar putea aplica.  Ei
bine, vom vedea mai multe
data viitoare.
Asta e pentru azi.