你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素
    就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报
    警。
    给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷
    窃到的最高金额。 

    1. 输入：[1,2,3,1] 输出：4 
    2. 输入：[2,7,9,3,1] 输出：12
    1. static int maxMoney(int[] nums, int index) {
    2.     if ((nums == null) || (index < 0)) {
    3.         return 0;
    4.     }
    6.     if (index == 0) {
    7.         return nums[0];
    8.     }
    10.     return Math.max(maxMoney(nums, index - 2) + nums[index],
    11.                     maxMoney(nums, index - 1));
    12. }
    14. static int maxMoney(int[] nums) {
    15.     if ((nums == null) || (nums.length == 0)) {
    16.         return 0;
    17.     }
    19.     int length = nums.length;
    21.     if (length == 1) {
    22.         return nums[0];
    23.     } /*int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); }return dp[length - 1];*/
    24.     int first = nums[0];
    25.     int second = Math.max(nums[0], nums[1]);
    27.     for (int i = 2; i < length; i++) {
    28.         int temp = second;
    29.         second = Math.max(first + nums[i], second);
    30.         first = temp;
    31.     }
    33.     return second;
    34. }

    如果房子首尾相连：

    1. public int rob(int[] nums) {
    2.     int length = nums.length;
    4.     if (length == 1) {
    5.         return nums[0];
    6.     } else if (length == 2) {
    7.         return Math.max(nums[0], nums[1]);
    8.     }
    10.     return Math.max(robRange(nums, 0, length - 2),
    11.                     robRange(nums, 1, length - 1));
    12. }
    14. public int robRange(int[] nums, int start, int end) {
    15.     int first = nums[start];
    16.     int second = Math.max(nums[start], nums[start + 1]);
    18.     for (int i = start + 2; i <= end; i++) {
    19.         int temp = second;
    20.         second = Math.max(first + nums[i], second);
    21.         first = temp;
    22.     }
    24.     return second;
    25. }
    1. public int rob(TreeNode root) {
    2.     int[] rootStatus = dfs(root);
    4.     return Math.max(rootStatus[0], rootStatus[1]);
    5. }
    7. public int[] dfs(TreeNode node) {
    8.     if (node == null) {
    9.         return new int[] { 0, 0 };
    10.     }
    12.     int[] l = dfs(node.left);
    13.     int[] r = dfs(node.right);
    14.     int selected = node.val + l[1] + r[1];
    15.     int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    17.     return new int[] { selected, notSelected };
    18. }