打家劫舍问题

还是动态规划

假想你就是这个专业强盗，从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。

如果你抢了这间房子，那么你肯定不能抢相邻的下一间房子了，只能从下下间房子开始做选择。

如果你不抢这间房子，那么你可以走到下一间房子前，继续做选择。

当你走过了最后一间房子后，你就没得抢了，能抢到的钱显然是 0（base case）。

以上的逻辑很简单吧，其实已经明确了「状态」和「选择」：你面前房子的索引就是状态，抢和不抢就是选择。

「状态」：面前房子的索引

「选择」：抢或不抢

	//自顶向下
	public int dp(int[] nums, int start) {
		int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));
		return res;
	}
	//自底向上
	public int rob(int[] nums) {
      int n = nums.length;
      int[] dp = new int[n + 2];
      for (int i = n - 1; i >= 0; i--) {
          dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
      }
      return dp[0];
  }
//当前状态转移只和dp[i]后两间相关 优化空间O(1)
  public int rob2(int[] nums) {
      int n = nums.length;
      int dp_i_1 = 0;
      int dp_i_2 = 0;
      int dp_i = 0;
      for (int i = n - 1; i >= 0; i--) {
          dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
          dp_i_2 = dp_i_1;
          dp_i_1 = dp_i;
      }
      return dp_i;
  }
  //二叉树题
  /**
   * [0]:不抢root
   * [1]:抢root
   */
  int[] dp(TreeNode root) {
      if (root == null) {
          return new int[]{0, 0};
      }
      int[] left = dp(root.left);
      int[] right = dp(root.right);
      //抢root 下家就不能抢
      int rob = root.val + left[0] + right[0];
      //不抢root 下家可以抢
      int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
      return new int[]{not_rob, rob};
  }