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.

思路

1. 根據(jù)題目项乒，因?yàn)椴荒苓B續(xù)偷兩家股缸，所以：有兩種可能惭每，偷當(dāng)前家可以最大獲利，或者不偷當(dāng)前家可以最大獲利。
2. 偷當(dāng)前家的最大獲利 = max（【偷上一家的再上一家的maxProfit + 當(dāng)前家的財(cái)產(chǎn)】，不偷當(dāng)前家（即偷上一家的最大獲利））
3. 用DP锋叨，dp[i] 表示偷第i家獲得的最大利益
4. 初始化時(shí)含鳞，必須初始化dp[0], dp[1], 因?yàn)樵谇?code>dp[i]的時(shí)候城丧，我們必須知道偷上一家和偷上上家的獲利延曙。所以循環(huán)只能從2開始。0和1必須被初始化亡哄。

class Solution {
    public int rob(int[] nums) {
        //用DP
        //因?yàn)椴荒苓B續(xù)偷兩家枝缔，所以：有兩種可能，偷當(dāng)前價(jià)可以最大獲利蚊惯，或者不偷當(dāng)前價(jià)可以最大獲利
        //偷當(dāng)前家的最大獲利 = max（【偷上一家的再上一家的maxProfit + 當(dāng)前家的財(cái)產(chǎn)】愿卸，不偷當(dāng)前家（即偷上一家的最大獲利））
        //dp[i]: 偷第i家的最大獲利
        
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        
        int[] dp = new int[nums.length];
        //循環(huán)只能從2開始，因?yàn)楸仨氈郎弦患?和 上上一家偷的情況
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

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.

思路 （遞歸）

與1思路相同截型，對(duì)于每個(gè)節(jié)點(diǎn)小偷都可以選擇偷或者不偷趴荸，那么對(duì)每個(gè)節(jié)點(diǎn)都返回一個(gè)int[2], result[0]表示偷這家能獲取的最大利益，result[1]表示不偷這家能獲取的最大利益宦焦。

1. DFS搜索：遞歸停止條件发钝，root == null 時(shí)返回new int[2]：表示偷與不偷的獲利都為0.
2. DFS計(jì)算其left和right child的獲利結(jié)果。
3. 當(dāng)前節(jié)點(diǎn)偷(那么左右節(jié)點(diǎn)都不能偷): cur.val + leftProfit[1] + rightProftit[1]波闹。
4. 當(dāng)前節(jié)點(diǎn)不偷（左右節(jié)點(diǎn)可以偷酝豪， 也可以不偷）：Max(leftProfit[0], leftProfit[1]) + Max(rightProfit[0], rightProfit[1])
5. 最后返回root節(jié)點(diǎn)偷或者不偷的最大值即可

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  
  public TreeNode(int val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}


class Solution{
  static public int rob(TreeNode root) {
    if (root == null) return 0;
    
    int[] result = helper(root);
    return Math.max(result[0], result[1]);
  }
  
  static public int[] helper(TreeNode root) {
    if (root == null) {
      return new int[2];
    }
    
    // index 0: rob, index 1: not rob
    int[] leftProfit = helper(root.left);
    int[] rightProfit = helper(root.right);
    int[] result = new int[2];
    
    // rob: cannot rob the neighbor
    result[0] = root.val + leftProfit[1] + rightProfit[1];
    
    // not rob: can rob the neighbor, or not rob the neighbor; choose the bigger profit
    result[1] = Math.max(leftProfit[0], leftProfit[1]) + Math.max(rightProfit[0], rightProfit[1]);
    
    return result;
  }
  
  public static void main(String[] args) {
    TreeNode root = new TreeNode(3);
    TreeNode n1 = new TreeNode(2);
    TreeNode n2 = new TreeNode(3);
    root.left = n1;
    root.right = n2;
    
    TreeNode n3 = new TreeNode(4);
    TreeNode n4 = new TreeNode(5);
    
    n1.left = n3;
    n1.right = n4;
    
    TreeNode n5 = new TreeNode(1);
    n2.right = n5;
    
    System.out.println(rob(root));
    
  }
}