[SCRÂȘIT]
[FOȘIT] [CLIC]
JUSTIN SOLOMON: Corect, așa că
astăzi va fi prima noastră,
cred, din două
sesiuni cu probleme care
acoperă programarea dinamică.
Am învățat că
programarea dinamică este
una dintre aceste
părți interesante ale unei clase de algoritmi
în care, cumva, oamenii
care sunt cu adevărat buni la asta
sunt complet disjunși
cu oamenii care
sunt buni la toate celelalte
părți ale clasei de algoritmi.
Deci, pentru unii dintre voi,
asta ar putea fi promițător,
iar pentru alții, poate
puțin mai puțin.  Așa că
poate vom petrece doar
un minut sau două revizuind
ideile de bază pe care le vom
aplica în aceste probleme,
deoarece acestea vor urma, mai mult
sau mai puțin, același șablon.
Deși, bineînțeles,
ca de obicei în 6.006,
ne place să punem niște
vitrine interesante în jurul lui,
astfel încât să nu fie complet
evident ce faci.
Și apoi vom face o
grămadă de exemple de probleme.
Dreapta.
Deci haideți să vorbim puțin
despre programarea dinamică
și despre ideea de bază aici.
Așadar, programarea dinamică este
un lucru ciudat amuzant în 6.006,
în sensul că,
de exemplu, în
partea de structuri de date a cursului,
am învățat, cum ar fi, ce...
acum mă chinui să mă
gândesc la o structură de date,
cum ar fi  un util, cum ar fi copaci
și matrice sau orice altceva.
Și acestea sunt de fapt
lucruri pe care le puteți codifica.
dacă te uiți și
vezi dacă există... ei
bine, în mod plauzibil, ar putea
fi o implementare
a unui arbore acolo undeva.
Și deci aceștia sunt
algoritmi utili pe
care poate chiar îi puteți
citi pseudocodul.
Și există un univers
în care într-adevăr
traduci acel
pseudocod în ceva în
interiorul laptopului tău.
Programarea dinamică este
puțin mai puțin.
Acesta este mai degrabă un meta--
Nu știu dacă l-ai
numi un meta algoritm
sau o abordare de rezolvare a problemelor
sau ce,
dar nu este așa cum spui
cumva, voi
aplica algoritmul de
programare dinamică
acestei probleme.  .
Dar, mai degrabă, este un fel de această
clasă mare de lucruri care
urmează toate un șablon similar sau un
fel de abordare a gândirii
despre rezolvarea problemelor, ceea ce
cred că explică de ce, de
fapt, într-un anumit sens,
ultimele două prelegeri pe care
le-ați  văzut-- și, cred, dacă
înțeleg corect secvența de timp
a cursului nostru, următorii
doi ani pe care îi veți
vedea--
și
sesiunile cu probleme încep de fapt
să coincidă în sensul
că atunci când Erik
vă preda, băieți  programare dinamică,
cum a făcut-o?  Ei
bine, el nu a
notat... ei bine, a
scris
un șablon
pentru programare dinamică,
dar apoi am făcut doar
câteva exemple de probleme.
Și exact asta
vom face astăzi.
Deci, cumva, toate
aceste lucruri vor
converge în
această parte a cursului nostru

, deoarece programarea dinamică este într-
adevăr mai mult un mod de viață
decât orice algoritm anume.
Și acesta este un
model pe care cred că îl
vedeți mult în
algoritmii avansați.
Ca, de exemplu,
în universul meu,
în analiza numerică, când
vorbești despre algoritmul ADMM,
este de fapt un
algoritm total inutil.
Ceea ce contează este aplicarea
acesteia la o anumită problemă.
Și acesta este, cred,
un fel de mod mai matur sau mai matur
de a gândi la
o mulțime de lucruri
în algoritmi, că destul de curând,
acest tip de chestii de uz general
care sunt utile
tot timpul,
cred, începe să
disperseze un  puțin în favoarea
diferitelor modele
și mecanisme la
care ești obișnuit să te
gândești.
Așa că există o introducere filozofică de
10 secunde

despre ceea ce facem,
timp în care am
reușit să urmăresc
această masă prin cameră.
Știi, am cântat...
Am făcut o facultate pe
coasta de vest și am
crezut că voi
fi o licență în muzică.
Și a fost o
clasă de master de pian în care am
uitat să punem
clemele mici pe roți
și a fost un
cutremur și am
crezut că sunt foarte nervos
pentru că pianul
scăpa literalmente de mine.
Nu mă pot gândi niciodată la acea
nocturnă a lui Chopin în același mod.
Dar, în orice caz, în
programarea dinamică,
Erik a prezentat pentru voi
un anumit
set de pași care sunt o
abordare utilă de rezolvare a problemelor
în
universul programării dinamice.
În sesiunea de probleme de astăzi
, voi
încerca să vă ajut să
traduceți puțin
din acest șablon la ceea ce
înseamnă să scrieți cod pentru a
implementa un
algoritm de programare dinamică,
deoarece cred că este
ușor să uitați asta aici.
Dar, pe de altă
parte, la temele tale,
atunci când scrii
răspunsuri la problema algoritmilor,
este perfect să urmezi
acest șablon chiar și literă--
presupun-- literal literă
cu literă și să răspunzi la fiecare
dintre aceste întrebări.
Și apoi lipiciul rămas
de care aveți nevoie pentru a scrie
codul nu este
teribil de interesant
din
perspectiva teoriei algoritmilor.
Deci, ideea de bază
aici este că există
o mulțime de probleme diferite
care pot fi scrise recursiv,
într-un anumit sens.
Cu siguranță, i-am întâlnit pe
mulți dintre aceștia la acest curs.
De fapt, cred că
părtinirea în modul în
care am prezentat
algoritmi care
nu trebuie să fie recursivi este să
le scriem într-un mod recursiv.
Iar ideea aici este că,
atunci când ai un apel recursiv
și repeți ceva,
dai funcției
aceeași intrare de
mai multe ori, s-ar
putea la fel de bine să-ți amintești ce ai
primit ultima dată când ai văzut
acea intrare și
apoi nu  nu trebuie să
fac calculul din nou.
Într-adevăr, într-o singură propoziție, cred că asta
este aproximativ logica din spatele
tuturor acestor
lucruri de programare dinamică.
Deci nu există niciun motiv să fii
prea redundant cu prelegerea.
Doar pentru o
privire de ansamblu de 10 secunde,
cred că există un exemplu
care este în același timp
bun și înșelător, care
este această secvență Fibonacci.
Este bine în sensul că
logica programării dinamice
este cu adevărat ușoară.
Este rău că timpul de rulare este
cam ciudat să te gândești.
Dar amintiți-vă, totuși,
secvența dvs. Fibonacci
arată ceva de genul f din
k este egal cu f din k minus 1
plus f din k minus 2.
Și dacă vă uitați la
arborele dvs. de apeluri recursiv aici -
cum ar fi, să spunem că
da.  k este egal cu 4.
Apoi va apela --
funcția mea f va trebui să o
evalueze la 3 și 2.
Și apoi 3 va fi
evaluat la 2 și 1 și așa mai departe.
Și lucru de observat este
că atunci când numesc f din 4--
sau, mai degrabă, f din 3 aici, dacă ar
fi 3 altundeva
în arborele meu, primesc
același număr, deci,
în special, f
din 2 și f  de 2.
Ambele vor
necesita ceva de
lucru algoritmic, dar
dacă doar prima dată când
văd un 2, am o
bucată de hârtie răzuită
și spun, oh, de fiecare
dată când văd k este egal cu
2, doar întoarce-te
acest număr mai degrabă
decât să fac
apeluri recursive, atunci, de fapt,
dacă există vreun subarbore
sub acest lucru,
tocmai l-am tăiat
din arborele meu.
Și asta este
logica de bază aici.
Și asta este practic
paradigma
care se întâmplă în acest
acronim SRTBOT, care înseamnă că
mai întâi îți iei problema
și o împărți în subprobleme.
Asta e misterios.
De ce se mișcă această placă?
Oh, am un telefon în buzunar
și m-am lovit de perete.
Nu sunt obișnuit cu această clasă.
Dreapta.
Da.
Așa că primul lucru pe care
doriți să-l faceți
este să scrieți problema mea
ca acest tip de formă.
Observați doar că am făcut
asta mult în această clasă, am
scris
lucrurile recursiv.
Diferența aici este că
tipul de argument
care intră în recursivitate
este de obicei, poate,
puțin mai simplu decât introducerea
unei structuri de date uriașe
în interior sau
ceva de genul acesta.
Deci, de exemplu,
sortarea îmbinării, ați
putea scrie în această paradigmă.
Bănuiesc că am acoperit
asta, dar probabil că
nu este cel mai natural mod
de a ne gândi la sortarea prin îmbinare.
Apoi trebuie să ne relaționăm
subproblemele unele cu altele.
Deci, de exemplu, în
problema secvenței Fibonacci,
tocmai v-am dat
relația care--
ceea ce definește problema.
De altfel, acesta este, ce,
un model pentru reproducerea
iepurilor,
cred, dacă îmi amintesc că am
citit istoria
șirului Fibonacci.
Și apoi, cred că,
pentru mine, cel mai--
nu neapărat nenatural-- dar
cred că lucrul care poate este cel
mai greu de transpus într-un
algoritm dacă te gândești să
scrii cod este acesta--
o, omule, acesta este  va
fi o problemă -
această idee de ordine topologică.
Ideea de bază aici este că
dacă f din 1 ar depinde de f din 2
și f din 2 ar depinde de f din
1, aș avea multe probleme,
nu, pentru că într-un fel
arborele meu nu ar
converge niciodată, mai întâi de toate,  dacă
aș face aceste apeluri recursive
și nu aș putea niciodată
să memorez sau, într-un fel, să-mi
amintesc o valoare când merg mai departe.
Dreapta?
Și deci ideea
aici este că există
o ordine a
subproblemei mele, astfel
încât să pot construi o soluție.
Și există, un fel
, două moduri duble
de a ne gândi
de ce este util.
Deci, în
universul memorizării, ce fac?
Adaug doar o declarație if care
spune că dacă am
evaluat deja f din k, returnez-o.  Asta e
perfect.
Celălalt lucru pe care îl pot face
este dacă îmi scriu problemele
în ordine topologică,
atunci pot să
merg într-un fel în direcția inversă și să-mi
construiesc tabelul de memorare.
Deci, de exemplu, pentru
problema secvenței Fibonacci,
aș putea face f de 1 și apoi f
de 2 și apoi f de 3 și f de 4
până ajung la
valoarea k pe care mi-am dorit-o de fapt.
Și acestea sunt doar
duble ale aceleiași monede.
Sunt exact
aceeași abordare.
Deși
versiunea de memorare,
uneori puteți
elimina subproblemele
pe care de
fapt nu trebuia să le rezolvați.
Deci, de exemplu, poate că
acesta a fost f de k minus 7
și, astfel, pot sări peste câțiva
indici din matricea mea.
Nu cred că, de obicei, asta
are un efect mare asupra timpului de execuție
pentru problemele pe care le-am
văzut,
dar ar putea, în mod plauzibil,
în unele universale.
Ar trebui să mă gândesc
la o problemă
în care asta face diferența.
Dreapta.
Și apoi cred că
partea BOT a SRTBOT
este puțin mai ușor
de gândit.
Trebuie să vă asigurați că
această recursivitate are un caz de bază,
cum ar fi când se va
opri acest lucru.
Este exact la fel.
Este orice
algoritm recursiv.
O pentru original,
cred, este puțin
retrofit pentru a face
SRTBOT să sune frumos,
dar cred că ideea
aici este că
trebuie să vă întoarceți la
problema inițială
și să vă asigurați că
corespunde
unuia dintre
apelurile de funcție pe care le-ați  Am scris
în toate chestiile astea complicate.
Sper că aceasta este o
caracterizare rezonabilă.
Și apoi, în sfârșit,
t este mai mult...
acestea sunt pentru a descrie
algoritmul tău.
Ultima este
pentru analiza.
Și, din nou,
partea BOT a SRTBOT
aproape se aplică la orice am
făcut în 6.006, așa cum ar trebui să
analizați întotdeauna timpul de rulare.
BINE.
Deci, în orice caz, aceasta este
versiunea mea de 10 minute
a ultimelor două prelegeri
și, cred, mai mult sau mai puțin,
suficient pentru a ne face să începem cu
câteva exemple de probleme aici.  Îmi
pare rău, nu m-am putut abține.
Îmi place să predau lucruri.
BINE.
Deci, corect.
Deci, în sesiunea noastră de probleme
, avem
câteva dintre problemele legate de teme
de anul trecut de rezolvat.
Dacă vă face să vă
simțiți mai bine,
m-am
încurcat cu unul dintre ele
aseară, în timp ce mă
pregăteam pentru azi.
Și aștept cu nerăbdare să fac
asta în fața voastră a tuturor
acum.
Dreapta.
Așadar, mi-e frică de asta, așa că voi
merge la următorul panou.
BINE.
Deci, în prima noastră
problemă, Sunny studiază--
asta a fost-- cumva, convențiile
drăguțe de denumire pe care le
avem în 6.006
au devenit meta în această problemă,
pentru că există o problemă
legată de Tim Castorul.
Dar, după cum știm cu toții,
Tim este MIT înapoi,
așa că se întâmplă să se încadreze
în acest joc prost
pe care lui Jason îi place să-l joace în
problemele cu temele de scris.
Oricum, dar este
și mascota MIT.
Oricum, m-am entuziasmat foarte tare.
Dreapta.
Deci, ce se întâmplă
în această problemă?
Deci, Castorul Tim are un fel de
interesant... știi,
matematică, cred că ai
numi asta o martingală dacă
arunci puțin moneda
când rezolvă problema asta.
Dar, din fericire, Tim Castorul este
un tip determinist.
Și se uită la
vremea de afară,
și dacă este o temperatură
t... se pare că
Tim castorul e
bine cu fierberea.
Cu cât temperatura este mai mare, cu atât
Tim devine mai fericit.
Așadar, acesta este un fenomen derivat din prima
.
În special, într-o anumită zi,
dacă am o temperatură t,
Tim castorul are
două lucruri pe care le
poate face pentru a-și schimba starea de spirit.
Aparent,
starea de spirit a lui Tim Castorul nu rămâne niciodată fixă.
Merge mereu în sus și în jos.
În special, poate fie să
iasă afară, caz în care
fericirea crește cu
t, OK, fie poate rămâne înăuntru, caz în care

