DP update

darecoder · darecoder · commit c125fc025c7f · 2021-04-11T10:53:08.000+05:30
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/src/com/company/Lecture12/EditDistance.java b/src/com/company/Lecture12/EditDistance.java
@@ -17,7 +17,6 @@ public static int editDist(String f,String s,int flen,int slen){
         if(slen == 0){
             return flen;
         }
-
         int count = 0;
         if(f.charAt(flen - 1) == s.charAt(slen - 1)){
             count = editDist(f,s,flen-1,slen-1);
@@ -54,7 +53,6 @@ public static int editDistDP(String f,String s,int flen,int slen,Integer[][] mem
     }
 
     public static int editDistDPitr(String f,String s,Integer[][] mem){
-
         int flen,slen = 0;
         for (flen = 0; flen <= f.length(); flen++) {
             for (slen = 0; slen <= s.length(); slen++) {
@@ -73,7 +71,6 @@ public static int editDistDPitr(String f,String s,Integer[][] mem){
                 }
             }
         }
-
         return mem[flen][slen];
     }
 }
diff --git a/src/com/company/Lecture12/EggDrop.java b/src/com/company/Lecture12/EggDrop.java
@@ -15,11 +15,9 @@ public static int eggDrop(int floors,int eggs){
         if(floors == 0){
             return 0;
         }
-
         if(eggs == 1){
             return floors;
         }
-
         int minimum = floors;
         for (int f = 1; f <= floors; f++) {
             int down = eggDrop(f - 1,eggs -1);
@@ -37,22 +35,19 @@ public static int eggDropDP(int floors,int eggs, Integer[][] mem){
         if(floors == 0){
             return 0;
         }
-
         if(eggs == 1){
             return floors;
         }
-
         int minimum = floors;
         for (int f = 1; f <= floors; f++) {
-            int down = eggDrop(f - 1,eggs -1);
-            int up = eggDrop(floors - f,eggs);
+            int down = eggDropDP(f - 1,eggs -1, mem);
+            int up = eggDropDP(floors - f,eggs, mem);
 
             int max = 1 + Math.max(down,up);
             if(max < minimum){
                 minimum = max;
             }
         }
-
         mem[floors][eggs] = minimum;
         return mem[floors][eggs];
     }
diff --git a/src/com/company/Lecture12/LongSubseq.java b/src/com/company/Lecture12/LongSubseq.java
@@ -15,16 +15,14 @@ public static int lcs(String f,String s,int flen,int slen){
         if(flen == 0 || slen == 0){
             return 0;
         }
-
-        int count = 0;
+        int count;
         if(f.charAt(flen-1) == s.charAt(slen-1)){
             count = 1 + lcs(f,s,flen-1,slen-1);
         }else{
             int right = lcs(f,s,flen-1,slen);
             int left = lcs(f,s,flen,slen-1);
             count = Math.max(right,left);
         }
-
         return count;
     }
 
diff --git a/src/com/company/Lecture12/ZeroOneKnapsack.java b/src/com/company/Lecture12/ZeroOneKnapsack.java
@@ -14,12 +14,11 @@ public static int zeroOne(int[] wts, int[] prs, int cap, int size){
         if(size == 0){
             return 0;
         }
-
         int acc = 0;
         if(wts[size - 1] <= cap){
-            acc = prs[size-1] + zeroOne(wts, prs, cap-wts[size-1], size-1);
+            acc = prs[size-1] +
+                    zeroOne(wts, prs, cap-wts[size-1], size-1);
         }
-
         int reject = zeroOne(wts, prs, cap, size-1);
         return Math.max(acc, reject);
     }
@@ -28,22 +27,20 @@ public static int zeroOneDP(int[] wts, int[] prs, int cap, int size, Integer[][]
         if(size == 0){
             return 0;
         }
-
         if(mem[cap][size] != null){
             return mem[cap][size];
         }
         int acc = 0;
         if(wts[size - 1] <= cap){
-            acc = prs[size-1] + zeroOneDP(wts, prs, cap-wts[size-1], size-1, mem);
+            acc = prs[size-1] +
+                    zeroOneDP(wts, prs, cap-wts[size-1], size-1, mem);
         }
-
         int reject = zeroOneDP(wts, prs, cap, size-1, mem);
         mem[cap][size] = Math.max(acc, reject);
         return mem[cap][size];
     }
 
     public static int zeroOneDPitr(int[] wts, int[] prs, int cap, int size, Integer[][] mem){
-
         for (int c = 0; c <= cap; c++) {
             for (int s = 0; s <= size; s++) {
                 if(s == 0){
@@ -53,7 +50,6 @@ public static int zeroOneDPitr(int[] wts, int[] prs, int cap, int size, Integer[
                     if(wts[s - 1] <= c){
                         acc = prs[s-1] + mem[c-wts[s-1]][s-1];
                     }
-
                     int reject = mem[c][s-1];
                     mem[c][s] = Math.max(acc,reject);
                 }

Original file line number	Diff line number	Diff line change
`@@ -17,7 +17,6 @@ public static int editDist(String f,String s,int flen,int slen){`
`17`	`17`	`if(slen == 0){`
`18`	`18`	`return flen;`
`19`	`19`	`}`
`20`		`-`
`21`	`20`	`int count = 0;`
`22`	`21`	`if(f.charAt(flen - 1) == s.charAt(slen - 1)){`
`23`	`22`	`count = editDist(f,s,flen-1,slen-1);`
`@@ -54,7 +53,6 @@ public static int editDistDP(String f,String s,int flen,int slen,Integer[][] mem`
`54`	`53`	`}`
`55`	`54`
`56`	`55`	`public static int editDistDPitr(String f,String s,Integer[][] mem){`
`57`		`-`
`58`	`56`	`int flen,slen = 0;`
`59`	`57`	`for (flen = 0; flen <= f.length(); flen++) {`
`60`	`58`	`for (slen = 0; slen <= s.length(); slen++) {`
`@@ -73,7 +71,6 @@ public static int editDistDPitr(String f,String s,Integer[][] mem){`
`73`	`71`	`}`
`74`	`72`	`}`
`75`	`73`	`}`
`76`		`-`
`77`	`74`	`return mem[flen][slen];`
`78`	`75`	`}`
`79`	`76`	`}`
Original file line number	Diff line number	Diff line change
`@@ -15,11 +15,9 @@ public static int eggDrop(int floors,int eggs){`
`15`	`15`	`if(floors == 0){`
`16`	`16`	`return 0;`
`17`	`17`	`}`
`18`		`-`
`19`	`18`	`if(eggs == 1){`
`20`	`19`	`return floors;`
`21`	`20`	`}`
`22`		`-`
`23`	`21`	`int minimum = floors;`
`24`	`22`	`for (int f = 1; f <= floors; f++) {`
`25`	`23`	`int down = eggDrop(f - 1,eggs -1);`
`@@ -37,22 +35,19 @@ public static int eggDropDP(int floors,int eggs, Integer[][] mem){`
`37`	`35`	`if(floors == 0){`
`38`	`36`	`return 0;`
`39`	`37`	`}`
`40`		`-`
`41`	`38`	`if(eggs == 1){`
`42`	`39`	`return floors;`
`43`	`40`	`}`
`44`		`-`
`45`	`41`	`int minimum = floors;`
`46`	`42`	`for (int f = 1; f <= floors; f++) {`
`47`		`- int down = eggDrop(f - 1,eggs -1);`
`48`		`- int up = eggDrop(floors - f,eggs);`
	`43`	`+ int down = eggDropDP(f - 1,eggs -1, mem);`
	`44`	`+ int up = eggDropDP(floors - f,eggs, mem);`
`49`	`45`
`50`	`46`	`int max = 1 + Math.max(down,up);`
`51`	`47`	`if(max < minimum){`
`52`	`48`	`minimum = max;`
`53`	`49`	`}`
`54`	`50`	`}`
`55`		`-`
`56`	`51`	`mem[floors][eggs] = minimum;`
`57`	`52`	`return mem[floors][eggs];`
`58`	`53`	`}`
Original file line number	Diff line number	Diff line change
`@@ -15,16 +15,14 @@ public static int lcs(String f,String s,int flen,int slen){`
`15`	`15`	`if(flen == 0 \|\| slen == 0){`
`16`	`16`	`return 0;`
`17`	`17`	`}`
`18`		`-`
`19`		`- int count = 0;`
	`18`	`+ int count;`
`20`	`19`	`if(f.charAt(flen-1) == s.charAt(slen-1)){`
`21`	`20`	`count = 1 + lcs(f,s,flen-1,slen-1);`
`22`	`21`	`}else{`
`23`	`22`	`int right = lcs(f,s,flen-1,slen);`
`24`	`23`	`int left = lcs(f,s,flen,slen-1);`
`25`	`24`	`count = Math.max(right,left);`
`26`	`25`	`}`
`27`		`-`
`28`	`26`	`return count;`
`29`	`27`	`}`
`30`	`28`
Original file line number	Diff line number	Diff line change
`@@ -14,12 +14,11 @@ public static int zeroOne(int[] wts, int[] prs, int cap, int size){`
`14`	`14`	`if(size == 0){`
`15`	`15`	`return 0;`
`16`	`16`	`}`
`17`		`-`
`18`	`17`	`int acc = 0;`
`19`	`18`	`if(wts[size - 1] <= cap){`
`20`		`- acc = prs[size-1] + zeroOne(wts, prs, cap-wts[size-1], size-1);`
	`19`	`+ acc = prs[size-1] +`
	`20`	`+ zeroOne(wts, prs, cap-wts[size-1], size-1);`
`21`	`21`	`}`
`22`		`-`
`23`	`22`	`int reject = zeroOne(wts, prs, cap, size-1);`
`24`	`23`	`return Math.max(acc, reject);`
`25`	`24`	`}`
`@@ -28,22 +27,20 @@ public static int zeroOneDP(int[] wts, int[] prs, int cap, int size, Integer[][]`
`28`	`27`	`if(size == 0){`
`29`	`28`	`return 0;`
`30`	`29`	`}`
`31`		`-`
`32`	`30`	`if(mem[cap][size] != null){`
`33`	`31`	`return mem[cap][size];`
`34`	`32`	`}`
`35`	`33`	`int acc = 0;`
`36`	`34`	`if(wts[size - 1] <= cap){`
`37`		`- acc = prs[size-1] + zeroOneDP(wts, prs, cap-wts[size-1], size-1, mem);`
	`35`	`+ acc = prs[size-1] +`
	`36`	`+ zeroOneDP(wts, prs, cap-wts[size-1], size-1, mem);`
`38`	`37`	`}`
`39`		`-`
`40`	`38`	`int reject = zeroOneDP(wts, prs, cap, size-1, mem);`
`41`	`39`	`mem[cap][size] = Math.max(acc, reject);`
`42`	`40`	`return mem[cap][size];`
`43`	`41`	`}`
`44`	`42`
`45`	`43`	`public static int zeroOneDPitr(int[] wts, int[] prs, int cap, int size, Integer[][] mem){`
`46`		`-`
`47`	`44`	`for (int c = 0; c <= cap; c++) {`
`48`	`45`	`for (int s = 0; s <= size; s++) {`
`49`	`46`	`if(s == 0){`
`@@ -53,7 +50,6 @@ public static int zeroOneDPitr(int[] wts, int[] prs, int cap, int size, Integer[`
`53`	`50`	`if(wts[s - 1] <= c){`
`54`	`51`	`acc = prs[s-1] + mem[c-wts[s-1]][s-1];`
`55`	`52`	`}`
`56`		`-`
`57`	`53`	`int reject = mem[c][s-1];`
`58`	`54`	`mem[c][s] = Math.max(acc,reject);`
`59`	`55`	`}`