198. House Robber.md

Solution1 (dp)

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int prev1 = 0;
        int prev2 = 0;
        for (int num : nums) {
            int temp = Math.max(num + prev1, prev2);
            prev1 = prev2;
            prev2 = temp;
        }
        return prev2;
    }
}

note

• time O(n) space O(1)
• The idea is actually dp, specifically iterative bottom-up approach with memo, in our case, memo is two variables. The idea is from this post: https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.