Update house-robber.js

lightningtgc · lightningtgc · commit 84e198d90bfa · 2015-06-16T23:55:28.000+08:00
diff --git a/leetcode/house-robber.js b/leetcode/house-robber.js
@@ -1,5 +1,3 @@
-//动态规划的题
-
 /**
  * Question: 
  * You are a professional robber planning to rob houses along a street. 
@@ -13,6 +11,16 @@
  * 
  * /
   
+/**动态规划的题
+ * 
+ * 思路：
+ *  本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。求极值的问题。
+ * 我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和，
+ * 经过分析，可得到递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1])
+ * 
+ * 分别维护两个变量a和b，然后按奇偶分别来更新a和b，这样就可以保证组成最大和的数字不相邻
+
+
   
 /**
  * @param {number[]} nums
@@ -23,13 +31,13 @@ var rob = function(nums) {
         lastRealMax = 0, //上一轮循环中的真正的最大值
         i = nums.length -1;
         
-        while ( 0 <= i) { // eg: [2,1,1,2]
-          var tempLastMaxPV = currMaxPV, //2 0 3
-              realLastMax = lastRealMax; //0 2 2
-          currMaxPV = realLastMax + nums[i];//1 3 4
-          lastRealMax = Math.max(tempLastMaxPV, realLastMax);//2 2 3
+        while ( 0 <= i) { // eg: [6,3,1,6,1]
+          var tempLastMaxPV = currMaxPV, //0 6 3 7 12
+              tempLastMax = lastRealMax; //0 0 6 6 7
+          currMaxPV = tempLastMax + nums[i];//6 3 7 12 8
+          lastRealMax = Math.max(tempLastMaxPV, tempLastMax);//0 6 6 7 12
           i--;
         }
-        return Math.max(currMaxPV, lastRealMax); // 4
+        return Math.max(currMaxPV, lastRealMax); // 12
 };
 
