House Robber 打家劫舍

     public int rob(int[] nums) {
         //一维dp
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        }

        int[] dp = new int[n + 1];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }

    public int robOPT(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } 
        int dp_i_0 = 0, dp_i_1 = 0;
        int dp_i = 0;
        for (int num : nums) {
            dp_i = Math.max(dp_i_1, dp_i_0 + num);
            dp_i_0 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
        //int first = nums[0], second = Math.max(nums[0], nums[1]);
        //for (int i = 2; i < length; i++) {
        //    int temp = second;
        //    second = Math.max(first + nums[i], second);
        //    first = temp;
        //}
        //return second;

    public int rob2(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        //分成两部分去解决问题 , 偷nums[0]不偷n , 偷nums[1]就正常进行
        return Math.max(robDist(nums, 0, n - 2), robDist(nums, 1, n - 1));
    }

    private int robDist(int[] nums, int begin, int end) {
        int first = nums[begin], second = Math.max(nums[begin], nums[begin + 1]);
        for (int i = begin + 2; i <= end; i++) {
            int tmp = second;
            second = Math.max(first + nums[i], second);
            first = tmp;
        }
        return second;
    }

    //在二叉树上rob
    Map<TreeNode, Integer> memos = new HashMap<>();

    public int rob3(TreeNode root) {
        return robTree(root);
    }

    private int robTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (memos.containsKey(root)) {
            return memos.get(root);
        }

        int rob = root.val + (root.left == null ? 0 : robTree(root.left.left) + robTree(root.left.right)) +
                (root.right == null ? 0 : robTree(root.right.left) + robTree(root.right.right));
        int not = robTree(root.left) + robTree(root.right);
        int ans = Math.max(rob, not);
        memos.put(root, ans);
        return ans;
    }

    public int rob3OPT(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    /* 返回一个大小为 2 的数组 arr
    arr[0] 表示不抢 root 的话，得到的最大钱数
    arr[1] 表示抢 root 的话，得到的最大钱数
    */
    public int[] dp(TreeNode root) {
        if (root == null)
            return new int[]{0, 0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);

        int rob = root.val + left[0] + right[0];
        int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{not_rob, rob};
    }