My C++ code (O(1) space and O(n) time), with explanation


  • 0
    D

    The basic idea is use an array "state" to track the state at each step i: state[0] is the state at which the robber can rob (i+1)-th house, state[1] is the state at which the robber cannot rob the (i+1)-th house since he/she robs the (i)-th house. The state transition is
    at the (i+1)-th stage, state[0]-> state[0], if no robbery at the i-th stage ; state[0]-> state[1], if a robbery occurs at the i-th stage
    state[1]-> state[0], if no robbery at the i-th stage ; state[1]-> state[1], not possible

    class Solution {
    public:
        int rob(vector<int> &num) {
            int len = num.size();
            
            if(len <=0) return 0;
            else if(len==1) return num[0];
            else
            {
                int i, temp, state[2];
                state[0] = 0;
                state[1] = num[0];
                
                for(i=1; i<len; i++)
                {
                    temp = state[0];
                    state[0] = state[0]>state[1] ? state[0]:state[1];
                    state[1] = temp+num[i];
                }
                
                return state[0] > state[1]? state[0] : state[1]; 
            }
        }
    };

Log in to reply
 

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