* Dynamic programming

. How to identify whether a problem DP

optimal 5ubstructare
i: check for recutsion |
Rerursive cquntiomne
choice
L- Repcattd funcion cals
2) optimal so| is a6ked.

* 5tamdaid Questions om Dp
o- knapsack (6)
Unbound et knnpsack (5)
(3) Fiboma cci () Parent problem
eLcs (15)
6) LI6 (10) VI V2 V3 Vy i Varjations

(6) Kadane's Alqprithm C6)

Matrix chain Mutiplication C)
8 Dp om Trees (4)
( Dp on Grid (14)
1)
(10) Othevs (5)

Notc: Memoization
Recursive codc
S Top down
 O-1 Knapsack problem. ’parent problem
) 6ub6et bum
O Equal 5um partitfom
(3 count of 5ub5et 5um
child probl em
(9 Minimum 5ubset sum diff
) Tarqet sur
6) Number of 6ubset & given difference

* O-1 Knapsack problenm

choice - Take / donlt taKe the object
optimal - Max profit
Recur6ive cqn :
pnm)’ Maximum profit for n-objecs and
m
capcity kna psack.

Pnm) pln-,m) Wnm

max(p- ,m-wa) p; Wn<n

*Identification of knapsack problem. (Krap5a Ck pattemJ

choose sone ite ms to maKe W

choiceJ
TEvay irem has chstee]
X
 2 9 4 5,
Ar-f3.34,4,12,6,2y
Sub6et 6um problem
O
6um
L 6
2

F 3
F F
T F D IF F|F 34
EF|F
F|F F
TFE

Felnmts TE|F
F T
T
FF
T E E T I F
F F
E 12 S543
S3,4,23
2 ways
5 TFF
TFTTTTT|T

dpli-JCj-arti]) l| apCi-lJJ
T d o t t T r
iz =
F
T
possibe
pos5ible oR not
is
6um
eiements bf arr.
dp[J4J’uuith
Yirst x
c=0
>0 and
F xangthing .
dp[zity)=5 ;y=0 and
T
ar[x-1) >
dp[x -i]ly] i
dpl-) y-ant 0))
(apbe-lly) |
 problem
Equal 6um pntitton divide the Arra4 into tuo 6ub6et5
[is it possibie to 1
6uch that y Sum [Bubset i] Sum [6ubsetz]
Loqie zf( bum(arr) odd )' euan Fauc,:
is odd.
ie If the 6um at of al elements ofintoarra
tw8 subscts
thn we can't divide the arreuy
having qual sum.
Ff ( sum (ar) even)
Sub6et 6um( arr, Sum ) )
(suncans/a)
If [um(arr) = 46
problem to Subsct Sum
Lwe can reduce the

Su bset6um (arr, 46|2 ) im thc

Mcans f 5ubsrt ith sum = 23 i5 prcsem
Sum 23
qiven array then we can have 2 5ub5ct5 having
in the qiven array
3) count of 6ubset 6um
x dement
with
6ub6cts possible
Loqic 3
dpx]iyl whose Sum i5
dp[o]Ty] = o :or y>1
dpl]to] =1 ; For 20
aplx-JEy-avta-0)+ dp[r13y]
when, arr [x1] s }

when arr Ca-] >t

** comtaims zero clement6"

NOte Sprciad case &- when arYay
Refer Lperfect bum problem JJon gfg

difference
(4) Mimimum 6ubset bum two Sub5ets Such thar
array imto
L Divide the qiven S| 52
abs(Gum(6i) - Sum(62))> Minivmurm for equal
we made
MaKe same Dp table
Loqic panitiom problem. right -’let
(mh row) frorm
last row
thm travclJC the
bccuse ab5[ 5um (5) - 5um (52)] Minimum
e Kample - 5um 5um [Link] clements m’elemcuts.
of arra
2
-Sumla.

Ttot
Let -Righe
ditf((6um-)-)’Mininnum
 qiven difference.
