Twice pass solution, C++


  • 35

    Twice pass:

    1. not rob nums[n-1]
    2. not rob nums[0]

    and the other is same as House Robber.

    int rob(vector<int>& nums)
    {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return nums[0];
        
        int pre1 = 0, cur1 = 0;
        for(int i = 0; i < nums.size() - 1; ++ i)
        {
            int temp = pre1;
            pre1 = cur1;
            cur1 = max(temp + nums[i], pre1);
        }
        
        int pre2 = 0, cur2 = 0;
        for(int i = 1; i < nums.size(); ++ i)
        {
            int temp = pre2;
            pre2 = cur2;
            cur2 = max(temp + nums[i], pre2);
        }
        
        return max(cur1, cur2);
    }

  • 1
    A

    clever code. But the explanation seems confused. Maybe this is better:

    1. not rob num[0]
      2.not rob num[n-1]
      Note that num[0] and num[n-1] can't robbed at the same time, so the division is complete.

  • 0
    S

    The same idea with you

     class Solution {
        public:
            // start is 0 or 1
            int work(vector<int> &nums, int start) {
                int n = nums.size();
                if (n < start + 1) return 0;
                if (n == start + 1) return nums[start];
                if (n == start + 2) return max(nums[start], nums[start+1]);
                if (start == 0)
                    --n;
                vector<int> dp(n, 0);
                dp[start] = nums[start];
                dp[start+1] = max(nums[start], nums[start+1]);
                for (int i = start+2; i < n; i++) 
                    dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
                return dp.back();
            }
            
            int rob(vector<int>& nums) {
                if (nums.size() == 0) return 0;
                return max(work(nums, 0), work(nums, 1));
            }
        };

  • 0
    X

    What is the length of the array is two?

    The answer is zero or the max of the two

    Are they adjacnet?


  • 0

    oh, aha, yes, rob nums[0] means not rob nums[n-1]


  • 0

    If the length of the array is two, then cur1 will be nums[0] and cur2 will be nums[1], so the answer is max(cur1, cur2).


  • 0
    X

    But they are adjcent,so none of them can be robbed,

    Am I right?


  • 0
    C

    I came up with a very similar two pass solution. I just modified my House Robber I solution to force robbing the 0th house (or not). Some special care needs to be taken on last house, depending on whether I robbed 0th house or not.

    class Solution {
    public:
        //if force0Rob is true,  I HAVE to     rob 0-th house
        //if force0Rob is false, I HAVE to NOT rob 0th house
        int robPrime(vector<int>& nums, bool force0Rob) {
            
            //dynamic programming cache; money made by robbing *optimal choices* of houses until index i
            vector<int> money(nums.size(), 0);
            money[0] = force0Rob ? nums[0] : 0;
            money[1] = force0Rob ? nums[0] : nums[1];
            
            //dynamic programming loop
            for (int i=2; i<nums.size()-1; i++) {
                int cand1 = nums[i] + money[i-2];
                int cand2 = money[i-1];
                money[i] = cand1 > cand2 ? cand1 : cand2;
            }
            
            //last place
            int last = nums.size() - 1;
            int lastbutone = nums.size() - 2;
            int lastbuttwo = nums.size() - 3;
            money[last] = force0Rob ? (max(money[lastbutone], money[lastbuttwo])) 
                                    : (max(money[lastbutone], money[lastbuttwo] + nums[last]));
            return money[last];
        }
        int rob(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            if (nums.size() == 1) return nums[0];
            if (nums.size() == 2) return max(nums[0], nums[1]);
            return (max(robPrime(nums, true), robPrime(nums, false)));
        }
    }; 

  • 0
    M

    The optimal solution may be not rob 0 and not rob n-1. Division "rob 0" and "not rob 0" may not cover the optimal solution. Rob 0 should be num[0] + HouseRobber(num[2...n-2]).
    But your code is correct. Thanks.


  • 0

    yeah, now I have modify it.


  • 0
    D

    They are adjacent, so one of them (not both) can be robbed.


  • 0
    X
    class Solution {
    public:
        int rob(vector<int>& nums) {
    		if(nums.size() == 1) return nums[0];
            int opt1 = rob1(nums, 0, nums.size() - 2);
            int opt2 = rob1(nums, 1, nums.size() - 1);
            //cout << opt1 << " " << opt2 << endl;
            return max(opt1, opt2);
        }
    	int rob1(vector<int>& nums, int start, int end) {
            if (end < start) return 0; //edge case
            vector<int> result;
            for (int i = start; i <= end; i++){
                if (i == start) result.push_back(nums[start]);
                else if (i == start + 1) result.push_back(max(nums[start+1], nums[start]));
                else{
                    result.push_back(max(result[result.size() - 1], result[result.size() - 2] + nums[i]));
                }
            }
            return result[result.size() - 1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.