1. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police

DP: while robbing i-th house, the max value is either rob the i-th house and the max value BEFORE the previous houses, or don't rob i-th house, and max value of robbing all previous houses

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length < 2) return nums[0];

        int[] res = new int[nums.length];
        res[0] = nums[0];
        res[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for(int i=2; i< nums.length; i++){
            res[i] = Math.max(res[i-2] + nums[i], res[i-1]); 
        }

        return res[nums.length-1];

    }
}

using constant space. you only need prev max, current max, in the next round, prev + nums[i] will be the current, and max(prev, current) will the prev.

public class Solution {
    public int rob(int[] nums) {
        if(nums ==null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        int prev=0; // res[i-1]
        int cur=0; // res[i];


        for(int i=0; i< nums.length;i++){
            int m = prev, n = cur;
            cur = prev + nums[i];
            prev = Math.max(m,n);
        }

        return Math.max(cur,prev);
    }
}

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = nums[0] > nums[1] ? nums[0] : nums[1];

        for(int i=2; i< nums.length; i++){
            int tmp = prev1;
            prev1 = Math.max(nums[i]+prev2, prev1);
            prev2 = tmp;
        }
        return prev1;
    }
}