DP C++, space O(1)


  • 1

    f[i] = max(f[i-2] + nums[i], f[i-1]),
    ppre = f[i-2], pre = f[i-1].

    int rob(vector<int>& nums)
    {
            if(nums.empty())
                    return 0;
    
            int ppre = 0;
            int pre = 0;
            int cur = 0;
    
            for(int i = 0; i < nums.size(); ++i)
            {
                    cur = max(ppre + nums[i], pre);
                    ppre = pre;
                    pre = cur;
            }
    
            return cur;
    
    }
    
    

Log in to reply
 

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