mumbey of 5ubset pairs ueith a
() count the diff 9
L#(sum(5) - un(ba) ) -
6tbsct5 5 and 52
Loqic 3 LWe havC two
Such that
-diff
Sum(51) - Sum(s3)
We Kno
[um(5) = Sum(arr) ’ )
Gum(6) 4+

[Link] (61) =
= ditf +buman)
diff + 5um(arr)
5um(s) =
2

Combtamt
problem mto
Thcs, u have cduced the qiven
"subsct 5um' problem.
a r y whose sum is
qiven
No-of 5ubset6 mm the given anay
le to count
[diff t sum(arr)
2

5um
Tarqet
Given an arrCN] and
taqet
arr 6uch
that
im
in
siqns I t oR -] to cach intqer
Aseign
thier 5urn quals to tasget can assiqn signs
Count in haw many different ways gou
to arr integers.
talget
-1+1-213 ’ 1
 reduce this probiem
We cam rduce Imto previos prob lem.

sabsee
Target G u m # prirs ith qiven differen
Subset 5um
 Unbound ed Knapsack >paent problem

ORod Cutting problem child

Number of ways
coin chanqe problem : Max of coins probiem.

change prob|em : Min Number

Com
4) Maximum Rtbbon Cut

* Unbounded Knapsack. can take

ans
unbounded, means you
y The count of itcms i6
the itenm ang NO- of times.

to Knap5ack problem .
Approach is almost 6imila) an item
don't tare
yTaKC f you Come back on
you uerll never
item
oon't tarsel that itenm again.
itm 4o
TF you tare the
Taxc y to take it
Don't take

m-objects cind
Recursive eq':pn,m) Marimum profit for
m-capacity

Wn m
pm) = p-m) :
Wy m.

Ff you,take the
jHem
Thy to tarc ft
 mumber of
O Rod cutting problem of pricest ).
9 coin chanqe
problem : Marimun different
Griven a rod of length N ary
mches and an Coins Cw] represenma
sum, Find the
price Ci] denotes the vae of a piece
of length iven on iteqer arrag and an integer different
denominations of currency by using
Deteminc the maimum Vaee obtainable by cuting
p Can aKe 6um
number of ways yo
coinsCNJ. Subset-um prob lem
the rod and setimg the pices. Combinatioms from
Unbounded
Same as Unbounded Knapsack Problem . ucstion is 5imi la2 to
204 Sum
price Is] = l,5, 6, 4,l0, 17»1)
Tnitíalizatiom
e N8 arr: 1ngy
5urm
(iro)
2 6 8 Rod iength Maximum
Number of ways 1o
Coins (first
i coi ys
frorm
coinsr
dplj] : with i
make Sum |
<j)
2
Loqic - if Ccoins Ci-1] dplj-coinsCinD) + dp[j1;
3 dpCj] - Dom't take
5
numbrr of coins maKe
Minimum c o i s to
6 coim chanqe problem of
num ber retuln-1.
nmini m u m Sum
) find the make a
o055ibl e
to
it5 not required to
": The item is a b u m . If
humber of coms total
Herc dp[jJ:
Minimurm
sum"" uith i coims. im
reusable. make
Ttems
We can reduce
Hhe space 3 Thitializat bn
ar:t J (emety)i=o)
6 8 Rod length.
ifCcoimsti-] <J)
If (itemstze <= Rodlergth) Ci-193+0, dpj)) :
Try to re- ncude thas
item for the dp7 =min ( dpLj- coins
updascd [Link] Cie j-i)
profit can be
HCrC , olpIj- 1]’ marDblained for the 5ame
ítenns when lenqth- Rod j-I
 Longest common Sub6equen ce
