4-line O(n) DP C++ solution


  • 1
    L

    The space complexity can be made to O(1), but visually requires more code and is not that illustrative as this one. The DP equation is dp[i] = max(dp[i-2]+currentHouse, dp[i-1])

    class Solution {
    public:
        int rob(vector<int> &num) 
        {
            vector<int> dp(num.size()+1,0);
            for(int i=1;i<=num.size();i++)
                dp[i] = max(i>1?dp[i-2]+num[i-1]:num[0], dp[i-1]);
            return dp[num.size()];
        }
    };

Log in to reply
 

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