begeekmyfriend
diff --git a/‎0072_edit_distance/edit_distance.c
Copy file name to clipboardExpand all lines: 0072_edit_distance/edit_distance.c
+14-11Lines changed: 14 additions & 11 deletions b/‎0072_edit_distance/edit_distance.c
Copy file name to clipboardExpand all lines: 0072_edit_distance/edit_distance.c
+14-11Lines changed: 14 additions & 11 deletions
diff --git a/‎0072_edit_distance/edit_distance.cc
Copy file name to clipboardExpand all lines: 0072_edit_distance/edit_distance.cc
+1Lines changed: 1 addition & 0 deletions b/‎0072_edit_distance/edit_distance.cc
Copy file name to clipboardExpand all lines: 0072_edit_distance/edit_distance.cc
+1Lines changed: 1 addition & 0 deletions
diff --git a/‎0300_longest_increasing_subsequence/lis.c
Copy file name to clipboardExpand all lines: 0300_longest_increasing_subsequence/lis.c
+29-1Lines changed: 29 additions & 1 deletion b/‎0300_longest_increasing_subsequence/lis.c
Copy file name to clipboardExpand all lines: 0300_longest_increasing_subsequence/lis.c
+29-1Lines changed: 29 additions & 1 deletion
diff --git a/‎0322_coin_change/coin_change.c
Copy file name to clipboardExpand all lines: 0322_coin_change/coin_change.c
+5-4Lines changed: 5 additions & 4 deletions b/‎0322_coin_change/coin_change.c
Copy file name to clipboardExpand all lines: 0322_coin_change/coin_change.c
+5-4Lines changed: 5 additions & 4 deletions
@@ -31,31 +31,34 @@ static inline int min(int a, int b)
 static int minDistance(char* word1, char* word2)
 {
     int i, j;
-    int len1 = strlen(word1);
-    int len2 = strlen(word2);
-    int *table = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
-    int **dp = malloc((len1 + 1) * sizeof(int *));
-    for (i = 0; i < len1 + 1; i++) {
-        dp[i] = table + i * (len2 + 1);
+    int l1 = strlen(word1);
+    int l2 = strlen(word2);
+    int *table = malloc((l1 + 1) * (l2 + 1) * sizeof(int));
+    int **dp = malloc((l1 + 1) * sizeof(int *));
+
+    for (i = 0; i < l1 + 1; i++) {
+        dp[i] = table + i * (l2 + 1);
     }
 
-    for (i = 0; i < len2 + 1; i++) {
+    dp[0][0] = 0;
+    for (i = 1; i <= l2; i++) {
         dp[0][i] = i;
     }
-    for (i = 0; i < len1 + 1; i++) {
+    for (i = 1; i <= l1; i++) {
         dp[i][0] = i;
     }
 
-    for (i = 1; i < len1 + 1; i++) {
-        for (j = 1; j < len2 + 1; j++) {
+    for (i = 1; i <= l1; i++) {
+        for (j = 1; j <= l2; j++) {
             if (word1[i - 1] == word2[j - 1]) {
                 dp[i][j] = dp[i - 1][j - 1];
             } else {
                 dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
             }
         }
     }
-    return dp[len1][len2];
+
+    return dp[l1][l2];
 }
 
 int main(int argc, char **argv)
 
@@ -26,6 +26,7 @@ class Solution {
                  left_up = up;
             }
         }
+
         return dp[l2];
     }
 };
@@ -2,6 +2,11 @@
 #include <stdlib.h>
 
 
+static int max(int a, int b)
+{
+    return a > b ? a : b;
+}
+
 static int binary_search(int *nums, int lo, int hi, int target)
 {
     while (lo + 1 < hi) {
@@ -15,7 +20,9 @@ static int binary_search(int *nums, int lo, int hi, int target)
     return hi;
 }
 
-int lengthOfLIS(int* nums, int numsSize){
+int lengthOfLIS(int* nums, int numsSize)
+{
+#if 0
     int i, piles = 0;
     int *tops = malloc(numsSize * sizeof(int));
     for (i = 0; i < numsSize; i++) {
@@ -26,6 +33,27 @@ int lengthOfLIS(int* nums, int numsSize){
         tops[pos] = nums[i];
     }
     return piles;
+#else
+    int i, j, res = 0;
+    int *dp = malloc(numsSize * sizeof(int));
+
+    /* dp array records subsequence length of nums[0...i], so we need to
+     * initialize each dp[i] with one element length in the beginning. */
+    for (i = 0; i < numsSize; i++) {
+        dp[i] = 1;
+        for (j = 0; j < i; j++) {
+            if (nums[j] > nums[i]) {
+                dp[i] = max(dp[i], dp[j] + 1);
+            }
+        }
+    }
+
+    for (i = 0; i < numsSize; i++) {
+        res = max(res, dp[i]);
+    }
+
+    return res;
+#endif
 }
 
 int main(int argc, char **argv)
 
@@ -6,13 +6,14 @@ int coinChange(int* coins, int coinsSize, int amount)
 {
     int i, j;
     int *dp = malloc((amount + 1) * sizeof(int));
-    for (i = 1; i <= amount; i++) {
-        /* INT_MAX */
-        dp[i] = amount + 1;
-    }
 
+    /* The dp array records minimum coin number corresponding to the
+     * amount of coins. So we need to initialize each dp[i] with
+     * amount + 1 as an invalid value */
     dp[0] = 0;
     for (i = 1; i <= amount; i++) {
+        /* initialized with INT_MAX */
+        dp[i] = amount + 1;
         for (j = 0; j < coinsSize; j++) {
             if (i - coins[j] >= 0) {
                 int tmp = 1 + dp[i - coins[j]];
Original file line number	Diff line number	Diff line change
`@@ -31,31 +31,34 @@ static inline int min(int a, int b)`
`31`	`31`	`static int minDistance(char* word1, char* word2)`
`32`	`32`	`{`
`33`	`33`	`int i, j;`
`34`		`- int len1 = strlen(word1);`
`35`		`- int len2 = strlen(word2);`
`36`		`- int table = malloc((len1 + 1) (len2 + 1) * sizeof(int));`
`37`		`- int *dp = malloc((len1 + 1) sizeof(int *));`
`38`		`- for (i = 0; i < len1 + 1; i++) {`
`39`		`- dp[i] = table + i * (len2 + 1);`
	`34`	`+ int l1 = strlen(word1);`
	`35`	`+ int l2 = strlen(word2);`
	`36`	`+ int table = malloc((l1 + 1) (l2 + 1) * sizeof(int));`
	`37`	`+ int *dp = malloc((l1 + 1) sizeof(int *));`
	`38`	`+`
	`39`	`+ for (i = 0; i < l1 + 1; i++) {`
	`40`	`+ dp[i] = table + i * (l2 + 1);`
`40`	`41`	`}`
`41`	`42`
`42`		`- for (i = 0; i < len2 + 1; i++) {`
	`43`	`+ dp[0][0] = 0;`
	`44`	`+ for (i = 1; i <= l2; i++) {`
`43`	`45`	`dp[0][i] = i;`
`44`	`46`	`}`
`45`		`- for (i = 0; i < len1 + 1; i++) {`
	`47`	`+ for (i = 1; i <= l1; i++) {`
`46`	`48`	`dp[i][0] = i;`
`47`	`49`	`}`
`48`	`50`
`49`		`- for (i = 1; i < len1 + 1; i++) {`
`50`		`- for (j = 1; j < len2 + 1; j++) {`
	`51`	`+ for (i = 1; i <= l1; i++) {`
	`52`	`+ for (j = 1; j <= l2; j++) {`
`51`	`53`	`if (word1[i - 1] == word2[j - 1]) {`
`52`	`54`	`dp[i][j] = dp[i - 1][j - 1];`
`53`	`55`	`} else {`
`54`	`56`	`dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));`
`55`	`57`	`}`
`56`	`58`	`}`
`57`	`59`	`}`
`58`		`- return dp[len1][len2];`
	`60`	`+`
	`61`	`+ return dp[l1][l2];`
`59`	`62`	`}`
`60`	`63`
`61`	`64`	`int main(int argc, char **argv)`
Original file line number	Diff line number	Diff line change
`@@ -26,6 +26,7 @@ class Solution {`
`26`	`26`	`left_up = up;`
`27`	`27`	`}`
`28`	`28`	`}`
	`29`	`+`
`29`	`30`	`return dp[l2];`
`30`	`31`	`}`
`31`	`32`	`};`