Dynamic Programmingπ


Dynamic Programming = mai hu DP (Ha ha wahi jis se sabko dar lagta hai π par ab darne ki zarurat nahi, mai itna bada saari badi company ka favorite topic hu π) **par mai bahut kaam ka hu to apna dar kam karne ke liye mai aapko poori detail mein bataunga ke kaam kaise karta hu, kya hu mai aur baaki sab is pure journey mein bataunga mai ok abhi daro mat π samjho mujhe tumhare us EXπ¨π¨π± se to accha hu mai uske tarah thoda toxic to par accha wala to chalo ab hum start karte hai (bolo Radhe Radhe ππ»ππ»ββοΈ)
Aur ek baat aur mere saath chalne se pehle mera ek chhota bhai hai agar aap usko thoda acche se dekh loge to accha hoga uska naam hai (Recursionβ€οΈ) bahut accha bade bade code ko bahut chhota kar deta usko aap thoda acche se padh lena ek baar
To pehle pehle mere andar kya kya hai ye dekha mai darna nahi chahta hu pehle aap hum se mil lo ke dekhta kaisa. Agar mai dekh jau to mujhe dekh kar aap jaan paoge mai DP hu ok.
IDENTIFYπ
1 = DP = Enhanced recursion, 2 = optimal
AB question kaise pata lagaye ke ye Enhanced recursion or Enhanced DP hai
to. A = Choice => matlab hamko bahut saari ya choice de rakhi hogi (jaise ek bag hai aur uske paas 2 ball hai to aapke paas hoti hai choice ke le ya na le π΄ ya jab aapke paas aapke bande ya bandi se accha option hota hai choice hoti hai na ke usko jeevan mein rakhe ya na rakhe choice milti hai na)
B => Dekho agar choice de rakhi hai to recursion lagega aur overlapping problem hai to DP lagegi (Ab overlapping kya hoti aayenge baad mein abhi sun lo bas)
Chalo upar upar se bata deta hu Recursion do baar call ho raha ho to DP lagega aur ek baar ho raha ho to nahi lagega par 2 baar ho raha hoga to lagega hi most aur chance hai lagega hi
2 Optimal = matlb min , max ya or bhi aage dekhte hai ok
To ab tumko dekh gaya ke multiple option hai to ab kya karoge samjh DP lagegi kaise lagegi ye pata nahi hoga na haan bahut se log honge jo (Top down) laga kar matrix fill karna start kar denge fir bolenge DP hard hai
nahi bro simple method hai ok
Recursionβ> Memorize β> Top down
Starting ke kuch most important problem hai ham ab sab kuch problem se learn karenge aur mai har problem ko explain karunga aur uske leetcode ke link dunga aur usko aap khud solve karoge jo padha uske base pe ππππ
0-1 knapsack (6), Unbounded knapsack (5), Fibonacci (7), LCS (15), LIS (10), Kadane's Algorithm (6), Matrix chain Multiplication (7), DP on Trees (4), DP on Grid (14)
ye hi DP hai bas inke variations hai inko kar le acche se around (80) problem hai jo solve kar sakte hai ham in question karne ke baad tum saare DP ke question laga paoge 100% (agar sahi se padha hoga)
To ab ham chapert 2 starte karege π( To isame ham pata lagaege ke kuapsack ke 6 most important perblom hai vo kon se hai ππ )To shru karte bina kise bakvass ke β€οΈβ€οΈ
Subset Sum
Equal Sum Partition
Count of Subset Sum
Minimum Subset Sum Difference
Target Sum
Number of Subsets with Given Difference
In saare problems ke baad aapko kisi bhi tarah ki problem nahi hogi ok
Jab hum pehli problem karenge tab uske baad saare code mein thoda minor sa change karna hoga aur aap log saare questions kar sakte hai aur in case koi new 7th problem aa jaye to vo nahi nahi ke inko karke dimaag itna aa jayega ke hum vo aaram se kar sakte hai vo ok.
To is sabko padhen se pehle hum 0-1 Knapsack problem.
What is 0-1 Knapsack problem? π€·π»
Ye in saare important questions ka base case matlab is se saare coding ke problems solve hongi ok isko dhyan se samajhna jab aap isko samajhna start karoge to aapne aap sab samajh mein aane lagega ok aur mai tum easy lagne lagunga ok (mujhe bhul gaye mai DPπ)
Three types mein dekhta hu ok:
a. Fractional Knapsack ββ Greedy
b. 0/1 Knapsack
c. Unbounded Knapsack
To haan bahut knapsack knapsack knapsack hota kya hai ye pehle to batao DP bhai ππ» OK
To simple language mein batata hu mai just imagine ke ek bag hai tumhare paas ok ab usme tum minimum number of items daal sakte ho (item ka matlab koi bhi object jaise banana, koi weight etc aur uski value bhi dekhte hai hum ok)
int[] weights = {1, 3, 4, 5};
int[] values = {10, 40, 50, 70};
int W = 7
Jaise aap dekh sakte hai isme humare paas do weight hai ok first one is weights aur unki value bhi dekh rahi hogi uske hisab se hum weight dalenge (I know nahi samajh aaya tumko dekho)
___________
/ \
| w |
| V | ------> BEG HAI YE BHAI/BEHAN
| |
\___________/
To jaise aap dekh sakte ho ek bag hai ok uske andar to jaise aap log dekh sakte hai ke
isme hum 7 weights tak hi daal sakte hai bas aur aise weights dalna hai ke hum max value
la sake (kaun sa aisa weight pick kare humko profit max ho)
Example 1: Jaise upar jo example hai usse hum bas index (1,2) lenge to max
profit aayega ok ---> 40+50=90
aur koi bhi weight nahi hai jis se humko 90 se zyada profit ho jaye ok
To abhi aap log mere first roop ko dekhoge jisko hum Fractional Knapsack bolate hai isme humko DP ki need nahi hogi hum isko Greedy ka use karke bana sakte hai hum (kyunki hum chahe to puri value le ya half bhi sakte jaise max weight ko 7 le sakte hai to max profit ke liye hum kisi ka half part bhi le sakte hai π₯Έπ₯Έ)
To ab meri baat karte hai ke kaise kya karna DP mera kaha use hai mera use hai knapsack mein π΄π΄
Like mujhe ya pura daalo ya fir daal hi mat like max value 7 hai aur mujh mein 6 aa chuka hai par 1 baki hai aur mujhe 1 pura hi daalna hoga mai half nahi daal sakta hu ok ya use hota hai mera pura.
1: subset Sum
2:Equal sum partition
3:Count of subset sum
4 Minimum subset sum Diff
5: Target Sum
6: Number Of subset given difference
To in saare problems ke baad aapko kisi bhi tarah ki problem nahi hogi ok.
Jab hum pehli problem karenge tab uske baad saare code mein thoda minor sa change karna hoga aur aap log saare questions kar sakte hai aur in case koi new 7th problem aa jaye to vo nahi nahi ke inko karke dimaag itna aa jayega ke hum vo aaram se kar sakte hai vo ok
To is sabko padhen se pehle hum 0-1 Knapsack problem.
___________
/ \
| w |
| V | ------> BEG HAI YE BHAI/BEHAN
| |
\___________/
to jasa aap dekh sakte ho ek beg hai ok uske ander to jasa aap log dekh
sakte hai ke isame ham 7 weights tak hee daal sakte hai bas or aase weights
dalana hai ke ham max value la sake(kon sa aasa weights pick kare hamko
profit max ho )
example 1: JASE uper jo examle hai usa se ham bas index (1,2) lenge to max
profit aayega ok --->40+50=90
or koi bhi weights nahi hai jis sa se hamko 90 se jada profit ho jaye ok
To abhi aap log mere frist roop ko dekhoge jisko ham Fractionaln kuapsack bolate hai isame hamko DP ke need nahi hogi ham isko Greedy ka use karke bana sakte hai ham (kuki ham chahe to puri value le ya half bhi sakte jase max weight ko 7 le sakte hai to max profit ke leye ham kise ka half part bhi le sakte haiπ₯Έπ₯Έ )
To ab meri baat karte hai ke kase kay karna DP mera kaha use hai mera use hai knapsack mai π΄π΄
like mujhe ya pura daloo ya fir daal hee mat like max valaue 7 hai or mujh mai 6 aa chuka hai per 1 baki hai or mujhe 1 pura hee dalna hoga mai half nahi daal sakta hu ok ya use hota hao mmera pura
javaCopyEditint[] weights = {1, 3, 4, 5};
int[] values = {10, 40, 50, 70};
int W = 7;
Qusetion=> TO seen ye hai ke hamko aase weigth pick karne jinke value max aaye
maatlb profit max aaye
EAX: index 1,2 per profit max aayga ok
TO ham pata kaise lagayenge ke knapsack ya hamko DP lagani hai to dekho ye kuch simple hints dega jaise choice aur optimal code likhne ko bolega
1.Choice: Ye tab hota hai jab aapke paas weight ko select karne ki choice hoti hai. Aapko check karna hota hai ki kaunsa weight lena hai ya nahi.
2.Optimal: Iska matlab hota hai maximum ya minimum nikalna, jaise maximum profit ya minimum cost.
To isme kaha ye sab? => Ye raha hamare weight ko select karne ki choice hai, 1 check β + max profit (aur tumne dhyan se padha ho to maine bataya optimal ka matlab ke max nikalna, min, etc.) to ye second β ye pehchaan iske.
DP: Recursion ββββ Memoization ββββ Top-Down (DP) main part jo ham karenge.
To this is a Knapsack Recursive(yaha se main maal ayega ππ)
stpe one is a =>π³ Choice Tree (Include / Exclude Diagram)
W = 3, i = 0
[i=0, W=3]
/ \
Includeβ
Excludeπ«
/ \
[i=1, W=2, val=10] [i=1, W=3, val=0]
/ \ / \
Inc Exc Inc Exc
/ \ \ \
[i=2,W=-1] [i=2,W=2] [i=2,W=0] [i=2,W=3]
val=? val=? val=? val=?
To ye choice diagram de rakha hai to isko dekho ham 2 choice hai jase ham
select kar skate hai or nahi kar sakte (jis se pata chlata hia ke ye DP ka
dono point aayege ok)
ye dekho choice diagram hai ye important hai ok isko bana liya to half kaam ho jayega ok (mai tumhare bas mein aane start ho jaunga aur tumhara dost ban jaunga ok)
to ye hai first function hai ok dhyan se dekho ye mera base part hai ok aa aayega to bahut aasani hogi mujhe samajhne mein ok π₯Έπ₯Έπ₯Έπ₯Έ
int Knapsack(int wt[], int val[], int w, int n){
// to ab important step hai first is a BASE CASE (BC => kaise dekhe ab ye question aata hai? Base Condition ββββ> Think of the smallest valid I/P)
to valid input kya hoga dekho sabse chhota lenge hum jaise humko aage need hogi to vo dono array ko mila kar hum n=0; aur W = 0 lenge sabse chhota aur valid kya hi ho sakta hai bro vo hi hoga)
if(n==0 || w==0) return 0 // BC => kyunki sabse chhota choose karna hai humko ok aur ye jaruri hai bag lekar jaoge sabse kam kya hi daloge usme Zero bas us se kam hi daloge
//choice diagram => To iske condition likhte hai ye hamari first condition hai aur vo jab aayegi jab hum weight select karenge ok else wali jab jab hum select nahi karenge π«
if(wt[n-1]<=w)
return max(val[n-1]+Knapsack(wt,val, w-wt[n-1], n-1),Knapsack(wt,val,w,n-1);
else(wt[n-1]>w) return Knapsack(wt, val,w,n-1)
}
Agr ye samjh nahi aaya aap log is link per ja sakte ho(https://www.youtube.com/watch?v=kvyShbFVaY8&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=3)
β 1. Java Version
javaCopy codepublic class Knapsack {
public static int knapsack(int[] wt, int[] val, int W, int n) {
if (n == 0 || W == 0) return 0;
if (wt[n - 1] <= W) {
return t[n][w]= Math.max(
val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1)
);
} else {
return t[n][w] knapsack(wt, val, W, n - 1);
}
}
public static void main(String[] args) {
int[] weights = {1, 2, 3};
int[] values = {10, 15, 40};
int W = 6;
int n = values.length;
System.out.println("Maximum profit is: " + knapsack(weights, values, W, n));
}
}
β 2. C++ Version
cppCopy code#include <iostream>
#include <algorithm>
using namespace std;
int knapsack(int wt[], int val[], int W, int n) {
if (n == 0 || W == 0) return 0;
if (wt[n - 1] <= W) {
return max(
val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1)
);
} else {
return knapsack(wt, val, W, n - 1);
}
}
int main() {
int wt[] = {1, 2, 3};
int val[] = {10, 15, 40};
int W = 6;
int n = sizeof(val) / sizeof(val[0]);
cout << "Maximum profit is: " << knapsack(wt, val, W, n) << endl;
return 0;
}
β 3. Python Version
pythonCopy codedef knapsack(wt, val, W, n):
if n == 0 or W == 0:
return 0
if wt[n-1] <= W:
return max(
val[n-1] + knapsack(wt, val, W - wt[n-1], n-1),
knapsack(wt, val, W, n-1)
)
else:
return knapsack(wt, val, W, n-1)
weights = [1, 2, 3]
values = [10, 15, 40]
W = 6
n = len(values)
print("Maximum profit is:", knapsack(weights, values, W, n))
HELLOW JI TO YE DAY TWO HAMARE DP KA PATH KA HAM AB RECURSION VERSION PADHNGE HAM OK TO START KARTE HAIππ(BOLO RADHE RADHEππ»ππ»ππ»ππ»)
Ab ham recursion ko Memoize mai convert karnege ok to ab
to seen aasa hai ke kuch chnage ho rahe hai kuch nahi ab dekho agr tum function se ye compare karo to
if (wt[n - 1] <= W) { return Math.max( val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1), knapsack(wt, val, W, n - 1) );
isame value[] arr ko dekho vo chnage nahi ho raha or wt [] arr bhi change nahi ho raha hai to change kay ho raha hai fir jo hamata int w wali value or int n wali to memo (Memoization) ke leye hamko vase metrix cretate karni jo chnage hp rahi hai
to jo bhi bhi chnange ho raha uski matrix banayye or puri matix mai -1 fill kar denge
π DP Table (Initial: All -1
)
plaintextCopy code Capacity β
0 1 2 3 4
Items +-------------------------
0 | -1 -1 -1 -1 -1
1 | -1 -1 -1 -1 -1
2 | -1 -1 -1 -1 -1
3 | -1 -1 -1 -1 -1
to koi bhi value nekalane hogi to mai pehle dekhuga waha per vo valaue prenst hai ke nahi hai to pura recursion function call karne ke need nahi bas dekho waha hai ke nahi or age -1 dekhuga or nahi hai to waha per usko relce kar dunga or dekhuga ke us jagha per like(3,2 ) w=3 Thred row,or n= 2 second col, agr kuch huaa -1 ke alava to mai retun kar dunag nahi huaa to waha per recursion call karuga or waha jo value hai unki help se new value stre kar dunga or jis aage nedd ho to return kar sake
Memoization mein yeh base case:
if(n == 0 || W == 0) return 0;
β
Initialization in Memoization (Conceptual Visualization)
Capacity β
0 1 2 3 4
Items +-------------------
0 | 0 0 0 0 0 β (n == 0) β no items = 0 profit
1 | 0 ? ? ? ?
2 | 0 ? ? ? ?
3 | 0 ? ? ? ?
To ab kay chnage kare ke hamaa Recurestion wala code ko ham Memoization
mai convert kar sake to
FRIST STEP(ham ab kay constrian ko dekh lenge or uske hisab se ek new dp bana lenge or usko top per banayege or unko static banayege taki sab accessble ho ok
To = int static t[102][1002] ye ham constrain dekh kar bana rahe hai ok to ye code kasa dekhyegga
int static t[102][1002];
memset(t,-1,sizeof(t))
second step ( Ham ab ye karege ke base to same rahega per uske uske baad ham ye line add karege like
if(t[n][w]β -1) return t[n][w];
is se kay jo call lag rahi pehle ke code 01Knapsack wale mai flatu mai vo nahi lagega to ye chheck karga ke value save hai agr nahi hai to ye karege ham
Thred step
jo mani tha na code max wala
if (wt[n - 1] <= W) { return t[n][w]= Math.max( val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1), knapsack(wt, val, W, n - 1) ); }
} else {
return t[n][w] =knapsack(wt, val, W, n - 1);
}
to kay huaa hamne bas t[n][w] ko hee add keay ku keya kuki hamko vo to matrix khali thi usko fill karna tha waha se -1 hata kar jo ki falatu call na lage
To full code ye raha
β Corrected + Memoized 0/1 Knapsack Code in Java
javaCopy codepublic class Knapsack {
// Step 1: Static DP array based on constraints
static int[][] t = new int[102][1002];
public static int knapsack(int[] wt, int[] val, int W, int n) {
// Base case
if (n == 0 || W == 0) return 0;
// Step 2: Memoization check
if (t[n][W] != -1) return t[n][W];
// Step 3: Choice diagram with memoization
if (wt[n - 1] <= W) {
return t[n][W] = Math.max(
val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1)
);
} else {
return t[n][W] = knapsack(wt, val, W, n - 1);
}
}
public static void main(String[] args) {
int[] weights = {1, 2, 3};
int[] values = {10, 15, 40};
int W = 6;
int n = values.length;
// Step 1.5: Initialize t with -1
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 1002; j++) {
t[i][j] = -1;
}
}
System.out.println("Maximum profit is: " + knapsack(weights, values, W, n));
}
}
β 1. C++ Version (Memoization)
cppCopy code#include <iostream>
#include <cstring>
using namespace std;
// Step 1: DP table
int t[102][1002];
int knapsack(int wt[], int val[], int W, int n) {
// Base case
if (n == 0 || W == 0) return 0;
// Step 2: Memoization check
if (t[n][W] != -1) return t[n][W];
// Step 3: Choice logic
if (wt[n - 1] <= W) {
return t[n][W] = max(
val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1)
);
} else {
return t[n][W] = knapsack(wt, val, W, n - 1);
}
}
int main() {
int wt[] = {1, 2, 3};
int val[] = {10, 15, 40};
int W = 6;
int n = sizeof(val) / sizeof(val[0]);
// Step 1.5: Initialize t with -1
memset(t, -1, sizeof(t));
cout << "Maximum profit is: " << knapsack(wt, val, W, n) << endl;
return 0;
}
β 2. Python Version (Memoization)
pythonCopy code# Step 1: Create DP table
t = [[-1 for _ in range(1002)] for _ in range(102)]
def knapsack(wt, val, W, n):
# Base case
if n == 0 or W == 0:
return 0
# Step 2: Memoization check
if t[n][W] != -1:
return t[n][W]
# Step 3: Choice logic
if wt[n - 1] <= W:
t[n][W] = max(
val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1)
)
else:
t[n][W] = knapsack(wt, val, W, n - 1)
return t[n][W]
# Inputs
wt = [1, 2, 3]
val = [10, 15, 40]
W = 6
n = len(val)
print("Maximum profit is:", knapsack(wt, val, W, n))
DP :Top Down DP
Top Down DP: iskani need kay padhi ku use karte hai jab ham recurion se kar rahe the sab kuch to need kay padhi
To need ye hai ke jab ham bahut jada hee resusive call use karte hai to to hamara stack uper tak bhar jata hai fir uske baad or resursion kaam nahi aata hai
to ham Top Down DP ka use karte hai
To step kay hunge
step 1 = Initialize karna hota hai
step 2 = Reverese call funcn ne
wt[]= [1,3,4,5]
val [] = [1,4,5,7]
w =7
t[n+1][w+1] = t[5][8]
ab ham matrix banayegi ok 5,8 ke
π Final Matrix Size:
i β / w β | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | ||||||||
2 | ||||||||
3 | ||||||||
4 |
Hum ye matrix bharte jayenge row-wise, left to right
i β / w β | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
3 | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
4 | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
π― Final Answer: t[4][7] = 9
That means: maximum value you can achieve in weight 7
= 9
to ye 9 hai ye last mai aaya to max profit hamko ye 9 milega 4,7 index per aap diagram mai dkeh sakte hai (or ab soch rahe hoge ke ye jo bolate hia sub perblom mai divied ho jata hai kase hota hai ku hota hai to iska ans ye hai
ke jab ham kise bhi index per jata hai to like[5][2] to ye to isko mai sub perblom mai baat leya ab usko slove karege or ham ko vpas jane ke need nahi hoto hai usko ag slove kar rakha hoga to to value hogi nahi kar rakha hoga -1 rahega jis se pta rahe ke vo index slove nahi huee hai
to ab code ke bari
for(int i=0;i<n+1;i++){
for(int j=0;j<n+1;j++)
if(i==0|| j==0) t[i][j]=0;
}
step2
jo jo function chnage ho raha hai waha per ham t la dnage ok
if(wt[n-1]<=w){
t[n][w] = max(val[n-1] + t[w-wt[n-1], [n-1]], t[n-1] [w]);
}else
t[n][w] = t[n-1][w]
π» Java Code
public class KnapsackTopDown {
public static void main(String[] args) {
int wt[] = {1, 3, 4, 5};
int val[] = {1, 4, 5, 7};
int W = 7;
int n = wt.length;
int[][] t = new int[n + 1][W + 1];
// Step 1: Initialization
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0) {
t[i][j] = 0;
}
}
}
// Step 2: Filling the table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (wt[i - 1] <= j) {
t[i][j] = Math.max(val[i - 1] + t[i - 1][j - wt[i - 1]], t[i - 1][j]);
} else {
t[i][j] = t[i - 1][j];
}
}
}
System.out.println("Maximum profit: " + t[n][W]);
}
}
π» C++ Code
#include <iostream>
#include <vector>
using namespace std;
int main() {
int wt[] = {1, 3, 4, 5};
int val[] = {1, 4, 5, 7};
int W = 7;
int n = sizeof(wt) / sizeof(wt[0]);
vector<vector<int>> t(n + 1, vector<int>(W + 1, 0));
// Filling the table
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] <= w) {
t[i][w] = max(val[i - 1] + t[i - 1][w - wt[i - 1]], t[i - 1][w]);
} else {
t[i][w] = t[i - 1][w];
}
}
}
cout << "Maximum profit: " << t[n][W] << endl;
return 0;
}
π» Python Code
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
W = 7
n = len(wt)
# Initialize matrix
t = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
# Fill the matrix
for i in range(1, n + 1):
for w in range(1, W + 1):
if wt[i - 1] <= w:
t[i][w] = max(val[i - 1] + t[i - 1][w - wt[i - 1]], t[i - 1][w])
else:
t[i][w] = t[i - 1][w]
print("Maximum profit:", t[n][W])
π§ Output:
yamlCopy codeMaximum profit: 9
To ab ham ab vo 6 perblom start karege ok πππ₯π₯
Subscribe to my newsletter
Read articles from Navneet Kumar directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
