你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

 

思路：

1.暴力递归

从前往后  包括要当前值和不要，要了就隔两个 位置

public static int rob(int[] nums) {
		int res = 0;
		return process(nums, 0, res);
	}

	private static int process(int[] nums, int i, int res) {
		if (i > nums.length - 1) {
			return res;
		}
		// 要当前值:就隔两个 和 不要当前值
		res = Math.max(res + nums[i] + process(nums, i + 2, res), res + process(nums, i + 1, res));
		return res;
	}

从后往前的递归

// 也是递归  每个位置 由之前的 和  隔两个的决定
	public int rob(int[] nums) {
	    return rob(nums, nums.length - 1);
	}
	private int rob(int[] nums, int i) {
	    if (i < 0) {
	        return 0;
	    }
	    return Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
	}

2.暴力递归改动态规划

动态规划 dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]); 要当前 不要当前值 

public static int rob(int[] nums) {
		if (nums.length == 0)
			return 0;
		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (i == 1) {
				dp[i] = Math.max(dp[0], nums[1]);
			} else {
				dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
			}
		}
		return dp[nums.length - 1];
	}