DP C++ O(n) in both time and space, need to use a table


  • 0
    T

    We make a table size n, which contains all the maximum of money robbed from house 0 to house 'i', and another value 'rob' to know this last house is robbed or not.
    If it is robbed,

        int rob(vector<int>& nums) {
            if (nums.empty()) return 0;
            
            int* DP = new int[nums.size()]; //contain the maximum value robbered from house 0 the house i
            
            DP[0] = nums[0];
            bool rob;
            if (nums[1] > nums[0]) {
                rob = true;
                DP[1] = nums[1];
            }
            else{
                rob = false;
                DP[1] = nums[0];
            }
            
            int size = nums.size();
            
            for (int i=2; i < size; i++){
                if (rob && nums[i] + DP[i-2] >= DP[i-1]){
                    DP[i] = nums[i] + DP[i-2];
                }
                else if (rob && nums[i] + DP[i-2] < DP[i-1]){
                    rob = false;
                    DP[i] = DP[i-1];
                }
                else if (!rob) {
                    DP[i] = DP[i-1] + nums[i];
                    rob = true;
                }
            }
    
            return DP[size-1];
        }
    

  • 0
    T

    The solution with O(1) in space. Base on the idea that, if the last house is not robbed, then the value of the last house and its previous house is equal.

    int rob(vector<int>& nums) {
            if (nums.empty()) return 0;
            
            int rob1 = nums[0];
            int currRob = rob1;
            if (nums.size() == 1) return currRob;
            int rob2 = nums[1]>nums[0] ? nums[1]:nums[0];
            currRob = rob2;
            int size = nums.size();
            
            for (int i=2; i < size; i++){
                if (rob2 == rob1) { //not rob the last house
                    currRob += nums[i];
                    rob1 = rob2;
                    rob2 = currRob;
                }
                else if (rob1 + nums[i] > rob2) {
                    currRob = rob1 + nums[i];
                    rob1 = rob2;
                    rob2 = currRob;
                }
                else{
                    currRob = rob2;
                    rob1 = rob2;
                }
            }
            return currRob;
        }
    

Log in to reply
 

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