Scribd
Upload
39 views47 pages

Dynamic Programming

Uploaded by

guptaaman0409
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
39 views47 pages

Dynamic Programming

Uploaded by

guptaaman0409
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 47
classmate Lecture $ 69 Dynome Pp a dp _kaam €k boar kar Bute Cae pase falco - Fibonace’ series 2 fer) 20, 4, 4, 2, 398/803, 2h, FEE Dynomic programming problem can _Selved in -fuo ways? + Nemoizaton ©) Fep claw Pipa © Tabstaon (eatin poppin) Amara : oa (loop) ___ Space optimization. nt frbanoee number 3 fir) = Pema + fines) Bae ne S F(2) Re amis paint We use our F(e) = 0 Lo NIZZ post Memory pecause ED ea) 3 £Cu) Ine solved FC2) v\S Previously 24) VEC2)) C Fea), ro : 2fo) 140 vN Fu Fw Y 0 Divide ANd Conquer ly DP ke proviem Ko pohle divide korte Joo OF uake baad usko ex Ge Kar Ke Jodte Joo. Overla pping Subproblen 5 Je problem Ka part solve kar chuxe hai Usko _dubara Solve noni Karo, Memory me Store S Karun Kar ako direct use kar lo. Before Dp * Aver bP erm 2234 a Fon N= 10 fr 4 =10 a= Ga) S iN t L See the diPference Of bor How +2 Store Re Value whith We calwloted previowly9 Maxe an affay OF size (as) FC> b&b ort) gaitially out Sik ony fcc me) FO) =a st value in each _step classmate aaa oO VS ist ea + 2 eai=3 a a Pet = cy ae TNE TSN =! 3144 OUO@®s TIERS 1 SENOOR Io § oo g = Tetum > a Ways = & ae Nef Vata fefarn 6 —— i n==5 _ Cedurn 1 5 — ars fetum 0 3 i es ete’ 6) era eg) YV Ee me a) Io = ee YES = © WY OES ESS pe 1 XO Pen) = _@ ent) + FCn+2) Qh => ferum 2 >A = fetum 0 classmate Bottom up Approach 8 eas nein be i = mae = 2414) =4 aro % 2{e Ve ' o AC sir G)o a K i se a Ac 3 Arfeady) Calculated, & oO code 2 long long _CountWays Lint _n) ( 9 op Vector < long long) dp (n+); dpind = 1) dpins = 0; Apins 2} = 0, foe Cint i= n-1; i>=0,; ED Spe ES RL sate Xaplits]) fe \o0000g00F; 3 feturn apie; 5 int find Cint rndex , Vector = 9) | Peturn 0} fetarn max (nums Lindex) + find Cindex +2, nums, n), Sind Cindex +1, nums, 9); int rob (vector = 9) Ceturn 07 cerurn find Cindex , amount Coins Lindex], Coins, 0) + eee *+\) amount, Coins , %)/ ink change (int amount, Vector £ coins) ¢ im \= Coins. sized) fetum fmdC Or Amount, Cons, 9+ | mee OS classnate ~ Dynamic _progomming _Appsoach * i Ta Gia dlassn Approseh) ~. We use Qp pp hee® cal ~ access 9 wate Cine LNG Sa ~ )_ index i 2) Armourt eS va S aaa Se ~ Fer storing the caleulate “value tle _ Woe : — ab Array here 8 eo becouse fir index = tthe Value Oh “— amwn Nes lw a> te 5 - == RA So,We we ad _— firroy! [= index 2 0 ® 2 4 J nm.) ~~ Matix (SxO fequired. Qndex 3 > O-Q “) M+!) Amougt $ Amount + | BD Dp Size % (nay) % Camount 41) We understand With an Examples eins. ¢ Up DSi Amount = S |code 2 Cop down Approach ) classmate ik Comount_ == 0) feturn 1; ub Cindex < 0) (eturn 0; uf Cap LindexJ LamountJ j= -1) feturn — dpLindex] amount) » ig (Coins Lindex] > amount ) 1 Fefurn ApLindexILameum] = find Cindex I, Amount, Coins, dP); else { fekarn dp Linder] amount) = find (index , amounts Coins Linderd, Coins, Ip) + find (index -1, amount, Gins, dp); j int change ( int amount, vector £ Coins) f int 0 = Coins.srze0)) Vechr Cvector< int)) dp (n+), vector cint> Camount +1, =e feturn find (n-1, amount, Qins, dlp); amoun Ne as an re] Las Ys] Soe ‘ 7 i oe cas = ~ = a. Cn SRS On iis a2 aa da Add Ad: C a o i " ae Siuciem cite i exist 4 cae ae fd Ph a . a Sie ca : Ie 1E £4 | Ser a a DSSS = se c 2 +e is Xin | Xe a ee oa i vey a a att 7 a Finol_ answer = 4 a coded w ie ime _chanye Cink amount, Veelord ints L Goins ) { i wt N= Goins. size; ~ ue Vector < int) dp Camount + 4, 0); a APpLed = 4; a ye fer Lint i= Veni tana) . fer Lint 3 = GinsLi=1]) 3 \ fedtura dp Lamounsy; Count _Woys to Nh Stair (Order does mot matter) => Mere are _N_ Staitss => person Can Clim (1, 2,45, {201,14 (1, 2) are Considered Qs same. aa Becowe ohrequen AZ 2 ase same in On. int index, int a, int Steper) f a >n return, ad Lindex -\, 9, saep)> else (etut Bad (index, o~ step Cinder ~0, step) + od (index -1, 9, step) > int cwdstair Cint a) ( int srepL2d = (11245 Pefurn od C210, step); nT PEE 80 fh _ problem 4 2 values chanjee 4 index & © So, 2D Dp __ required here cas Down roach (lode) o.| _ int ind _Cint index, iat n,_ int Spl, vector vector < iotss£eP) { if (9 == 0) fefurn 41; Cindex == 0) fetum 0; dp Lindex][n]J J= -1 fefum dplindexICr1; sep Lindex -1] ) 1) feturn dppLindexd En] = fod (soder 1, 0, step, dp): else fetarn dp CinderxI[a]= find ( index , A step Lindex ~ 1], np) + fiod(inder-1, 0, step, dp) 4 [a int _ntStair Cit 0) £ int stepC2J= [11 2}; Vector

You might also like