11/**
2+ * dp[i] = Math.max(dp[i-1], dp[i-2]+num[i-1])
23 *@param {number[] } nums
34 *@return {number }
45 */
@@ -9,24 +10,30 @@ var rob = function(nums) {
910// the robber has not robber the ith house yet.
1011var maxAmount = [ 0 , nums [ 0 ] ] ;
1112for ( var i = 2 ; i <= nums . length ; i ++ ) {
12- maxAmount [ i ] = Math . max ( maxAmount [ i - 1 ] , ( maxAmount [ i - 2 ] + nums [ i - 1 ] ) ) ;
13+ maxAmount [ i ] = Math . max ( maxAmount [ i - 1 ] , ( maxAmount [ i - 2 ] + nums [ i - 1 ] ) ) ;
1314}
1415
1516return maxAmount . pop ( ) ;
1617} ;
1718
1819// O(1) space, O(N) time
20+ // when a robber arrives at a houose, he has two options: rob or not rob. We use two variables (rob, notRob)
21+ // to track the maxAmount of these two options for the house the robber arrived, say ith house,
22+ // and find the max amount from these two values. So, when the robber arrives at ith house, if
23+ // he decided to rob current ith house, then the max amount he can rob is i-1 th house's max amount
24+ // of not robbed plus this house's amount (nums[i]). If he decided not to rob current ith house, then
25+ // the max amount he can rob (or has robbed) at current (ith) house is the maximum value between robbed
26+ // not robber at (i-1)th house.
27+ //
1928var rob = function ( nums ) {
20- if ( nums . length === 0 ) return 0 ;
21- var prevMax = 0 ;
22- // the currMax is the money the robber has robbed when the robber arrives at ith house,
23- // the robber has not robber the ith house yet.
24- var currMax = nums [ 0 ] ;
25- for ( var i = 2 ; i <= nums . length ; i ++ ) {
26- var tmp = currMax ;
27- currMax = Math . max ( currMax , ( prevMax + nums [ i - 1 ] ) ) ;
28- prevMax = tmp ;
29+ var rob = 0 ;
30+ var notRob = 0 ;
31+
32+ for ( var i = 0 ; i < nums . length ; i ++ ) {
33+ var tmp = rob ;
34+ rob = notRobCurrHouse + nums [ i ] ;
35+ notRobCurrHouse = Math . max ( tmp , notRobCurrHouse ) ;
2936}
3037
31- return currMax ;
38+ return Math . max ( rob , notRobCurrHouse ) ;
3239} ;