6ubsequence (Lc5) lenqth of their longest
OLatgest Commom subaning Lonqest Common the
Strings X and y . Find
print Lcs iven two
Comm0m subsenquence.
shortest commom Super Sequence
primt 6c6 Outpet
6) Mimimum mumber of in6ertion
2 deleion (a’b) ly:b
Erput
Largest reptng Subsequence. of tuo
in b. and m' be the enqths
of which is a subsequence Loqici- Let m
Length of largest Gubsequence optimal 5uhoruete:
(8) Subsqene pattern matchimg
Count How mamy timcs a appea)y as 6ub6 equence in b. if(an =Ym)
ifan=Ym)
(9) Longest patindromic Gubsequence
0 Longest patinaromic Suberring
COunt of palimdromic Sub6tring palimdrome nn
Mimimum number of deeiors in a to make it a."
srin t0 make it a.
4) Minimum munmber of imsertion in a
Palimdrome.
sub iequence aiomg
Recussive cquatlon
L(n,m) : lenqth
of longest m and m.
ket Strigs having length
0M==0 oR mn=0
n-ym
m-1); mm>
o and
)=1 + L(n-, and
L(m,m
L(rm-1)):
haéx mav ((Ln-l,m),
14emS WICU
 LCS
2 3 m
Oprint
3itatization
oooooo
When (n OR m= D)
length (Lc6) =o
*Recursive so|7
Bortom up 50| [Memoization]V
Lmd
>ol
Top Down 5ol"CJ Lmax(LCn-m],
(LCm1]
COmmm 6ub5tring
DOLomgest ABMD E F Logie;
56
A
B 2O
T if(dig Sans)
20
F
Initiatizatio
 shortest Coomom 5uper bequence
Given two srings Largest palindromic 6ubsequence
and y of legth m ard m respectively lonqest palindromic
Hd the length of smatest 6trim which has both and y Griven a , ffnd the lenqth of
s its 5ub-Sequence.
Subscquence]S
AGMIANB [shortest comman Loqic n’given 5rng
GMTMAN8 Super Squmre y e . reverseC)
GTAB [Lc5]
If we yenove LC6 from 6c5.
we weill left wirh the chosacters
ans
Les(*)
which ae not comon m both. to maKe it
deletion im a sring
Minimum numbrr of
:. WC Can
shor rest common supctscquenre= mtn palindaome. of chaacte rs
TLC5ky
cOz, m = len(Lc5) +char which [Griven a srimg Fimd the
minim um
number
palindrorme.
ane not in Y remove to mare it
m =lem (Lc6) + #chas. we need to
which cae mot in c x ’ qiven string
Loqi c rever5c(a) .
(12) Minimum nunmber of imsertfon and Detetiom to convert
sning a to b.
ans = n - L c s ( 0 ) |
a: hep a:
b: pea LCS
#min number of inieHion t Deletion = mt m- 2* Lcs
to comvcrt a b
() print shortcst Commomn
Suprsequence
Given tuo srings x and y of length (5c6)
m and m respty 9 longest Repeasing Subsaquenoelenqth of the longeit repeanq
the
Given a srimg 5tr,, find found twlce in the
given
TasK i5 to primt thier 5c6. such that it an be
Sub5equence
XX* subsequenre repnttd
sring
pea
’ heap (5c6) str " akzy" 4oice
h
2 6
ooloo o ooo
oooooooa
X
GtrCi-]== tr S )
2
e 2 30
X
+
3 and itj
X
i=m,j= m, 6c6 =";1
white (i >o 2e j>o) axxzxY
6tr[i-] -= Strlj
But i==i (Same etement)
i--j
Loqi c - L2
if (dpLi-i1Jj7 <dptilj-0) dpliy] = It dplir3ð-02
5c5 = Ci-1] + 5c6;
while (i>o) sc5 - 2ri-13 +6c5 ; Í--i
(9 Sequenee pattern mathing
Given tws 5trings x and u, checK whethe is subsequene Matiik chain Muttplcatton
Of
Sting or mot OMCM
xabe"
8ahbgde" vye) printrg MaM
Laqic if (x == LCs(* )) ’ Fvaluate expressiorm to true
Boolean parernhesizatior
retum true
compasig thier lenqths Min/ Max vaue of an expressio
palindrome paritoring
G Sctarmb|e 6tring
retutn fatse;
Eqg aogping problem.
(10) Mimimum number of ’Tdentifi Cation of McM problem
imsertiomns in a string to make it a
patindrome. 5olve (ij) Right
end
Given a string, Fid the minimunm number "of imsertioms énd
required to mmake the Strimg paindrome. TI-4nanglsning
Move k betwecn
4 revelser ); n=length (O ito j cals
Mare fun cHion
ans
m- Les( y].lngth(
6olve (is K) Bo)ve (kttj)
OMCM Sring i5 padindrome
iven n matriccs A,Az, As,. An ith orders ÉR.A.e.. G} Opalindrome paritoming of the i6
buch that Drder of murix A¡ Px P riven a string rs pasritioning
6tr
bub 6tring of the
pastton
required for
number of
cuts
palanthasize qiven m- matrice s Such that minimum cost of pastionig Fimd
Minimumn
srimg
of the qiven
palindrome.
mutiplication js acheived. pauindrome pesnitioming
’ans9
ABCD 6tr = obabbnalt baba for
required
(ABcD) (A B)Xc D) number of cuts
from i to
Minimum
PLj] of arig
patindome pasitoning
(i-j)=T
AÂ C)D) A6(cD) OR
ispaliredrome
ket
CLijJ- Minimam number of 5calai multiplicattons
Yequired in ordel to patenthesize mttices (for vik, isk<j)
from Ai to Aj
mincct.]+ cEktsj]+ R*aRy:i>i
(for tky isk<i)
Evonte expressiom to truc [Boo l Can
Griven a string 5 tepres enting booleanpa\enthesizatiom]
expression of legth
with n
foltowing smbojs:T,FR, I,A
Count the mumber of ways we can palenthesize the
So that the vallec of expression express iom
evaes to true.
6=TAFIF" const int mod 1003:
&dpFstring s,int iint j,bool
goal)