fericirea lui scade cu t.
BINE.
Așa că în fiecare zi, Tim
Castorul, se trezește el...
Vreau să spun foarte mult că
își verifică umbra,
dar asta e un gopher, nu?
În orice caz, se trezește
dimineața, verifică vremea
și decide dacă

vrea sau nu să iasă afară.
Și dacă iese afară,
devine mai fericit
cu o sumă
egală cu temperatura.
Dacă rămâne înăuntru, devine
mai puțin fericit cu o sumă
egală cu temperatura.
Apropo, cred că
soluția noastră este perfectă
dacă aici temperaturile sunt negative
, caz în care,
presupun, totul s-
ar întoarce intuitiv.
Dar nu există niciun motiv să
fii prea obosit de asta.
Dar, desigur,
există o întorsătură aici.
Deci, Tim, ca și mulți dintre voi,
are n zile până la examenul final.
Și îi face griji să studieze.
Da?
Deci, în special,
nu vrea să meargă niciodată --
a venit cu
o hotărâre personală
de a nu ieși niciodată afară mai mult
de două zile la rând.
Da?
Deci, corect.
Și deci întrebarea este...
corect, pentru că așa
trebuie să stea înăuntru
și să studieze cel puțin una
din trei zile.
BINE.
Deci întrebarea este cum își poate
maximiza Tim fericirea.
De altfel, în
învățarea automată,
uneori ei numesc
acest regret de minimizare,
ceea ce am considerat întotdeauna
un mod foarte trist de a mă
gândi la algoritmi atunci când
există o versiune complet duală.
Dar Tim este un tip optimist.
Vrea să-și maximizeze
fericirea sub rezerva acestei
constrângeri că nu poate ieși
afară mai mult de două zile
la rând.
Dreapta?
Deci, dacă ies
luni și marți,
trebuie să stau
înăuntru miercuri.
Da?
PUBLIC: Cred că
nu are niciun efect asupra fericirii lui
când rămâne înăuntru.
JUSTIN SOLOMON: Nu are
niciun efect asupra fericirii lui
când rămâne înăuntru.
PUBLIC: Cel puțin,
asta este [INAUDIBIL]..
JUSTIN SOLOMON: Nu, spune
cu o scădere.  în fericire
când t-- oh, când t este negativ.  De
fapt, asta nu ne va
afecta deloc problema.
PUBLIC: Nu o va
afecta.
JUSTIN SOLOMON: Sigur,
da, pot să repar asta în direct.
Asta se întâmplă când
rezolv singur problema
înainte de a privi răspunsul
și apoi nu îl verific îndeaproape.
Amenda.
Deci, hai să schimbăm asta.
Îmi place mai mult această problemă, cumva
, din punct de vedere psihologic.
Dar este in regula.
Dreapta.
Deci, Jason subliniază corect
că, dacă citești cu adevărat
problema, ceea ce se cere
acolo este ușor diferit,
că atunci când iese afară,
fericirea lui crește cu t.
Dacă rămâne înăuntru,
fericirea lui nu face nimic.
Dreapta?
Deci rămâne la fel.
Scuzele mele, așa că Tim Castorul
este un castor deosebit de optimist
.
Fericirea lui poate
crește doar în timp,
presupunând că trăiește într-un climat
cu temperaturi pozitive.
BINE.
Cred că l-am prins chiar acum.
Misto.
Vom vedea dacă
mai pot face asta.
Da, cred că practic
nimic nu se schimbă.
OK, e grozav.  În
regulă.  O vom
face.
BINE.
Corect, deci întrebarea este
cum rezolvăm această problemă.
Și, din fericire, cred că
punem cea mai ușoară problemă pe primul loc.
Și, în special, dacă ne
urmăm paradigma SRTBOT
aici, există cumva un
set de subprobleme care
ne privesc în față.
Acesta este cuvântul pe care îl caut.
În special, ei
bine, există un
singur indice în
problema noastră, care
este ziua respectivă.
Deci, lucrul evident
de făcut ar fi să spunem, ne
putem da seama de
cantitatea maximă
de fericire pentru zile, să
zicem, până în ultima zi?
Apropo, dacă fac asta,
folosesc versiunea de prefix
a problemei mele -
ah, versiunea de sufix
a problemei mele.
Aș putea face, de asemenea, în
sens invers și să lucrez de la sfârșit
înapoi înăuntru.
Poate dacă avem timp până la
sfârșit, o
vom face pe al doilea.
Dar nu prea contează.
BINE.
Deci, în special, doar pentru a
adăuga un pic de notație,
să presupunem că t din i este egal
cu temperatura din ziua i.
BINE.
Și acum vom
face un lucru nou, care va
fi
variabila reală pe care vrem să o calculăm.
Acesta va fi de la x la
i, ceea ce, vom scrie,
este fericirea maximă pe care o
puteți obține dacă luați în
considerare doar calendarul din ziua
i până în ziua n, cred că inclusiv.
BINE.
De altfel, doar
pentru comoditate,
vom presupune că
x i este egal cu 0
dacă trec de sfârșitul
matricei mele, ceea ce cred că
este un fel de lucru tipic de
făcut în acești algoritmi de tip DP.
BINE.
Așadar, întrebarea este dacă putem
veni
cu un
algoritm recursiv care să calculeze
x i folosind acest mod frumos, un fel de
aciclic tipologic,
de a gândi problema noastră.
Răspunsul este evident da,
altfel nu aș fi aici astăzi.
Și așa că, în absența
unei idei mai inteligente,
să facem
aici abordarea Toucan Sam și să
ne urmăm nasul și să vedem dacă ne putem
scrie problema în termenii
altora.
Deci, în general, să
spunem că Tim Castorul se
trezește în ziua I.
Are, practic, două decizii pe
care le poate lua, nu?
Fie poate rămâne înăuntru,
fie nu poate sta înăuntru.
Poate să iasă afară, nu?
Deci, să ne
ocupăm de aceste trei cazuri.
Deci, în caz, unul rămâne înăuntru.
Ei bine, acum ce se întâmplă
cu fericirea lui?
Ei bine, conform
versiunii mele revizuite
a acestei probleme, nimic, deci,
în special, ce știm?  Ei
bine, dacă rămâne
înăuntru, atunci are...
orice decizie pe care o poate lua
mâine, nu contează.
Poate să intre înăuntru,
poate să iasă afară,
orice, pentru că, fiindcă a
stat înăuntru, și-a
câștigat două
zile libere să iasă afară
dacă vrea.
Dreapta?
Deci, în special, în acest
caz, ne putem convinge
că acest lucru este adevărat, cred.
Da, deci, cu alte cuvinte, deși
nu are nicio utilitate pentru azi,
mâine se trezește și
poate lua orice decizie
dorește.
BINE.
Al doilea lucru pe care îl
poate face este să iasă.
Aici lucrurile
devin puțin complicate.
Dreapta?
Pot doar să iau t
i și să-l adaug la x i plus 1?
Ce merge prost?
PUBLIC:
Ieși trei zile...
JUSTIN SOLOMON: Poate
ieși trei zile la rând, nu?
Cumva, trebuie să-ți
amintești asta, nu?
Și de-acolo lucrurile sunt
puțin dure de cap,
că, în special, dacă
ies azi și mâine,
nu mai pot ieși a doua
zi.
Și cumva, dacă am
trata doar acest caz
ca t i plus x i plus 1,
nu ne-am aminti asta.
Și asta e o problemă.
Deci, în schimb, ceea ce
putem face este să ne gândim că
există două subcazuri, nu?
Deci, ceea ce vom presupune
este că nu numai că
iese astăzi, ci că este
liber să iasă mâine.
Și vom face
acea presupunere recursivă
pe măsură ce ne deplasăm în jos.
Deci, dacă facem asta, ei bine, acum
avem cazul a și cazul b.
Deci, în cazul a, el iese
astăzi și rămâne mâine.
Da.
BINE.
Deci, ce se întâmplă în
acest caz, ei bine...
apropo, folosesc acest
tip de notație ciudată cu săgeți.
Nu știu dacă
acest lucru este bun sau nu,
dar, în esență,
ideea este că
țin evidența cazurilor
și, în cele din urmă, o să
vreau să fiu nevoit să
iau maximul
total al acestor lucruri.
Așa că nu-mi place
semnul egal pentru că, cumva, este
puțin înșelător.
Dreapta.
Deci, în acest caz, ei bine,
el are utilitatea
de a fi ieșit astăzi.
Mâine rămâne
înăuntru, ceea ce înseamnă
că poimâine
poate face ce dracu
vrea.
Are domnie liberă.
Așa că pot scrie asta folosind
acest apel recursiv.
BINE.
La fel... corect.
Mă pricep la asta.
Îmi pare rău, este mult prea
distractiv pentru mine.
Pot să mă joc cu
această placă toată ziua.
BINE.
Deci, în cazul 2b, el iese
astăzi și iese mâine.
BINE?
Deci...
PUBLIC: E un animal de petrecere.
JUSTIN SOLOMON:
Este un animal de petrecere.
Este un animal și
iese foarte mult.
Corect, deci în acest
caz, ce se întâmplă?
Ei bine, el înțelege asta.
El primește utilitatea de astăzi.
El primește utilitatea de mâine.  A
doua zi, el
trebuie să rămână înăuntru,
așa că ar putea la fel de bine să omitem.
Și apoi poate face ce
vrea a doua zi după aceea.
BINE?
Deci, dacă ne întoarcem,
cred că, din punct de vedere tehnic, ar
trebui să ne revizuim
puțin definiția pentru x,
că nu este maximul
fericirii - ei bine, ne
putem convinge
că este același lucru.
Dar, într-adevăr, nu este
fericirea maximă pentru ziua i până la n.
Este
fericirea maximă pentru zilele de la i la
n, în
ipoteza că are
permisiunea de a ieși în ziua i.
Dreapta?
Și asta este cu adevărat
ceea ce se întâmplă
în setul nostru recursiv
de apeluri de aici.
BINE.
Deci recursiunea noastră
are sens aici?
Misto.  În
regulă.
Deci haideți să vedem aici.
Deci, dacă ne urmăm
SRTBOT--
continui să revizuiesc lucrările care
folosesc mult cuvântul paradigmă,
așa că simt că ar trebui să fac asta.
Deci ce este t?
Este ordinea topologică.
Observați că x i
depinde doar de i-urile mai mari.
Deci, în ceea ce privește
ordinea noastră topologică,
graficul de dependență
este foarte simplu.
Este doar o linie,
așa că nu uitați că vă
puteți gândi la
ordinea topologică
sau vă puteți gândi la a
fi un graf aciclic.
Acestea sunt echivalente.  Am
acoperit asta în acest curs.
Îmi place să mă gândesc
la graficele aciclice.
Deci x1 depinde de x2 depinde
de x3 depinde de x4.
Graficul acela nu are
cicluri, așa că suntem buni.
Dreapta.
Deci, în continuare, trebuie să
venim cu cazul nostru de bază
pentru recursiunea noastră.
Observați că modul în care am
ales să rezolv această problemă
este prin apelarea
indicilor viitori, ceea ce
înseamnă că cazul meu de bază
se află la sfârșitul matricei mele,
deoarece este un fel ca cel
mai jos din
trenul recursiv.
Lanțul recursiv este
ceea ce căutam,
dar îmi place
mai mult trenul recursiv.
În special, în ziua n-- ei
bine, dacă are permisiunea
de a ieși în ziua n,
el poate face unul din două lucruri.
Poate ori să iasă, ori nu.
Nu contează, nu?
Deci, în special, putem
spune că acesta este maximul lui 0
sau t al lui n.
Ține minte, nu
ți-am spus că temperaturile
trebuie să fie pozitive.
Poate că e un
fel de castor Celsius.
BINE.
Dreapta.
Și apoi, pe lângă...
pentru comoditate,
observați că, de exemplu, există
un univers în care mă
uit dincolo de sfârșitul matricei mele
în apelul meu recursiv aici, așa că
ar trebui probabil să mă gândesc la
câteva x-uri suplimentare.
Evident, utilitatea
ieșirii într-o zi care nu există
este 0.
Deci putem spune că x n plus
1 este egal cu x n plus 2 este egal cu 0.
OK.
Am reușit să folosesc mult prea
mult spațiu pentru o
problemă simplă de algoritmi.
BINE.
Da?
Primesc credit pentru asta?
BINE.
Dreapta.
Deci acum trebuie să
facem o și t.
Deci, care este problema noastră inițială?
Ei bine, amintiți-vă că vrea să-și
maximizeze fericirea începând
din prima zi, așa că problema noastră inițială
este doar x de 1,
sau nu?
Așa că, amintiți-vă că
Tim Castorul --
instructorul dumneavoastră este
foarte neglijent când
vine vorba de a
citi cu adevărat problemele,
așa cum ați văzut la început.
O a doua greșeală pentru care
aș fi
pierdut personal puncte dacă aș fi rezolvat
această problemă la temele mele
este că nu mi-a cerut doar
cantitatea maximă de fericire
pe care Tim a putut-o obține --
asta nu este foarte practic
pentru castorul tău de zi cu zi --
ci mai degrabă, el vrea să
cunoască planul real.
Vrea să știe în ce zile
poate ieși și în ce zile
nu.
Da?
Și de fapt nu
ți-am spus cum să faci asta, nu?  Ți-am
spus doar
cum să calculezi
x, care este doar
cantitatea maximă de fericire.
Dacă aș fi în voi, băieți,
cred că aceasta este
o simplificare perfect rezonabilă,
care este
ca o problemă de încălzire de rezolvat.
De fapt, aș susține că este mai
puțin o încălzire și mai mult
cheia problemei --
și apoi să mă întorc
și să te asigur că
te poți convinge
că ai putea
reconstrui soluția.
Modul meu de a rezolva acest lucru
a fost puțin
diferit de
cel din problemă,
dar sunt echivalente,
adică
pot face o a doua matrice -
nu o voi scrie,
pentru că sunt lent la scris  --
asta spune doar în fiecare zi,
dacă am luat opțiunea 1, opțiunea
2a sau opțiunea 2b.
Și acum îmi pot reconstrui
planul foarte ușor, nu?
Așa că mă uit la x1, dacă am luat
opțiunea 1, atunci rămân
și mă uit la ziua a doua.
Dacă am luat opțiunea 2a, atunci
pot eticheta azi, mâine
și poimâine.
Oh, stai... da, așa e.
Pot eticheta alegerea de azi,
alegerea de mâine,
alegerea a doua zi și apoi să mă
uit trei zile mai târziu
și să recurg în acest fel.
Opțiunea b este oarecum similară.
Așadar, o modalitate rezonabilă de a
reconstrui setul real
de zile în care ieși
și în ce zile intri
este doar să-ți amintești, în timp ce faci
memorarea sau orice altceva,
dacă ai făcut
opțiunea 1, 2a sau 2b.
Și apoi este destul de ușor
de reconstruit de acolo.
Poate vă las să
vă convingeți
de asta acasă sau
în ultimele 8 secunde
dacă se întâmplă să fiți cei doi
membri ai publicului pe care îi am.
Și apoi, în sfârșit,
trebuie să ne facem treaba cu timpul.
Și de cele mai multe ori
argumentele de aici
urmează mai mult sau mai puțin
același model,
adică numărați
numărul de subprobleme
și timpul pe subproblemă,
înmulțiți aceste două lucruri
împreună și
obțineți timpul de rulare.
Vom
vedea într-o singură problemă
a acestui set de probleme care
nu este tocmai corectă, deoarece
trebuie să ținem cont de
unele precalculări.
Dar în acest caz, este.
Bine, deci să vedem, care
sunt subproblemele noastre aici?
Ei bine, în esență... Presupun că
nu am spus-o,
dar trebuie să luați
maximul acestor trei valori.
Acesta este maximum de
trei expresii care
au un număr constant
de semne plus și căutări
și memorie și toate
acele lucruri bune.
Deci, fiecare subproblemă
ia ordine o dată.
Câte probleme sunt?
Ei bine, există,
cred, n plus 2 max,
dacă vrei să fii
conservator în privința asta.
Deci, în special, există
ordine n subprobleme, nu?
Deci tot ce trebuie să fac este să înmulțesc
aceste două lucruri împreună,
iar algoritmul meu
ia ordine n timp.
Și aceasta este soluția noastră
la problema numărul unu.
Aveți întrebări până acum?
Da?
Uh-oh.
PUBLIC: Când mă gândeam
la problemă în prealabil,
mă întrebam dacă poți
folosi cazuri de bază --
acum, avem două
tipuri diferite de caz de bază,
un caz de bază pentru x din n și un
caz de bază pentru lucrurile ulterioare.
Pot să îl elimin pe primul
și să adaug și un x de n
plus 3 egal cu 0?
Ce ar face asta?
JUSTIN SOLOMON: Aș putea să îl
elimin pe primul
și să adaug un x de n plus 3?
Da, cred că e în regulă.
Îmi pare rău, acesta nu este un
răspuns deosebit de util
pentru cei care
urmăresc videoclipurile.
Răspunsul meu la această întrebare pe care
nu o auzi este da.
Deci întrebarea, ca să repet,
a fost că acest caz de bază
arăta cumva complicat.
Pentru a fi corect, este
cea care mi s-a
dat în sarcina [INAUDIBLE]
, dar asta e în regulă.
Dar întrebarea a fost dacă
acest lucru este cu adevărat necesar.
În special, pot
scăpa de cazul x n
și, în schimb, pot adăuga o a treia
zi după sfârșitul timpului,
care are și valoarea 0?
Și dacă, într-un fel, uitați-vă la
acel plus cazul b, cred că-- sau
mai degrabă, cazul a--
credeți că puteți convinge-- ei
bine, cazul a și b,
de altfel, vă puteți
convinge că acestea
sunt  echivalent, nu?
Este absolut corect.
Așa că aș putea adăuga o a treia zi după
sfârșitul acestui lucru, care
are și valoarea 0.
Sau, apropo, aș putea
spune doar în codul meu dacă n este --
dacă i este mai mare decât n, returnează 0.
Acesta este  același lucru.
Da, și atunci
cred că nu trebuie să-mi fac
griji pentru cazul x n.
Da, astea sunt la fel.
Fiecare a lui.
Intrebare fabuloasa.
Alții la care pot
răspunde în timp ce suntem la asta?
Misto.  În
regulă.
Deci asta e problema unu.
Scriind prea mare... Nu-mi
place această cretă mare, știi.
BINE.
Deci problema a doua este
cea care m-a înfierbântat
și m-a deranjat ieri.
Deci, să vedem dacă ne descurcăm
mai bine în fața oamenilor,
pentru că acesta este de obicei cel
mai bun mod de a îmbunătăți
abilitățile de rezolvare a problemelor.
Dreapta.
Deci, în problema doi,
care, în mod enervant,
este, de asemenea, probabil cea
mai practică problemă
din acest set de probleme.
În esență, ai un...
Presupun că ar trebui să
notez niște chestii.
Deci, în problemă-- am
folosit partea greșită--
doi, aveți un
sistem de operare Menix--
orice-- care este--
aparent, este foarte simplu.
PUBLIC: Menix, Unix.
JUSTIN SOLOMON: Oh, am înțeles.
[RÂDE] Nu
înseamnă că trebuie să-mi placă.
Dreapta.
[RÂDE] Deci, în
Menix, aparent,
singurul lucru pe care
sistemul meu de operare îl poate face
este să calculeze
distanța de editare dintre fișiere.
Și vrea să
facă acest lucru eficient.
Deci avem că un fișier
este o secvență de șiruri.
Și cred că
spunem că lungimea lor este
mai mică sau egală cu k.
Asta va intra în
joc puțin mai târziu.
Și șirurile sunt
practic doar linii
ale diferitelor fișiere.
Deci, există trei
moduri diferite prin care putem schimba un fișier.
Deci, iată
schimbările pe care le putem face.
Schimbarea numărului 1
înseamnă adăugarea unei linii.
Schimbarea numărului 2 înseamnă
a elimina o linie.
Iar schimbarea numărul 3 înseamnă schimb.
Dar o avertizare pentru acest
model interesant
de ceea ce este ieftin și ce
nu este că, aparent,
schimbarea a două linii este ieftină,
deoarece acestea există în memorie.
De exemplu, poate că, nu știu
, folosesc o
listă legată sau ceva
pentru a stoca fișiere, așa că
schimbarea a două
indicatori nu este atât de rău.
Dar introducerea și
îndepărtarea unei linii
este dificilă pentru că, nu știu,
alocarea memoriei este costisitoare,
așa cum Menix funcționează de fapt
pe tablete de argilă.
Și îmi pot tăia
tăblițele de lut în felii diferite
și pur și simplu le ridic și
le schimb, și asta e în regulă,
dar dacă vreau să adaug
o linie în dosarul meu,
trebuie să merg la Tigru și
Eufrat și să scot...
sau orice ar fi fost,
Eugris și
Tiphrates... și
scoate o piatră.
Este multă muncă să faci
o nouă linie sau să arunci.
Deci acestea sunt scumpe
și acestea sunt ieftine.
Și deci întrebarea pe care
încerc să o
spun și pe care
încearcă să o pun problema
este că vi se oferă fișierele
A și B cu n linii fiecare.
Vrem să știm care este
numărul minim de operațiuni non-swap
,
deci, cu alte cuvinte,
numărul minim de timp pentru
a adăuga și elimina linii
pentru a transforma A în B,
în esență, cu costuri reduse.
Și, de fapt, doar pentru a fi drăguț--
Cred că de fapt este un fel de
indiciu critic în această problemă-- îți
oferim timpul de rulare.
Și o să
o ignor în răspunsul meu, să
observ că am făcut ceva
greșit și apoi să mă întorc
și să o repar.
Acesta este diferit de
felul în care este scris răspunsul,
unde a intrat Dumnezeu și a spus,
cum ar fi, o, observăm că
probabil vom avea
nevoie de acest lucru,
așa că vom merge
mai departe și o vom face aici.
Cred că asta, poate, nu este
reprezentativ pentru logica
de aici.
Corect, deci timpul de rulare aici
este k n plus n pătrat.
Primul lucru de remarcat
este că aici există un k.
Da, și așa că într-o zi va
trebui să comparăm șirurile,
pentru că asta este k.
Și cred că acesta este
indiciu care este
implicit în această problemă.
Este ușor să ratezi.
Și așa, într-adevăr, ceea ce
vom observa
este că ne vom
uita la soluția noastră
și vom spune, ei bine, așteptați o secundă, dacă
nu am implicat un factor de k,
trebuie să fi făcut
ceva greșit.
Și, într-adevăr, așa va
fi,
dar este doar o
soluție minoră să o schimbi.
PUBLIC: Există o altă
distincție importantă
în această privință [INAUDIBIL].
JUSTIN SOLOMON: Oh, îmi pare rău.
Da, corect, când schimb lucrurile,
trebuie să fie adiacente.
Nu pot scrie în
partea de jos a tablei.
Ar trebui să fie a, d,
j, pentru cei care se uită acasă.
Dar ele trebuie să
fie-- puteți
schimba doar liniile care sunt
adiacente, așa cum
apar în fișierul lor original.  O
voi spune cu voce tare, mai degrabă decât să
încerc să o scriu pentru că va
dura restul
prelegerii pentru a face asta.
OK, alte lucruri pe care le-am
uitat?
Există o mare probabilitate.
Sunt rău la asta.
BINE.
Deci acesta a fost enervant.
Și nu este de fapt enervant.
Este de fapt o instanță relativ ușoară
a unui
program dinamic foarte bine-cunoscut plus
câteva lucruri suplimentare, care
se numesc distanță de editare.
De fapt, cred că dacă sunteți în
căutarea intuiției cu privire
la această problemă, s-
ar putea să o căutați pe Google
mai întâi ca, un fel de...
ce a fost asta?
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Oh, de fapt
faci o recitare.
Oh, de aceea nu este
total nerezonabil să
venim cu răspunsul
aici, chiar mai bine.
Dar chiar dacă
nu ai fi avut, știi,
aceasta este doar o altă
problemă de programare dinamică,
care este
puțin mai enervantă
decât problema ta medie de
programare dinamică.
Acum, soluția scrisă
în notele de curs
funcționează de la, un fel,
ultima linie a fișierului
în jos, într-un anumit sens - în
sus, indiferent.
Mi-am pierdut literalmente
două ore din viață
încercând să mă gândesc la
editarea fișierelor de la final
și doar să mă
supăr și să mă confuz.
Deci, aici, voi încerca
să o fac în cealaltă direcție
și probabil să introduc o grămadă
de greșeli în acest proces.
Deci, ce facem în
programarea dinamică
dacă nu știm
ce altceva să facem?
Facem chestii, SRTBOT.
Și să facem asta aici.
Deci, în special, care
sunt subproblemele noastre?
Acesta este puțin funky.
Deci, de fapt, chiar înainte de a
face S-ul SRTBOT,
să ne gândim
puțin la problema noastră.
Să ne gândim la
ce înseamnă de fapt
editarea unui
fișier, pentru că asta m-a
ajutat să mă gândesc
la răspunsul corect
aici, adică
, știi,
deci ce se întâmplă?
Am două documente.
Acesta este documentul A. Acesta este
documentul B. Fiecare dintre ele
este compus dintr-o grămadă de rânduri.
Și, practic,
încerc să transform A în B.
Și singurul lucru pe care îl pot
face este să derulez din linie, să
inserez, să apeși
tasta Enter sau să fac un al treilea lucru
în care îmi place să
schimb două lucruri care
sunt adiacente  unul pe altul.
Acesta este singurul lucru pe care îl pot face.
Și felul în care îmi place să mă
gândesc la această problemă--
există un fel de
enervare aici,
care cred că este o
supărare tipică
în problemele de programare dinamică
, și
anume că ordinea operațiilor
sugerează că această problemă este
mult, combinatoric, mai
dificilă.  decât este, pentru că,
cum ar fi--
OK, să ne gândim la modul în care
editez de fapt documente-- cum ar fi, îmi
petrec 2/3 din zi editând
scrieri de studenți prost absolvenți--
este ca și cum aș sări peste tot
între diferite  linii.  De
exemplu, mai întâi șterg
această linie, apoi
poate merg în partea de
jos a documentului meu
și șterg altul.
Aceasta ar fi o mare problemă
din perspectiva programării dinamice
.
Nu pot sări
peste tot documentul meu,
pentru că ținerea evidenței
întregului istoric al editării
va fi oarecum
uriașă din punct de vedere combinativ.
Dreapta?
Nu sunt butonul Urmăriți modificările
din Microsoft Word.
Vreau
numărul minim de modificări.
Și dacă trebuie să recurg
la toate editările posibile
pentru fiecare
linie în orice ordine,
este o
mulțime de factoriali
și 2 la n care plutesc în jurul valorii
de care nu vreau să am.
Dreapta?
Și deci acesta este genul de
cheie al provocării aici,
este să-mi organizez abordarea
pentru editarea acestor fișiere
într-un mod care să nu
mă oblige să
fac acest tip de
sărituri combinatorii peste tot.
Și cred că este și
cel în care există un fel de... de
parcă știu că Jerry
Caine de la Stanford vorbește
mult despre
saltul recursiv al credinței.
De exemplu,
împărțind cumva problema ta
în
subprobleme organizate, aici este
într-adevăr
provocarea.
Deci, dacă aș fi un
consilier de doctorat mai organizat,
modul în care aș edita
un fișier sau o tabletă de lut,
cred că, în acest caz,
ar fi liniar,
că aș putea la fel de bine să
fac orice naiba am de gând
să fac.  la rândul unu
înainte de a trece pe linia doi.
Și la sfârșitul
zilei, chiar dacă am făcut lucruri
într-o ordine diferită,
te poți convinge
că le-aș putea
comanda întotdeauna în așa fel
încât toate editările pe care le
fac la prima linie,
într-un fel, să aibă loc înaintea
rândurilor.  mai târziu în document,
cu posibila excepție
a acestui lucru de schimb.
Dar vom vedea că
cumva nu contează.
Și, în plus, dacă
fac o editare,
aș putea la fel de bine să o fac pentru a
îmbunătăți lucrurile, nu?  Nu
există niciun motiv să începeți să
introduceți
și să eliminați, vrând-nevrând, linii.
Aș putea la fel de bine să fac întotdeauna o
operație care îmbunătățește lucrurile.
Și așa că, gândindu-mă la acest
tip de logică, mă duce--
ta-da-- la un
mod special în care aș putea să-mi notez
S-ul, câteva
probleme aici, ceea ce
înseamnă că mă voi
gândi la editarea
liniei de document.  pe linie.
Deci, cu alte cuvinte, odată ce
m-am ocupat de linia unu, ceea ce
înseamnă că am găsit
o modalitate de a-l încurca
și de a-l face să se potrivească cu linia
unu a celuilalt tip,
mă voi
gândi doar să o elimin
și apoi să mă gândesc la
restul documentului.
Începi să spui, aha, acea
propoziție sună ca recursivitate.
Și așa este.
Așa vom
rezolva această problemă.
BINE?
Deci, în special, aici va
fi treaba noastră.  Voi
face una ușor
diferită în soluție -
așa că ar trebui să
fiți cu toții vigilenți - și
anume voi scrie x ij
pentru a fi munca minimă de convertit.
Nu sunt programator Python,
dar sper că am înțeles bine.
i două puncte va
fi totul, de la i
până la sfârșitul fișierului.
Deci, cu alte cuvinte, aceasta este
versiunea sufixului problemei noastre -
și în B j două puncte, așa.
BINE.
Deci, cu alte cuvinte,
am un pic--
este un fel ca un videoclip--
cum ar fi, gândește-te la Tetris.
Odată ce obțineți acea
linie completă de blocuri,
puteți doar să aruncați acea
linie de blocuri
și întregul
joc video se mișcă în jos.
Într-un fel, se întâmplă
ceva foarte asemănător
aici, care
este a doua în care am
reușit să obțin o potrivire
pentru rândul unu al documentului
în rândul unu al
documentului următor, o
voi arunca
și o să mă prefac
că am două documente
cu o linie mai puțin în ele.
Acum, lucrul care
m-a blocat aseară,
problema mea inițială presupune
că ambele documente
au aceeași lungime.
Dar aici, nu fac
această presupunere, nu?
Și, în esență, ceea ce ne vom da
seama
este că asta de fapt
nu contează foarte mult,
că dacă ajung cu un
document de lungime k-- ei
bine, nu ar trebui să folosesc k--
un document de  lungime l și un
alt document de lungime 0,
care este cantitatea de muncă
pe care ar trebui să o fac pentru a converti?  Ei
bine, eu, pentru că singura mea alegere
este să inserez o grămadă de linii
într-un document, apropo,
sau să șterg o grămadă de linii
din celălalt.
Acestea sunt duale între ele.
Sunt exact la fel.
Filosofez mult pentru că
mă conving și pe mine
că răspunsul meu este
OK în acest proces.
BINE.
Deci, acestea vor fi
subproblemele noastre setate.
Și acum trebuie să
facem r, nu?
Trebuie să relaționăm, ceva
cu care ne luptăm
uneori la departamentul de matematică.
Și, în esență, modul în
care am procedat în acest sens
este să fac doar un
miliard de cazuri diferite
din toate editările posibile pe care le-aș
putea face pentru linia i și linia j.
Și asta e
perfect în această problemă.
Cred că problema
este un pic neplăcută.
Și modul în care au
scris soluția, s-au
convins
că unele lucruri sunt
echivalente cu altele
și le-au eliminat.
Dar nu trebuie.
Atâta timp cât există
un număr constant
de cazuri, Ponyboy-ul tău de aur.
Deci, în special, să ne
gândim la unele cazuri.
Deci, în primul rând, dacă linia i
se potrivește cu linia j a documentului meu --
amintiți-vă că
nu este chiar linia j.
Este ca și cum ai face un
document care se
întâmplă să înceapă la rândul j.
E ca și cum ai lua foarfece.  Ei
bine, atunci le pot asorta
cu cost zero
pentru că începuturile
sunt în același loc.
Și pot muta
Tetris-ul meu a coborât unul,
și asta e perfect.
Deci, primul caz, cred,
este cel mai ușor, și
anume dacă A i este egal cu
B j, atunci pot doar să
elimin acea linie
din ambele documente
și să merg mai departe,
caz în care--
voi folosi aceeași
notație prostească--
O să iau acel x ij.  Ei
bine, voi
crește doar i și j
și voi continua, așa.
Misto?
Deci ce
altceva aș putea face?
Aș putea șterge o linie.
Da, deci ce se întâmplă...
OK.
Deci cazul doi este
ștergerea A i, nu?
Acesta este un lucru diferit pe care îl
pot face pe linia i.  Ei
bine, acum ce trebuie să fac?
Am un document în
partea stângă,
care este cu 1 rând mai scurt.
Și în
partea dreaptă, nimic nu s-a schimbat.
Dar ștergerea unei linii m-a
costat un dolar.
Deci, în special,
am acel x ij.  Ei
bine, ce se întâmplă?  Ei
bine, am scăpat de o
linie, dar a trebuit să plătesc.
BINE.  Să ne
gândim la
alte lucruri.
Ai putea șterge B j.
Acest caz de fapt
nu este în soluție,
deoarece se dovedește
a fi inutil.
PUBLIC: Ei bine, avem
voie doar să edităm A.
JUSTIN SOLOMON: Oh, am
voie doar să editez A?
Oh, în acest caz,
nu trebuie să șterg B j.  Chiar
nu am citit aceste
probleme foarte atent.
Asta e răul meu.
Acest lucru ar fi
făcut mult mai ușor.
Chiar ar trebui să
citesc aceste lucruri.
Cool, așa că elimină jumătate
din cazurile de pe notițele mele.
Fabulos.
De altfel, ai putea face aceste
lucruri în cealaltă direcție
și chiar nu ar schimba
prea mult această problemă.  Îmi
pare rău, știi,
am acest obicei prost
când citesc lucrări de cercetare
de a citi lucrarea de cercetare pe care am
vrut să fiu acolo în
loc de cea
care este de fapt pe hârtie.
Și, cumva, este un
fenomen foarte asemănător aici.
BINE.
Dreapta.
Asa de bine.
Așa că pot edita doar
documentul A, ceea ce
face acest lucru probabil mai ușor
decât ceea ce îmi făcea griji.
Fabulos.
În acest caz... ah, banane.
Cu al treilea caz
aici, ei bine, să vedem,
aș putea introduce și o linie.
Să vedem.
Deci, ce se întâmplă acolo?
Deci pot edita doar documentul A?
Deci, asta face cazurile mele
diferite de cele pe care le-am
notat pe note.
Îmi pare rău.
BINE.
BINE.
Deci, dacă introduc...
hai să facem asta live.
Da, OK, deci dacă
inserez o linie la linia i,
aș putea la fel de bine să o
fac să se potrivească cu B j.  Nu
există niciun motiv să nu.
Dreapta?
Aș putea la fel de bine să ucid un
element din B în timp ce sunt la asta.
Da?
Deci, dacă fac asta, ce se va
întâmpla?  Ei
bine, încă trebuie să
potrivesc linia i.  L-am
cam mutat mai
jos în dosarul meu.
Dar, în esență,
am ucis o linie din fișierul B
făcând-o să se potrivească cu această
nouă linie pe care am inserat-o.
În notele mele, pentru că am
crezut că pot edita B,
am spus: OK, pot doar să
șterg linia din B.
Și cumva, logic, e
puțin mai ușor de gândit.
Dar acestea sunt exact
duale între ele.
Deci, în acest caz, am x ij.  Ei
bine, mai am de-a
face cu A i.
Nu am scăpat de el.
Dar am potrivit linia j.
Așa că am plătit 1 USD pentru
inserarea unei linii.
Și acum am asta
pentru că am scăpat
de o linie din celălalt fișier.
Dacă m-aș opri aici, de altfel, l-
aș avea la distanță.
Dar, din păcate pentru mine,
am un caz suplimentar,
care este ușor iritant, după cum se
spune, și anume pe care îl pot schimba.  În
primul rând, pot schimba întotdeauna?
Adică, pot, dar
dacă schimb două linii
și tot nu se potrivesc cu
liniile din partea dreaptă,
sunt oarecum furtun, nu,
pentru că te poți convinge
că la
pasul următor, eu'  va
trebui să șterg
ceva oricum.
Schimbarea a fost gratuită.
Dacă schimb și șterg, este
același lucru cu ștergerea,
deci nu contează cu adevărat.
Deci, în special,
ceea ce înseamnă că
aș putea la fel de bine să
verific schimbul doar dacă
mă ajută cu adevărat.
Da?
Deci, cu alte cuvinte,
dacă am A--
acum trebuie să fii puțin
atent pentru că fac schimb.
Deci, dacă următorul tip din A
este egal cu B, tipul actual din B
și tipul actual din A
este egal cu următorul tip din B. Ei bine,
acum pot să schimb acest tip și să
opresc două rânduri din fișierele mele
în timp ce sunt la asta  , dreapta?
Deci, în acest caz,
obțin că X ij.  Ei
bine, schimbul nu
mă costă nimic
și am omorât două lucruri.
Deci aceasta este recursiunea.
Deci, dacă ar fi să scriu
asta pe teme,
ce ar trebui să fac?  Ei
bine, nu ar trebui... Adică,
probabil dacă folosești această
notație de eroare, nu cred că
ar fi mare lucru.
Dar într-adevăr, ar
trebui să adăugați o linie
în partea de jos care să spună
că pot alege
să fac oricare dintre aceste lucruri.
Deci, într-adevăr,
apelul meu recursiv este x
ij obține minul
tuturor acestor 1,
2, 3, 4 expresii pe
care le-am scris aici.
BINE.
PUBLIC: Ce se întâmplă dacă ai
prima condiție, dar nu și
a doua?
JUSTIN SOLOMON: Dacă am
prima condiție, dar nu și
a doua?
Ah, deci asta e o întrebare grozavă.
Da, deci întrebarea
a fost de genul, OK, ei bine,
dacă pot potrivi următoarea
linie, dar nu și cea actuală.  Ei
bine, sunt două
lucruri diferite pe care le poți face.
Ai putea fie să faci un
alt caz pentru asta.  Asta e
perfect.
De fapt, ai putea face asta.  Ai
putea să faci că am îndeplinit
a doua condiție, nu
prima, indiferent.
Puteți enumera
câte lucruri
doriți, atâta timp
cât toate sunt adevărate
și există un număr constant.
Alternativ,
vă puteți convinge
că de fapt nu este necesar
aici, deoarece un alt...
deci este ca o schimbare.
Dar apoi una dintre aceste două
linii este încă nepotrivită,
așa că va trebui să
ștergeți ceva
în pasul următor.
Deci, ați putea la fel de bine să
ștergeți mai întâi, mai degrabă decât să
schimbați și apoi să ștergeți.
Și de aceea acest
caz nu este necesar.
Da?
PUBLIC: [INAUDIBIL]
în primul caz.
JUSTIN SOLOMON: Exact.
Exact.
Deci, dacă ai schimbat și ai
ucis o linie, atunci, de fapt,
cred că este o combinație
de cazul 1 și cazul 2
aici, dacă, într-un fel,
extinzi recursiunea.
Dar dacă întâmpinați
probleme în a vă convinge
de asta, este în regulă,
adăugați un caz aici.
Da.
Alte intrebari?
Am de gând să întreb repede pentru că
această problemă mă face nervos.
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Sigur.
BINE.
În cel mai rău caz, dacă
am făcut ceva greșit, cu
siguranță puteți adăuga un
alt caz aici.
Mă voi gândi la asta acasă.
BINE.
Așa că, din moment ce am reușit
să pontific prea mult, să
continuăm să ne mișcăm aici.
PUBLIC: Le putem schimba
dacă [INAUDIBLE] se potrivesc?
JUSTIN SOLOMON: Oh,
știi, problema
este că s-ar putea să fi fost...
PUBLIC: --folosit
în fișierul final.
Deci, dacă puteți schimba
unul dintre ele și nu cu
celălalt, atunci nu este în regulă.
JUSTIN SOLOMON: Da, pentru că
la sfârșitul zilei,
dosarele trebuie să fie de acord.
De exemplu, trebuie să potriviți B cu A.
PUBLIC: Schimbarea și
ștergerea este mai ieftină
decât efectuarea a două ștergeri
și două inserări.
PUBLIC: Nu, nu, nu,
dar schimbul și ștergerea
sunt ilegale pentru că
trebuie să le folosești pe ambele.
Asta e o condiție
în buzunar.
JUSTIN SOLOMON: Oh, îmi pare rău.
Acesta este un răspuns mai bun.
Așa că Jason subliniază
că dacă schimb, atunci
nu îl pot șterge din cauza
felului în care este scrisă problema.
Deci,
elimină efectiv acest caz.
Altfel, cred...
Presupun că Erik este...
PUBLIC: De fapt, există
două condiții importante...
JUSTIN SOLOMON: Oh, îmi pare rău.
Am reușit să
greșesc total asta,
ceea ce nu este deloc surprinzător.
Da.
Deci, cred că problema mai
spune că dacă schimbi,
schimbul trebuie să fie util.
Și de aceea acest
caz suplimentar în
care Erik întreabă despre
unde schimbi și apoi
potriviți o linie, dar nu
cealaltă, este inutil.  S-ar
putea să vă relaxați
doar adăugând un caz aici,
dar din moment ce problema
nu o cere,
nu mă voi gândi.
BINE.
Dreapta.
Deci, în baza tuturor
ipotezelor acestei probleme pe care
nu le-am citit, dar care sunt
foarte importante pentru a rezolva corect
această problemă
, cred că
într-adevăr am
notat toate cazurile noastre aici.
BINE.
Deci, să continuăm cu
paradigma noastră SRTBOT.
Deci acum avem toată
recursiunea noastră.
Ordinea topologică aici este
puțin mai complicată decât în ​​mod normal,
deoarece acum aveți
o matrice bidimensională,
dar urmează un model
destul de tipic aici, și anume
că x ij
depinde doar de alte x ij
cu i mai mare și j.
Așa că mă gândesc la
graficul meu de subprobleme.
Dacă am scris asta într-o
matrice 2D, întotdeauna, cam așa,
arată în jos și în
dreapta, poate, ceea ce îl

