1. House Robber

You are a professional robber planning to rob houses along a street. line

public class Solution {

    public int rob(int[] nums) {

        int curNo = 0, curYes = 0;
        int preNo = 0, preYes = 0;

        for(int num: nums){

            preNo = curNo;
            preYes= curYes;

            curYes= preNo + num;
            curNo = Math.max(preNo, preYes);
        }

        return Math.max(curYes, curNo);
    }

}

public class Solution {

    Integer[] dp;

    public int rob(int[] nums) {

        int n = nums.length;
        dp    = new Integer[n];
        return rec(nums, 0);
    }

    public int rec(int[] nums, int s) {

        if(s >= nums.length)
            return 0;

        if(dp[s] != null)
            return dp[s];

        int curNo = rec(nums, s + 1);
        int curYes= nums[s] + rec(nums, s + 2);

        dp[s] = Math.max(curNo, curYes);
        return dp[s];
    }
}

2. House Robber II

all houses at this place are arranged in a circle

public class Solution {
    public int rob(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0], nums[1]);

        return Math.max(rob1(nums,0,nums.length-2), rob1(nums,1,nums.length-1));
    }

    public int rob1(int[] nums, int s, int e) {

        int curNo = 0, curYes = 0;
        int preNo = 0, preYes = 0;

        for(int i = s; i <= e; i ++){

            preNo = curNo;
            preYes= curYes;

            curYes= preNo + nums[i];
            curNo = Math.max(preNo, preYes);
        }

        return Math.max(curYes, curNo);
    }
}

3. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, 
called the "root." Besides the root, each house has one and only one parent house. After a tour, 
the smart thief realized that "all houses in this place forms a binary tree". 
It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
     3
    / \
   2   3
    \   \ 
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

/*dfs all the nodes of the tree, each node return two number, int[] num, 
    num[0] is the max value while rob this node, 
    num[1] is max value while not rob this value. Current node return value only depend on its
         children's value. Transform function should be very easy to understand.
*/

public class Solution {
    public int rob(TreeNode root) {

        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    public int[] dfs(TreeNode node) {

        if(node == null) return new int[2];

        int[] left = dfs(node.left);
        int[] right= dfs(node.right);

        int[] res = new int[2];
        res[0] = node.val + left[1] + right[1];
        res[1] = Math.max(left[0], left[1]) + Math.max(right[1], right[0]);
        return res;
    }
}