My 0 ms DP solution


  • 1
    H

    DP solution with two additional variables, instead of memorisation which will exceed the time limit in test case.

    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int twoAway = 0;       // the money robbed that is two houses away from current robbed house
        int oneAway = nums[0]; // the money robbed that is one houses away from current robbed house
        int opt = nums[0];
        for ( int i = 1; i < nums.size(); i++) {
            opt = max(twoAway + nums[i], oneAway);
            // step the 
            twoAway = oneAway;
            oneAway = opt;
        }
        return opt;
        /*
        vector<int> money(nums.size()+1); // save the money robbed from first n houses
        return robHelper(nums, money, nums.size());
        */
    
    
    // memoraztion exceeds the time limit ! Actually only two variable are needed during comparison.
    /*
    int robHelper(vector<int>& nums, vector<int>& money, int n) {
        if ( n <= 0 ) return 0;
        else if ( money[n] > 0) return money[n];
        else {
            money[n] = max(robHelper(nums, money, n-2)+ nums[n-1], robHelper(nums, money, n-1));
        }
        return money[n];
    }
    */
    

    };


Log in to reply
 

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