face aciclic.
Acesta este un model foarte tipic
în acest tip
de
problemă de programare dinamică bidimensională.  În
regulă.
Deci, să vedem aici, SRTBOT.
Deci avem nevoie de cazul nostru de bază.
Acest lucru nu este prea rău
pentru că, în esență,
atunci când aveți
documente plictisitoare, acestea sunt
foarte ușor de asortat între
ele.
Deci, în special, pentru orice
i, dacă sunt la linia n plus 1--
cu alte cuvinte, am un
document gol pe care îl potrivesc
cu documentul i-- ei
bine, câtă muncă
trebuie să fac?
Trebuie să fii
puțin atent.
Aici versiunea sufixului
acestei probleme este puțin
mai enervantă decât
cea a prefixului --
sau am reușit să le schimb din
nou înapoi --
că, în special,
numărul de linii rămase
arată ca n plus
1 minus i,  care este
diferit de cel din problema.
Sunt doar eu pentru că
ei lucrează
în cealaltă direcție
, mai degrabă în soluție.
Și, în mod similar, aveți nevoie de un al doilea
caz pentru cei doi de aici, nu?
Deci aveți x n plus 1 j
va fi n plus 1 minus j.
Misto.
BINE.
Deci vom
continua cu SRTBOT aici.
Deci, care este cazul nostru original?
Prin definiție,
este x 1, 1 sau 0 0,
în funcție de modul în care indexați.
Și apoi, în sfârșit,
care este timpul nostru de funcționare?  Ei
bine, să vedem, există n
plus 1 subprobleme pătrat
și, desigur, este
egal cu ordinul n pătrat.
Subproblemele sunt doar
o cantitate constantă de muncă,
deci fiecare este
cu muncă constantă.
Deci întregul nostru timp de rulare
este ordin n pătrat.
Și sper că, urmărindu-mă
confuz în fața ta
și gândindu-mă la
această problemă, și tu
vei vedea cum
procedura de rezolvare a problemelor se
poate întâmpla în propriul tău
creier dezorganizat.
BINE.
Deci, asta încheie
tratarea noastră a acestei probleme aici.
Asta cred că este cel
mai greu.
Așa că celelalte două, din fericire,
sunt mult mai ușor de gândit,
m-am gândit.
Dar nu mi-a plăcut niciodată distanța de editare.  Îmi
amintesc că am văzut asta și
algoritmii de licență s-au
încurcat.
BINE.
Deci următoarea problemă, problema 3
aici, se ocupă de Saggy Mimsin.
Și ea are o grămadă
de blocuri și
vrea să le stivuească unul peste
altul, așa cum o face.
Și ca tânăr
inginer structural,
are câteva criterii cu privire
la problema ei.
Permiteți-mi să merg la
pagina potrivită în notele mele de aici.
Dreapta.
Deci, aceasta este problema 3.
Deci avem acel bloc bi are o
dimensiune care arată ca lățimea wi
prin înălțime hi cu lungimea li.  Îmi
amintesc că am fost confuz
în școala elementară
cu privire la diferența dintre
lățime și lungime tot timpul.
Pentru mine, acelea
au sunat mereu la fel.
Dar nu prea
contează, pentru că este
fericită să-și rotească cuburile în
orice mod dorește.
Există un detaliu cheie pe care mi-am
amintit să-l citesc
în această problemă, și anume
că ea are cel puțin trei
de fiecare tip, unde tipul
aici înseamnă că pot permuta
aceste trei numere în
orice mod
vreau, deoarece este același lucru
cu doar rotirea.  un bloc.
Dar de fiecare dată când are un
bloc care este ca 1 cu 2 pe 3, mai
are cel puțin două
în geantă undeva.
BINE.
APPLE WATCH: Este 6.
JUSTIN SOLOMON: Oh, 1 ori de
2 ori 3 este egal cu 6.
Mulțumesc, Apple Watch.
BINE.
Deci e ciudat.
Așa că își poate orienta
blocul în orice mod
dorește, ceea ce înseamnă că îl
poate roti în orice mod
dorește.
Și așa că ceea ce încercăm
să facem, ceea ce vrem
este înălțimea maximă la care își
stivuiește n blocuri.
Presupun că ar trebui să
spun că sunt n blocuri.
Așa că vrea înălțimea maximă pe
care o poate atinge.
Dar doar pentru a fi cam
enervant, sau pentru că, din nou,
este foarte preocupată de
stabilitatea structurală--
trăiește într-o
zonă cu cutremure-- și-
ar dori
cu condiția
ca fiecare bloc să fie strict
sprijinit de blocul
de sub el.
Dreapta?
Deci, cu alte cuvinte, dacă aceasta
este baza unui bloc,
atunci următorul bloc care este
stivuit deasupra acestuia
trebuie să fie strict conținut
în blocul de sub el.
Dreapta?
Deci problema are sens?
Am omis
detalii critice?
Nu cred că am timpul asta.
Acesta este puțin mai ușor.
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Oh, da.
Și ea nu poate face nimic nebunesc.
Ea nu poate face ceva ciudat,
cum ar fi, să echilibreze
acest tip
de lucru, care--
Erik are perfectă dreptate-- i-
ar putea oferi de fapt un turn mai înalt
decât ai putea obține
dacă ți-ar permite
să rotiți blocurile doar la 90 de grade.  .
Nu cred că problema
indică asta în mod explicit, dar aceasta
nu este o clasă de trigonometrie, așa că cred că
suntem într-o formă bună.
BINE.
Dreapta.
Deci aceasta este
problema noastră de bază aici.
Și aceasta este una dintre
aceste probleme care
va fi o
problemă de programare dinamică,
dar, din nou, asemănător cu
multe dintre lucrurile pe care le-am
văzut în prelegere, nu este
deloc evident cum,
pentru că, cumva, are
acest sac mare și dezorganizat
de blocuri.  .  Vă
puteți imagina
un univers în care
există 2 până la n
lucruri diferite pe care le-ar putea face, nu?
Pentru fiecare
bloc, ea ar putea
decide dacă
îl pune sau nu în stiva ei,
apoi trebuie să facă
o grămadă de alte lucrări
pentru a verifica dacă
le poate stivui
în timp ce susține
condiția strictă de suport sau nu.
Deci, inițial,
pare cam enervant.
Deci, ceea ce trebuie să
facem, ceea ce, din nou,
este destul de comun pentru
multe dintre aceste probleme,
este să punem o ordine în el.
Vreau să spun că atât în
sensul de entropie,
cât și, la propriu,
urmau să comande lucruri.
Și, în special, vom
vedea că această problemă are
multe în comun
cu cea mai lungă
problemă comună a subsecvenței pe care
am văzut-o în prelegere-- creșterea
subsecvenței, îmi pare rău.
Dreapta.
Deci, iată câteva observații
despre problema noastră
care ne vor ajuta.  În
primul rând, atunci când ne
stivuim blocurile,
am putea la fel de bine să aliniem întotdeauna
partea mai scurtă a blocului
de deasupra cu partea mai scurtă
a blocului de sub el.
Dreapta?
Lasă-mă să fac o imagine
a ceea ce vreau să spun.
Așa că să presupunem că am un cu adevărat...
un bloc a cărui bază
arată cam așa
și apoi un alt bloc
care este, de asemenea, dreptunghiular, pe
care îl așez
deasupra.
Atunci observă că aș putea... deci, în acest
caz, marginea mai scurtă a unui
bloc este aliniată cu
marginea mai lungă a celuilalt.
Observați că îl pot roti cu
90 de grade și
încă se sprijină unul pe celălalt.
Deci nu există niciodată un caz -- te
convingi
doar cu câteva inegalități -- în
care eu nu
pun întotdeauna partea lungă paralelă
cu latura lungă a tipului
dedesubt și partea scurtă
paralelă cu
tipul scurt dedesubt  aceasta.
Are sens?
Misto.
Deci asta e observația.
Observația a doua, pot
vreodată... să
zicem că Maggie de
fapt... îmi pare rău,
Saggy de fapt nu avea doar
trei blocuri de un tip,
ci cam 25.
Deci are doar blocuri Hella.
Întrebarea mea este dacă contează.
Răspunsul este nu, deoarece acest
cuvânt aici este cu adevărat critic, și anume
că există un
sprijin strict.
Deci blocul tău
are doar atâtea fețe.
Și, de fapt, prin
observație,
tot ceea ce contează este care
dintre cele trei tipuri de fețe
se află deasupra, pentru că
o putem roti întotdeauna.
Deci, există trei configurații
pentru fiecare bloc, deci, cel mult,
orice configurație poate
apărea de mai multe ori?
Nu, din cauza
condiției stricte de sprijin.
Dreapta?
În caz contrar, dreptunghiurile s-
ar potrivi
și asta contravine regulilor.
Deci, în special-- hopa,
numărul de după doi este--
numărul de după 1 este 2,
ceea ce arată așa.
BINE.
Dreapta.
Deci, în special,
există doar trei orientări.
Aceasta este doar care dintre cele
trei margini ale blocului
este cea care se îndepărtează
de podea, cea normală
la sol.
Și mai mult, fiecare poate apărea
mai puțin sau egal cu 1 dată.
Este bine pentru că limitează
dimensiunea problemei noastre.
Și, în sfârșit... hopa, am prăbușit
două dintre cazurile din notele mele
într-un singur caz aici.
Dar este in regula.
Și, de fapt, observă
că problema ne spune
că are cel puțin
trei de fiecare tip.
Deci, într-un fel, dacă problema...
dacă observați unul dintr-un
bloc, ați putea la fel de bine să
aruncați restul
pentru că știți că
îl puteți folosi de cel mult trei ori.
Și ea are trei din acel bloc.
Nu îl putem folosi de mai mult de
trei ori, așa că, într-un fel,
sunt doar informații de prisos
.
BINE.
Dreapta.
Deci asta ne permite să punem
puțină ordine
aici, pentru că observați că atunci când
mă uit la teancul de blocuri
de aici, ce știm?
Dacă mă uit la
lungimea laturii lungi
și la lungimea
laturii scurte în planul solului,
acele numere trebuie să scadă
la fiecare nivel al blocului meu.
Ele nu pot crește niciodată.
Așa
spun condițiile stricte de sprijin,
combinate cu
observația, de fapt, chiar și
fără observație,
ceea ce este o veste bună, nu?
Deci, acesta este ceea ce
ne va permite să impunem ordinea
problemei noastre, și anume, că
putem sorta după lungimile marginilor
pentru că știm că
avem această condiție de sprijin.
BINE.
Deci, să completăm câteva
detalii ale algoritmului nostru.
BINE.
Deci, inițial, deja putem
vedea că lista noastră de blocuri
este oarecum inutilă,
deoarece lățimea, lungimea
și valorile sunt sortate în
moduri care nu contează.
În plus, dacă avem mai mult de
trei dintr-un anumit bloc,
nu este cumva foarte util.
Deci, în loc de asta,
fără pierderi de generalitate,
să presupunem--
deci WLOG aici-- putem întotdeauna să
luăm blocul nostru și să presupunem--
Voi face acest lucru ușor
diferit de notele mele--
că lățimea este mai mică decât
sau egal cu înălțimea este mai mic
sau egal cu lungimea.
BINE.
Așa că fiecare bloc, dacă
nu este cazul, aș
putea să merg în jos în gama mea
de blocuri și să sortez.
Și sortarea unei liste de trei
numere este un timp constant.
BINE?
Dreapta.
Deci ce
îmi permite asta să fac?  Ei
bine, voi spune
că un tip de bloc este de fapt
un set ordonat în care
al treilea număr va
fi axa care indică în sus.
Și motivul pentru care
facem asta este că
știm că nu putem
folosi niciodată asta de mai multe ori
pentru orice tip de bloc.
Da?
Așa că acum voi face o nouă
listă de blocuri cu B majuscule
pentru că îmi plac blocurile.
Și va arăta
ca următorul.
Deci, dacă lățimea - deci dacă w este
mai mică decât h este mai mică decât l,
atunci voi
lua fiecare bloc
și îl voi duplica de trei ori.
Observați că s-ar putea să ajung
cu o listă cu, de exemplu, de nouă
ori pentru fiecare bloc,
dar o vom remedia mai târziu.
Dreapta.
Și va arăta
ca următorul,
adică, OK, voi
avea wi, hi, li.
Este ca și cum aș descrie o modalitate de a-mi
stivui blocul, deoarece
spune că aceasta este
partea scurtă, aceasta este partea lungă,
aceasta este partea verticală.
Și există trei cazuri în
care oricare dintre acești tipi
poate fi partea verticală.
Deci există unul.  Să
presupunem că h
este latura verticală,
atunci w trebuie să meargă înaintea lui l.
Deci ar fi wi, li,
hi, și un al treilea
în care al treilea tip este w.
H este mai mic decât l, deci ar
fi hi, li, wi.
Și acestea sunt toate
modalitățile diferite în
care pot, într-un fel, să orientez
aceste blocuri în stivuirea mea,
presupunând că impun
aici o condiție pentru comoditate.
BINE.  Voi
face o
nouă listă de blocuri în
care iau fiecare
bloc din setul meu original
și
îl dublez de trei ori în acest fel
după ce îi sortez coordonatele.
Și acum, ei bine, ce
trebuie să fac?
În primul rând, acest lucru
poate avea prea multe blocuri.  S-
ar putea să am un bloc care se
repetă de mai multe ori
și nu pot face asta.
Și mai mult, va
fi convenabil să
rezolv asta pentru că trebuie să-i
stivuiesc pe acești tipi în cele din urmă.
Da?
Așa că o să sortez lista.
Și vreau să o fac --
nu pot spune niciodată acest
cuvânt -- lexicografic,
ceea ce înseamnă că voi sorta
prima coordonată, apoi
a doua și a
treia lexicografic.
Observați că această lungime este de 3 n dacă am
avut n blocuri pentru a începe.
Deci, întregul lucru ia
ordine n log n timp, ceea ce
este important de luat în considerare.
Și apoi pot
elimina duplicatele.
Vă voi lăsa să
vă convingeți că
puteți face asta în ordine în timp.
O modalitate mai ușoară ar fi fost să
faci a doua matrice și doar un
fel de mișcare -
și să adaugi lucruri numai
atunci când nu ai
văzut același lucru înainte.
BINE.
Și, în cele din urmă, acum acestea sunt
ordonate într-un mod foarte frumos,
deoarece îmi pot stivui
blocurile, dar numai
uitându-mă la
dreapta în lista mea sortată
, presupunând că stivuiesc
de la vârful turnului în jos,
adică eu  Gândește-te, cam
ce se întâmplă în chestia asta.
BINE.
Așa că acum, în sfârșit, ne
putem face SRTBOT.
Și s-ar putea să fac S și R
și T și apoi vă permit
să vă gândiți la
restul pentru că, ca de obicei,
vorbesc prea mult.
BINE.  Așa că
acum aceasta începe să
arate ca o problemă ulterioară
pentru că, în esență, când
mi-am blocat blocurile, dacă
folosesc acest bloc aici--
din nou, dacă stivuiesc din
turnul meu de sus în jos--
toate blocurile care pot
Stați sub acesta
trebuie să fie mai la dreapta
în matricea mea din cauza modului în care
am sortat.
Asta nu înseamnă
că pot pune orice
în dreapta
sub tipul ăsta,
dar înseamnă că nu
știu că nimic din stânga nu
poate merge sub tipul ăsta.
Acesta este modul de a
gândi.
BINE.
Deci va fi SRTBOT.
Deci, S, ceea ce voi
spune este că x i aici
este egal cu înălțimea maximă
a turnului meu și o să-- mă