as =o (OAF IF) int

count(vector<vector<int>
&dpT,vector<vector<in

if(i> j) return 0:
Loqie forK COZ, operators
K<i:k= Kt)) ata
win be present if(i j)
distance of 1 if(goal true)
from cach oth ers
det sub probi m(i, K-l) return dpT[JG]-(s[i]T);

if(goal false)
Sub problem (ktl ,j) return dpF[JG]-(s[i] F);

At=f weuys to mare lefH sub- problrm Truc.

rt =#ways to make right Sub probrm True !=-1) return dpTi]0]:
if(goal -- true && dpT[i]] return dpF[i]U1:
if(goal == false && dpF[i]0] = -l)
f= # wogs to make left 6ub-proplcm faLsc. int ways =0;

to mave ight sub- probiem fue, for(int k = itl; k<j; k t= 2)

Thees and Goal is to mae int Itrt,[Link]:

if (6K] == 2) <xpressjon Truc if(dpT[i][k-1] ==-1) It= count(dpT,

else It = dpT[i][k-1]:
dpF,s,i.k-1,true) P%mod;

ans t- at* rt) if( dpT[k+1]] -l) rt = count( dpT. dp

Fs,k+1j,true) %mod,
¬lse else rt = dpT[k+1]0];:
i,k-1,false)%mod,
ns + = (1t*rft 1f*rt t lf * rf) if( dpF[i][k-1]==-1) If= count(dpT, dpF,s,
else If = dpF[i][k-1];

-and Gaoal is to make if( dpF[k+ 1]6]

-)rf- count(dpT, dpFs,k+1j,false)%mod:

if (6tK] == l|y espresson Truc

else rf = dpF[k+ 1]U]:

if(s[k] =-&)
ans t =(t *tf 1f*rt t+ Ittrt) if(goal = true)

ways =(ways + It*rt)%mod:

ans t (0f Frf) else

ways = (ways + It*rf + lft + If r)%mod:

Similby for (A(xof) T

T F4)
ns
else if(s(k] )
if(goal true)
ways (ways +It"rf+1fn
+imod,
else
Ifrf)%omod;
ways = (ways +
else
if(goal true)
Ifn)%mod:
ways = (ways + It*rf+
else
ways (ways + Ifrf+ It*r)%mod;
if(goal = true)
return dpT[JU]= ways%mod;
else
return dpF[JÜ]= ways?%omod;
int countWays(int n, string s)
vector<vector<int>> dpT(n,vector<int>(n,-1);
vector<vector<int>> dpF(n, vector<int>(n,-1):
return count(dpT, dpF,s,0,n-1,true)%mod;
 5crambied 6tting the task is
Given two Gtrings 6 and 52z of equal length.
5crambled form of St.
to determine if 62 i5 a reprsent it as
We can
Scrambled sring i- Griven a si"g stT, it into two
binary tree by porition ing
nom-empty Substrings recursively sting
chosse nt
To 6cramb le the tio childrens
coder and auap its
mon- leat node Co " a Suap
its
choo6e the node
(co der fuppose )we scrambl ed Sring
/
er
tuo chiHren, H procduces
d
Y
"ocred
when Suap worKS.
Cse - I
br
if( 5ove (asibsr(o,i). b. abse ri:i') 2k
Sove (a:sabaY Ciy m-1) , brsubser (o, -i))
6olve (argr) &e 6olve (eat, eat) for, i=2
case 3-II when uap i5 ot tequired.
b
H( ove (aaibstr(o.i) . b:substr(o-1) 22
b"6ubstr (iyn-i)
Solve (a«ubsty (sn-f),
i=2
Golvc (gr>qr) Le olwe (eat yare) for,
asei5 truc
Cor fom abve two
String is 6crambed .
 Basc conditiong acce35 to
) length of both stings nust be 9 Fgg daopping probi em
identtcal
cggs and
you have
Same to become sctanblcd, Yow ae
given E to f
from 1 pped
iH(alength() != btength0) Ten fase; af-ftoored buildimA K<f) Guch
thas any 11
daogped
exist a floor K(0<
when to 5top There uin break ard
hiqher than k
trom a ftoor will not
break.
if (a --b) retutn from oR below
fioor 7
can be
sed gain
truc; that
survives a tall
(3) tf onc of Nules : OEgq muest be
discasded.
th
Sring is enpy ’rettun fase Abroren 7
If(a length() <= 1) Tetan talí C; Solve (E,f)
(ohy )!- (ter kenghjana (is equel to)
\is cqudI
h ffor
thn they must be same ans shoeld
handetrd by the above base [Link] Break
Here, H lenqth and not equal’Yettsn tale. 6rcak
L
X
Aowe (E-i, k-i) Solve(E,f-K)
Memoizaion i- We se 7map to Gtore and it boolan requireol to
Valeee
mim. number of attc mptswuth E-engs and
ftoor
Vue Bowe (EF):- find the
thresholl
f- flooeld building
ab
T/F :-if(EI Of f= 1)
Base cCUSe
OR
a#b ans
INT-MAX)
<=fiKtt)
K=|:k
for( fntk
(E, f-x) ):
temp Itmax
(oovc(E-t,K), Sove
Cns
min([Link])>
 De on Trees cny mode
any mode to
Maximum path Sum from
) Diameter of Tree
Maximum path sum from mode to any other mode
dplroot ]:
) Maximum patth Sum from leaf mode to any other leafnode !=0) return
Diameser of N-ary Tree. if(dploot]
(root’left)
Jeft = 6oNe
9Diametey of Binary Trec - 5ove(Yoot right)
right)
left t
Note : |Diameter/width of ca tree is defined astug
the mumbt max(ans , root data +
modes. ans = left
of modes on the lorgest pth betwen any data t Max rghtd
n the trec* retwm
dplioor J=max (0, Yoot
other
to a y
Loqie - Base cast :ifNut mode) rctutn 0j fromm leaf mode
path sum
if (dptroot] != 0) rettujn dp Iroot ] 3) Maximum
Ieft = So ve (root -left) leaf mode
)
retun ;
(Nt
; 1f
Rigbt -Solvc (Yoot- igbt) Loqie : Basccase dpoot]
4 t lrft t != 0) tetuin
Cns = Max( ans5 right) H
(dpCroot]
50lve (root-’
left);
Aeft =
-> hight );
Truln dplvoot] = 1 t Max (left ; kight ) : Right =
5olvc (root
leftt hight
t
root d a t a
max(ons,
dp ’ unordered_map (Nodet s int>
ans
voot-data t Max(eft , right)
Tettun dp[root ]=
 Tnereasing Subsequence. (LI5)
Lonqest
)LIS
Oprint Lrs
Subset
9 Largest divisible
) Longest String chain
Subsequence
) Longest Bitcoin
(6) Number of LIS
the length
of the
)LIS inteqers,find
Griven an arrey. at J of n
Ilomgest imereaaing 6ubscquence.
4,IY ’ LIS-{5,t4Y
aT6] - 6.6,3,7, Ars = 3
6utbsequene
Loqic dp[<J[p] ngh of lomqest Tneresing
Ststing from
that can he fomm ed
revious indrx)'p"
1he 'c currant index)uith thc
elemrnt inetuded im
os the index of last
Subsequence
if( amlc) > arlp])
Itf(cH, ))
dple1(p] - muf(cisprev),
dp to1lp] f(cn,p)
Solution - Binavg Sealch Sub arag
Maximum 5ub arra 6um. arrCn).
Find the
int LIS (int n,int at3) aruy
Gaiven an intgrr Sum. (Find
urm)
maximum
vectOr Kint> tmp) that has -2,l5,-33
,-3.4,
Imt 5.e m , imdex ; art] = Sum =
[Maim Subarray
for (iny i- o, i<m; itt) Goletiorm
3 * 5olutioms
Ynaxi INT-MIN
if (*mp- empty() | Rct) >[Link])) L Brut for cc i for(int i-o;j<m; itt)
temp-push-backar )): j=-iij<n ijtt)
for( t Cj];
Tc: 0n?)
Sum t = arr
maxi);
max(5um,
6C: 0 ) =
maxi
e= tmp-6ize() -1;
om) SeBchinary
while (5 <=e) 5Lm
O(ogn)
)
laxqest 5ub a n a
possible
Maximum
: at mdey j "
if (ari > temp[m]) dptig
(Base case )
First element
o]i
dplo] = arr
e m-1;
for (i : 1’n-1) dpli-1J)
(artt], art) t
dpli) =max
|tmptindex] - aríJ; mar(dprtl, ans)
rettsn tcmp. sirc(); Tc: 0(m)
5c: 0()
kaclanes Algorithrn
5um.
Maximum 5uharray
=-1;
end
maximum = INT- MIN Qprint 6tast - temp
for(int i-o; i<m i itt) 5um =O
We Keep on ompimg ans
= I N T MIN
|5um t= arr Ci]; Sub-array 5um
if (5um > mauimum)maximum 6um, for(nt i- 0; i<m
; itt)
if (um <0)Sun =0; t if (Surn -=0) temp =J
CiJ
5um t = arr
uuith ngeic
TC:0m) 5um i5 disasded
if (6um > ans
)
6C:0() Lwe carny sub-at ay t it ans = 5um
gives tve sun end = i
Stait =tmp i
6 print Maximum Subariay if(6um<0) 6um =0
Stasd -1 , end= -
5um =
ans = INT MJN
far (int-oi<mitt)
i5um ==0 \stat = i;
6um t= anti];
ifan > ans)iarx 6umy
if (6urm)