DP, O(n) time and O(1) space


  • 2

    dp[i]: current max money in place i

    so dp[i] = max(dp[i-2] + num[i], dp[i-1])

    and also we can use two variables a and b to replace dp[i]:

    int rob(vector<int> &num)
    {
        int n = num.size();
        
        if(n == 0)
            return 0;
        else if(n == 1)
            return num[0];
        else if(n == 2)
            return max(num[0], num[1]);
        
        int a = num[0], b = max(num[0], num[1]);
        for(int i = 2; i < n; ++ i)
        {
            int temp = b;
            b = max(a + num[i], b);
            a = temp;
        }
        return b;
    }

Log in to reply
 

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