inspir puțin
din problema noastră ulterioară pe
care am văzut-o deja,
eu  Mă voi forța
să folosesc blocul i.
Vom vedea dacă este convenabil.
i și, eventual, doar
pentru distracție, poate vom
face versiunea prefixă a
acestei probleme de data aceasta.
Deci acum pot folosi oricare
dintre blocurile anterioare.
Așa că pot folosi primele
blocuri i pentru a face un turn,
dar sunt forțat să folosesc blocul i.
Apropo, de acum
înainte, când folosesc indici, se află
în această matrice sortată.
BINE.
Deci aceasta este o problemă.
Evident, dacă aș
putea rezolva pentru x,
aș fi terminat, pentru că aș
putea obține înălțimea maximă
doar iterând peste toate
x-urile și alegând aici cea mai mare
valoare posibilă.
Și întrebarea este, cum
fac asta recursiv?
BINE.
Deci, iată pasul nostru recursiv.
Deci, să spunem că
folosesc blocul i, ei bine,
pentru că știm că trebuie.
Dreapta?
Deci, în special, avem...
acum înțeleg de ce
nu au folosit această notație
în răspunsul lor, dar este în regulă.  Să
folosim o altă literă pentru a ne
referi la a treia coordonată.
PUBLIC: v i pentru
verticală [INAUDIBIL]..
JUSTIN SOLOMON: Da, să
spunem că v i este întotdeauna
a treia coordonată.  Am
folosit deja
w, h și l și mă
tem că dacă
le reutilizez după sortare,
va deruta oamenii.
Deci v i este a treia
coordonată a elementului i
al matricei mele sortate.
E în regulă, OK.
Corect, deci care este
înălțimea mea dacă folosesc x i aici?  Ei
bine, am ceva înălțime de la vi.
Și în plus
, primesc tot ce aș
stivui sub acel tip.
Deci, în special,
primesc că xi.  Ei
bine, înțeleg
înălțimea blocului
pe care tocmai am decis să o folosesc.
Și acum, care sunt toate cazurile mele?  Ei
bine, aș putea decide
să nu fac altceva,
cum ar fi să nu folosesc
alte blocuri.
Asta îmi dă o înălțime de 0.
Sau, ei bine, să vedem aici.
Aș putea folosi x-urile,
dar trebuie să am grijă să
le pot stivui.
Deci, în special, ei
bine, am nevoie de...
da, pot lua o
valoare x j, dar
trebuie să am grijă să
o pot lipi dedesubt.
Deci, în special,
ce știm?  Ei
bine, pot face orice
de la 1 la i minus 1
pentru că asta este un fel de
definiție a lui xi.
Dar, în special,
îl pot stivui deasupra.
Deci, o modalitate ușoară de a face
acest lucru este să fac doar matrice --
iterez prin primele i
minus 1 elemente ale matricei mele
și doar îmi verific
starea de stivuire
pentru fiecare
dintre ele în raport
cu blocul j, deci, cu alte cuvinte,
că lățimea și înălțimea--
sau mai bine zis, prima și
a doua coordonată
satisfac
inegalitățile stricte de care am nevoie.
Exprim această
propoziție în mod neutru
pentru că uit dacă aceasta
crește sau descrește.
Dar în orice caz...
deci ce fac?
Verific toate blocurile
pe care le-aș putea
stivui din indexul
perspectivei matricei.
Mă asigur că
le pot stivui,
datorită dimensiunii
blocului curent
pe care tocmai am decis
să-l adaug la stiva mea.
Și mă mișc recursiv.
BINE.
Dreapta.
Deci acest lucru este grozav
pentru că acum ne aflăm
exact în
scenariul recursiv în care am vrut
să fim, deoarece x i
depinde doar de x j, unde
j este mai mic decât i.
Și aceasta este exact ordinea
noastră topologică de
care avem nevoie.
Dacă faci asta la teme,
primești un minus n pentru n mare.
BINE.
În mod similar, care este cazul nostru de bază?
Ei bine, evident, dacă
am doar un bloc, aș
putea la fel de bine să-l folosesc.
Deci, în acest caz, avem x1 este
egal cu v(1) notația noastră aici
așa.  Cel
inițial, trebuie să fim puțin
atenți din cauza
modului în care am definit
x, deoarece x presupune că am
folosit un anumit
bloc, așa că trebuie să spun, ei
bine, s-ar putea să nu fi
ales de fapt  ultimul bloc
ca cel pe care vreau să-l păstrez.
Așa că trebuie să repet.
Pot spune că,
într-adevăr, originalul meu
este maximul peste i al lui x i.
Deci, unul dintre aceste blocuri trebuie să
fie blocul de deasupra.
Voi repeta
peste toate cele posibile
și o să le găsesc.
Și apoi ultimul lucru
de făcut este timpul de execuție t.
Acesta este ușor mai complicat
decât runtimele anterioare pe
care le-am făcut până acum
în problema noastră exemplu.
În special, câte
subprobleme există?  Ei
bine, există n subprobleme--
sau voi spune ordine n pentru că
sunt întotdeauna oprit cu 1--
corespunzătoare fiecărui
bloc din stiva mea aici.
Dar cât timp durează
fiecare subproblemă
, cel puțin așa cum am
scris-o aici?  Ei
bine, ce am de făcut?
Trebuie să fac bucla peste toate
blocurile posibile
și să-l găsesc pe cel pe care îl
pot stivui
și apoi să iau maxim.
Deci aici există o buclă de la 1
la i.  i este mărginită superioară de n.
Deci aceasta este ordinul n
subprobleme ori ordinea n
lucrează per subproblemă.
Deci, la sfârșitul
zilei, algoritmul meu va
fi ordin
n timp la pătrat.
Și, bineînțeles, din nou--
cred că am promis-o și
apoi nu am făcut-o de fapt--
pentru a implementa efectiv
acest algoritm,
există un fel de două
moduri diferite de a face acest lucru.
Aș putea scrie un
apel recursiv plus un tabel.
Tabelele pot fi inițializate
la o grămadă de NaN.
Și apoi implementez această
funcție în mod recursiv.
Dar înainte de a face asta, spun, dacă
tabelul nu este egal cu NaN,
returnați doar
valoarea din tabel
și, altfel, numiți
această recursivitate.
Sau pot avea doar o
buclă de patru de la 1 la n
și să construiesc tabelul câte
un element.
Și ambele
sunt exact aceleași
din perspectiva runtime.
BINE.
Așa că cred că am reușit
să urmăresc asta mult
mai mult decât notele mele sau
soluția scrisă,
dar problema
în sine este de fapt
destul de simplă.
Deci, dacă citiți
răspunsul și câteva dintre...
Cred că, de fapt,
părțile grele ale acestei probleme
nu au fost
programarea dinamică, ci
toate observațiile de care
aveți nevoie pentru a ajunge acolo.
Așa că de aceea am petrecut
puțin mai mult timp acolo.
BINE.
Deci, ca de obicei, nu
mi-am lăsat suficient timp
pentru ultima problemă.
Dar avem câteva
minute și vor
fi suficiente pentru a
configura piesele.
De fapt,
ultima problemă a
fost mai ușoară, chiar dacă din punct de vedere
tehnic este, un fel,
două programe dinamice într-unul.
Deci cred că logica
este puțin mai ușoară.
BINE.
Deci
PUBLIC: Folosește
panoul [INAUDIBIL]..
JUSTIN SOLOMON: Cred că
acesta este panoul.
Da, tocmai îmi dădeam seama
că această cameră nu funcționează
la fel ca cealaltă.
Da, e jenant.
Știi, mi-am petrecut toată ziua
gândindu-mă la topologie,
iar aceasta este ca o
problemă clasică în acel univers.
BINE.  Ei
bine, vom șterge
o tablă la un moment dat
și voi încerca să nu scriu de
data aceasta lățime de trei picioare.
Oh, aceasta este probabil
singura placă pe care nu ar trebui să o folosesc.
Nu cred că îmi
place această clasă.
BINE.
Deci, corect, în problema noastră finală, ni se
oferă o grilă n-cu-n.
Și pe grila noastră n-by-n
, Princess Apple--
Banana--
PUBLIC: Prune.
JUSTIN SOLOMON: --Prune.
Prințesa Prune.
Corect, deci iată
configurația noastră de bază.
Există o grilă mare de
lucruri, sau poate o grilă mică
pentru că nu am chef de
desen.
Și fiecare pătrat de grilă poate
avea unul din trei lucruri.
Putem lua o ciupercă.
Putem avea un copac.
Sau nu poate avea nimic.
Și prințesa noastră începe
aici și pleacă...
vrea să meargă acolo.
Și mai mult, există
câteva lucruri
care merită remarcate aici.
Deci, în primul rând,
calea ei este rapidă, ceea ce înseamnă
că poate traversa doar
2n minus 1 pătrate de grilă
pentru a ajunge dintr-un
colț în altul.
Și, se pare, îi place
foarte mult ciupercile
și și-ar dori să acumuleze
cât mai multe
pe calea ei.
Aceasta este configurația de bază aici.
Așa că vrea să ajungă din stânga sus
în dreapta jos.
Și, pentru a face acest lucru,
vrea să ia o cale rapidă.
Prioritatea ei principală
este să fie eficientă.
Dar printre
diferitele căi rapide,
ea vrea să culeagă
o mulțime de ciuperci.
E de înțeles.
PUBLIC: Și nu te
plimbi prin copaci.
JUSTIN SOLOMON: Și nu numai
prin copaci, mulțumesc.
Așa că poate că există
niște pătrate de grilă
care sunt marcate cu un
copac, ceea ce înseamnă că pur și simplu
nu poți merge acolo.
Acesta este un copac.
BINE.
Corect, deci aceasta este
configurația noastră de bază aici.
Dar problema... este
nevoie de
o întorsătură, nu?  Nu
înseamnă că ar putea
fi cea mai scurtă cale, care
ar fi foarte asemănătoare cu
ultimul tip de unitate din 6.006.
Dar, mai degrabă,
întrebarea este, într-un fel,
care este numărul de căi
pe care ea le poate lua dintr-o parte
în alta și care este
numărul maxim de ciuperci, este
aproximativ întrebarea pe care o
pune, sau cel puțin
ce îmi amintesc din
citit-o.  aseară.
PUBLIC: numărul de căi
care maximizează același număr.
JUSTIN SOLOMON: Așa este.
Așa că trebuie să ia cel
mai mult număr de ciuperci pe care îl
poate, dar poate exista
mai multe căi care să
te ducă până acolo și care să
fie rapid, care
să îndeplinească această
condiție, caz în care,
ea dorește numărarea
numărului total de moduri prin care
poți  mergi dintr-un
colt in altul.
De ce, ați putea întreba...
de ce nu?
BINE.
Deci, corect.
Deci, de exemplu, poate că
este o ciupercă aici.
Acum există o
cale rapidă care o duce acolo
și adună o ciupercă.
Deci există exact unul.
Dar poate dacă există o ciupercă
acolo, ei bine, inițial,
se simte că poate ar
putea obține două ciuperci.  Ar
putea merge acolo, merge să
culeagă a doua ciupercă
și să se întoarcă.
Dar vom vedea că
această condiție rapidă permite de fapt...
nu
vă permite să faceți asta.
BINE?
Deci, de fapt, se va dovedi
că căile rapide pot
colecta doar o ciupercă
în acest caz de 3 pe 3,
deci există cel puțin
două căi diferite.  Ei
bine, există 1,
2, 3 moduri diferite prin
care ea ar putea colecta o
ciupercă și să aibă o cale rapidă.
BINE.
Așadar, primul lucru de
observat este că instrucțiunile
sunt puțin cam furioase
prin definirea unor căi rapide,
practic,
fără a-i lăsa deloc slăbiciune.
Dreapta?
Și iată o observație de bază.
Observați că pentru a
da din stânga sus
la dreapta jos,
ea va trebui să
meargă în jos și la dreapta.
În mod plauzibil, ar putea să urce și ea.
Ar putea încerca să ocolească
un copac, dar numai în mod plauzibil.
Și, în special, întrebarea
este de câte ori
trebuie să coboare și de
câte ori a
trebuit să meargă la dreapta.  Ei
bine, ea trebuie să ajungă la
partea de jos a grilei.
Deci ea se află pe
pătratul numărul 1.
Trebuie să coboare, în acest
caz, de cel puțin două
ori, deci, în general,
n minus 1 ori.
Ea trebuie să meargă la
dreapta n minus 1 ori.
Deci ce înseamnă asta?
Ea trebuie să facă
2n minus 2 mișcări.
Și asta e o limită inferioară, nu?
Deci, dacă urcă, va
trebui să coboare din nou,
așa că o va
face doar mai mare.
Dreapta?
Deci, cel puțin, trebuie să
facă 2n minus 2 mișcări
în jos și la dreapta pentru a ajunge din stânga
sus la dreapta jos.
Câte pătrate
atinge când face asta?
Aceasta este o problemă cu stâlpul de gard.
Așa că a făcut 2n minus
2 mișcări și a
avut un loc de unde a început.
Asta înseamnă că doar
deplasându-se în jos și la dreapta,
ea face 2n minus 1 pătrate -
mai degrabă atinge.
Deci se poate ridica vreodată?
Nu. Se
poate muta vreodată la stânga?
Nu.
Și, practic, asta este tot ce ai
nevoie pentru a rezolva această problemă.
Restul este
de fapt destul de ușor.
Deci, observația de bază aici
este că ea se poate mișca doar în jos
și la dreapta, deoarece dacă s-ar
deplasa în sus sau la stânga,
drumul ei nu
s-ar mai spune rapid
și asta ar fi o problemă.
În plus, fiecare potecă care se
mișcă în jos și la dreapta
este o cale rapidă, presupunând că
ea își atinge ținta
și nu lovește un copac.
BINE?
Deci asta este observația de bază.
Și observați că asta
deja sugerează, practic,
ca să vă țip,

