[C++] Super Simple 0ms solution with explanation


  • 32
    M

    Since you cannot rob both the first and last house, just create two separate vectors, one excluding the first house, and another excluding the last house. The best solution generated from these two vectors using the original House Robber DP algorithm is the optimal one.

    class Solution {
    public:
    
        int robOriginal(vector<int>& nums) {
            int a = 0, b = 0, res = 0;
            
            for(int i = 0; i < nums.size(); ++i){
                res = max(b + nums[i], a);
                b = a;
                a = res;
            }
            
            return res;
        }
    
        int rob(vector<int>& nums) {
            if(nums.empty()) return 0;
            if(nums.size() == 1) return nums[0];
            
            vector<int> numsA(nums.begin() + 1, nums.end());
            vector<int> numsB(nums.begin(), nums.end()-1);
            
            return max(robOriginal(numsA), robOriginal(numsB));
        }
    };

  • 0
    H

    What if the solution starts at index 4 and ends at index 2 ?


  • 0
    G

    quite an easy solution! Thank you!


  • 0

    Good thought


  • 0
    R

    same idea here in this way .

    int  houseRob(vector<int>&a , int l ,  int h){
            int oneStepBack = 0; 
            int twoStepBack = 0;
            int MaxRob = 0;
            for(int i=l ; i<=h ; i++){
                MaxRob = max( twoStepBack+a[i] , oneStepBack);
                twoStepBack = oneStepBack;
                oneStepBack = MaxRob;
            }
            return MaxRob;
        }
        int rob(vector<int>& a) {
            if(a.size() == 0) return 0;
            if(a.size() == 1) return a[0]; 
            return max( houseRob(a , 0 , a.size()-2) , houseRob(a , 1 , a.size()-1));
        }

Log in to reply
 

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