O(n) dynamic solution with O(1) memory


  • 1
    P
    class Solution {
    public:
        int rob(vector<int>& num) {
        	if (num.empty()) {
        		return 0;
        	}
        	int a[2] = {num[0], 0}; // { 'rob_current', 'do_not_rob_current' }
            for (int i = 1; i < num.size(); ++i) {
            	int t = std::max(a[0], a[1]);
            	a[0] = num[i] + a[1];
            	a[1] = t;
            }
            return std::max(a[0], a[1]);
        }
    };
    

    at each step,

    1. if we rob the current house, we shouldn't rob the previous one (cur[0] = prev[1] + num[i] )
    2. if we do not rob the house, we may or may not rob the previous one, therefore take maximum (cur[1] = max(prev[0], prev[1]) )

Log in to reply
 

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