cum să faceți programare dinamică
pentru că, literalmente, aveți
o masă care se uită la tine pe
tablă chiar acum
și aveți o comandă în
jos și la  drept care
este aciclic.
Da?
BINE.
Am trântit de
destule ori pe tablă?
Prima dată când am
predat la Stanford, am
primit feedback negativ asupra cursului
că am băut prea multă cafea
și că trânteam
mult pe tablă, se pare.
Am vizionat videoclipul mai târziu și,
într-adevăr, nu a fost greșit.
BINE.
Deci, corect.
Deci, vom numi k--
acestea vor fi
ciupercile maxime pe care le
poate obține pe toată
calea din stânga sus
în dreapta jos.
Deci vrem să știm
numărul de căi rapide
care pot atinge acest număr k.
BINE.
Deci haideți să facem SRTBOT foarte repede
pentru că am patru minute --
de fapt, puțin mai mult decât
atât pentru că am început târziu.
BINE.
Acum, genul de
enervare aici este
că există două
numere diferite pe care nu le știm.
Unul dintre ele este k, iar
celălalt este numărul de căi.
Problema nu ți-a spus
câte ciuperci poate ridica.
Îți spune că
există o cale
de a ajunge din stânga sus
la dreapta jos,
că nu este doar
un șir de copaci
undeva, pe care îl simt
uneori în naveta.
Dar nu-
ți spune numărul pe
care trebuie să-l realizeze.
Și, inițial, asta e
cam enervant.
Deci, poate că primul
lucru pe care îl facem
este doar să calculăm k, de
exemplu, numărul maxim
de ciuperci pe care ea le poate
colecta pe orice cale rapidă.
Și apoi ne întoarcem și
calculăm celălalt număr.
Aceasta ar fi o
abordare de rezolvare a problemelor la
care ne-am putea
gândi puțin.
Deci, în special, să ne definim
k ij ca fiind egal cu... ei
bine, putem generaliza
problema noastră ușor
și să spunem care este
numărul de ciuperci
pe care le pot obține pe orice fel
de dreptunghi încorporat
în întreaga mea problemă, corect  ?
Deci, cu alte cuvinte, acesta este
numărul maxim de ciuperci,
sau m pe scurt, pe
o cale rapidă către ij.
Deci, cu alte cuvinte,
începe întotdeauna în stânga sus,
dar acum se oprește la
orice altă celulă grilă.
BINE?
Pentru că nu mai am
timp...
nu, voi face asta
așa cum vreau eu.
Nu, așa că ne vom
gândi doar la k.
Da?
Deci întrebarea este dacă
putem calcula la fel
ca valoarea k, ceea ce cu
siguranță pare convenabil.
Prințesa Prune, ar putea la fel de bine să-
și cunoască inamicul.
Ar putea la fel de bine să știe
numărul de ciuperci pe care îl
țintește,
dacă îl poate obține.
Deci, cum am putea face
asta recursiv?  Ei
bine, trebuie să
ajungă în poziția ij.
Și din argumentul nostru de
acolo sus, ea
trebuie să ajungă acolo fie
venind de sus, fie din stânga,
așa cum am ales noi să
scriem această problemă.
Deci, care sunt cazurile noastre diferite?  Ei
bine, în primul rând,
dacă există un copac,
nu poți face nimic al naibii.  Nici
nu ar trebui să
poată ajunge acolo.
Și pentru comoditate, vom
descoperi că puteți
argumenta că este 0. Vom
marca acest lucru
cu un număr special
și vom vedea că
asta face notația noastră
puțin convenabilă.
Deci, una este, dacă
există un copac,
atunci vom spune că
k ij este minus infinitul.
Din nou, există o
întrebare filozofică acolo.
Primește minus
ciuperci infinit
dacă stă
în vârful unui copac?
Nu știu,
pentru că nu ar trebui să
stea în vârful unui copac.
Dar cel puțin
ne va anunța că ceva nu
a mers prost în acest
pătrat de grilă în celelalte părți
ale recursiunii noastre.
BINE?
Și în rest, ei bine, care
sunt cazurile noastre diferite aici?
Ei bine, ea ridică întotdeauna
o ciupercă dacă este acolo.
Ar putea la fel de bine.
Ea maximizează.
De fapt, problema chiar
spune că îi place foarte mult
ciupercile.
Ea le colectează
automat, nu?
Deci ce primim?
Folosesc
notație inutil de fantezie.
Acesta este un indicator al
existenței unei ciuperci
la poziția ij, adică
acesta este un 1 dacă există
și există un 0 dacă nu există.
Uneori, acest lucru este indicat cu
un 1 cu un mic indice,
dar orice.
În plus, s-
ar putea să fi cules
ciuperci de-a lungul potecilor.
Și știm că drumul ei
către poziția ij
venea fie de sus, fie de stânga.
Deci, cu alte cuvinte,
știm că
ar fi putut obține maximul
din orice potecă care se termină deasupra ei
sau din orice cale din stânga ei.
Deci este k i minus
1j, care, cred,
este la stânga, și k
ij minus 1, așa.
Și aceasta poate fi folosită pentru a completa
întregul nostru tabel cu k valori.
De fapt, din moment ce am
puțin timp,
vă voi lăsa să faceți TBOT pentru
restul acestei probleme.
În esență, cred că
observația cheie este aceasta.
Evident, când
începe în stânga sus,
primește 0 ciuperci
pentru că nu
stă deasupra uneia.
Problema spune asta.
Și acest lucru ne permite să
completăm întregul nostru tabel k.
Deci, în special, asta ne
dă dușmanul nostru acum.
Știm acum câte
ciuperci ar trebui să aibă
la fiecare pas al călătoriei sale.
De fapt,
ne spune puțin mai mult
decât atât, deoarece
spune că dacă mă aflu la acest pătrat de rețea--
la acest
pătrat de rețea în timpul drumului meu, ar
trebui să am atât de
multe ciuperci.
Dacă nu am făcut-o, atunci
ceva a mers prost.
Da?
Deci, modul în care
este scrisă soluția,
ei fac două bucăți din
recursivitate simultan.
De fapt, ai fi putut
rezolva mai întâi această matrice k
și apoi să te întorci
și să faci a doua jumătate
a acestei probleme.
Și acestea sunt exact la fel.
Și când îmi
scriam soluția,
așa m-am gândit
la asta, pentru că, într-un fel, am
simțit că ea
ar putea la fel de bine să știe
câte ciuperci vrea
să adune înainte de a începe să
numere cărări.
E ca o
întrebare secundară, știi.
Și deci acesta este o modalitate de a face asta.
Deci, în cele
2 minute negative rămase, să ne
gândim la
recursiunea pentru calcul.
Amintiți-vă că vrem să știm
numărul de căi necesare
pentru a colecta atâtea
ciuperci, numărul maxim
de ciuperci.
Vă rog să nu existe o
mulțime de lucruri pe această placă.
Ah, nu sunt
lucruri pe această placă.
Grozav.
BINE.
Deci, în special, acum
voi defini un al doilea lucru
pe care și eu voi
face programare dinamică.  Voi
spune că x ij
este egal cu-- și voi
face
aici o definiție furișă,
care este numărul de
căi rapide care se termină la ij cu--
acum, să anticipăm
problema noastră a  un pic.
Deci, la sfârșitul zilei,
vom face x din n comandă
pentru că ea vrea să ajungă până în
jos și la dreapta.
Și câte ciuperci
vrea să aibă,
acum că știm k?
Ea vrea să aibă k din
n virgulă n ciuperci.
Pe parcurs, ar
fi cam ambițios
dacă ar vrea să
aibă k de n
ciuperci de comandă pe tot drumul.
Dar ar fi puțin mai
puțin ambițios să avem
k de ciuperci ij
pentru că, într-un fel, asta este
exact ceea ce tocmai am construit
în lucrul anterior
unde erau poteci.
Ei bine, ultimul tip
arată ca un max.
Acum ne vom aștepta
să vedem câteva semne plus aici,
deoarece însumăm
câte poteci avem.
BINE?
Și acum să venim cu o
regulă recursivă pentru tabloul x
și apoi o vom numi o zi.
Deci, în special, [INAUDIBLE]
unul, dacă există un copac,
câte poteci sunt?
Nu există căi,
pentru că nu pot ajunge acolo.
Deci, ij este egal cu 0.
OK?
Altfel, nu există copac.
Și acum trebuie să fiu
puțin atent, nu?
Așa că trebuie să scriu asta
ca pe o mică bucată de cod.  Ați fi
putut scrie asta ca
un max uriaș, în schimb, sau o grămadă
de cazuri și orice altceva.
Deci, să ne gândim la asta
ca la o bucată de cod.
Deci, inițial, cred că
nu există poteci care să
mă k ij ciuperci.  Asta e
perfect.
Și amintiți-vă,
vom continua să
aplicăm aceeași
bucată de logică, și anume
că o cale poate
veni doar de la stânga și în sus.
Și să ne gândim la
aceste două cazuri.
Și apropo, vom
folosi chi
pentru a egala acest chi
de lucruri pe care le-am
avut în expresia anterioară.
Deci chi este 1 dacă există o
ciupercă în acest loc
și 0 dacă nu există.
BINE.
Deci calea mea poate veni
din stânga sau în sus.
Știu că nu poate veni din
sus dacă numărul de ciuperci pe
care le-am luat din sus plus,
potențial, cel pe care l-am primit
aici nu se aliniază cu
numărul de ciuperci
pe care ar trebui să le am
după standardul k ij
pe care îl  am stabilit pentru mine.
Deci, dacă vreau să scriu asta
în cod, modul în care fac asta este
aș spune, dacă k of--
deci să spunem că mă uit
mai întâi la stânga.
Este ca, știi, uită-te în
stânga ta, uită-te în dreapta,
unul dintre voi va trece acest
gen de scenariu de examen.
Și pot adăuga o
ciupercă la poziția mea actuală,
dacă există.
Dacă este egal cu k ij,
ei bine, ce înseamnă asta?
Asta înseamnă că potecile
care mergeau spre stânga
au putut colecta numărul
de ciuperci de care am nevoie pentru a ajunge
la poziția în care sunt acum.
Așa că acum pot adăuga toate
modurile diferite.
Poate voi face un plus
egal cu x din i minus 1j
pentru că orice cale care
a ajuns la tipul anterior
și a colectat
numărul potrivit de ciuperci
poate ajunge acum la mine și obține
numărul potrivit de ciuperci.
Și, în mod similar, pot să mă uit în sus
și să fac exact aceeași logică.
Deci, dacă k din ij minus 1 plus
acest număr este egal cu k ij,
atunci x ij primește un
număr suplimentar de căi, așa.
Și acum cred că merită să
petrec 8 secunde gândindu-mă
la cazurile noastre de bază
aici, pentru că, inițial,
când am văzut asta pentru prima dată,
am intrat puțin în panică
pentru că se pare că
asta ar ajunge doar prin a
primi o grămadă de 0
pentru că eu"  m doar adaugând
valori ale lui x la ei înșiși.
Nu am
un 1 plus nimic
nicăieri, ceea ce e cam
ciudat dacă te gândești la asta.
Deci, tot motivul pentru care
apar numerele pozitive
în această problemă provine din
cazul de bază, ceea ce cred că este destul de grozav
.
Acesta este, cred,
unul dintre aceste lucruri în care,
dacă ai anticipat o
problemă, atunci este grozav,
iar dacă nu ai anticipa
problema de la început
și ai
notat aceste formule,
probabil nici nu te-ai
gândi că  e interesant.
Dar, în orice caz,
care este cazul nostru de bază?
Deci, vom face B în SRTBOT.
Deci, în primul rând,
ce este k din 1, 1?
Amintiți-vă, acesta este
numărul de ciuperci pe care le
poate colecta
pornind de la pătratul din stânga
și mergând nicăieri.
Și acesta este 0 pentru că
problema spune că
nu există ciuperci în stânga sus.
Care este x din 1, 1?  Ei
bine, acesta este
numărul de căi de la 1,
1 la sine care adună
0 ciuperci, deci este 1.
OK.
Și cred că
restul tabelului SRTBOT
de aici nu este îngrozitor de
greu de completat.
Așa că am observat că într-un
fel amuzant,
toți acești
pași recursivi adaugă doar 1
la sine de câteva ori.
Dar, desigur, felul în care
faci asta, motivul pentru care
obții un număr
care este interesant,
este din cauza tuturor acestor
afirmații if și a faptului
că poți adăuga două
plusuri diferite provenind
din două surse diferite.
BINE.
Așa că vă încurajez de fapt

să priviți codul din
soluția problemei,
deoarece cred că este un
exemplu frumos de a lua
această formulă recursivă și
apoi de a o derula,
cum ar fi, repetarea peste un tabel.
Și aceasta este o abilitate utilă
pe care intenționam să o fac astăzi
și apoi nu am
făcut-o cu mare atenție.
Dar cu asta, ca de obicei,
am trecut peste timp aici.
Așa că o vom chema pentru ziua respectivă.
Și mă voi vedea
când vă voi vedea.  În
regulă.