Refine

begeekmyfriend · begeekmyfriend · commit ebdeffe537fd · 2020-06-12T08:58:11.000+08:00
Signed-off-by: begeekmyfriend &lt;begeekmyfriend@gmail.com&gt;
diff --git a/198_house_robber/robber.c b/198_house_robber/robber.c
@@ -9,20 +9,22 @@ static inline int max(int a, int b)
 
 static int rob(int* nums, int numsSize)
 {
-    int i;
-    int **money = malloc((numsSize + 1) * sizeof(int *));
-    for (i = 0; i < numsSize + 1; i++) {
-        money[i] = malloc(2 * sizeof(int));
-        memset(money[i], 0, 2 * sizeof(int));
+    if (numsSize == 0) {
+        return 0;
     }
 
-    for (i = 1; i <= numsSize; i++) {
-        int cash = nums[i - 1];
-        money[i][0] = max(money[i - 1][0], money[i - 1][1]);
-        money[i][1] = money[i - 1][0] + cash;
+    int i;
+    int taken = nums[0];
+    int untaken = 0;
+    /* Record max profits of nums[0...i] respectively */
+    for (i = 1; i < numsSize; i++) {
+        int tmp_taken = taken;
+        int tmp_untaken = untaken;
+        taken = untaken + nums[i];
+        untaken = max(tmp_taken, tmp_untaken);
     }
 
-    return max(money[numsSize][0], money[numsSize][1]);
+    return max(taken, untaken);
 }
 
 int main(int argc, char **argv)
diff --git a/213_house_robber_ii/robber.c b/213_house_robber_ii/robber.c
@@ -10,19 +10,17 @@ static inline int max(int a, int b)
 static int _rob(int* nums, int numsSize)
 {
     int i;
-    int **money = malloc((numsSize + 1) * sizeof(int *));
-    for (i = 0; i < numsSize + 1; i++) {
-        money[i] = malloc(2 * sizeof(int));
-        memset(money[i], 0, 2 * sizeof(int));
+    int taken = nums[0];
+    int untaken = 0;
+    /* Record max profits of nums[0...i] respectively */
+    for (i = 1; i < numsSize; i++) {
+        int tmp_taken = taken;
+        int tmp_untaken = untaken;
+        taken = tmp_untaken + nums[i];
+        untaken = max(tmp_taken, tmp_untaken);
     }
 
-    for (i = 1; i <= numsSize; i++) {
-        int cash = nums[i - 1];
-        money[i][0] = max(money[i - 1][0], money[i - 1][1]);
-        money[i][1] = money[i - 1][0] + cash;
-    }
-
-    return max(money[numsSize][0], money[numsSize][1]);
+    return max(taken, untaken);
 }
 
 static int rob(int* nums, int numsSize)
@@ -32,6 +30,7 @@ static int rob(int* nums, int numsSize)
     } else if (numsSize == 1) {
         return nums[0];
     } else {
+        /* The first and the last element are adjacent */
         return max(_rob(nums + 1, numsSize - 1), _rob(nums, numsSize - 1));
     }
 }
