class Solution {
    //动态规划4步：1.确定dp数组及下标的含义
    // 2.确定递推公式
    // 3.dp数组如何初始化
    // 4.确定遍历顺序
    // 偷窃当前房屋，不偷窃当前房屋
    // dp[i] 代表从0-i间房偷窃获得的最大值是多少
    // dp[i] = Math.max(dp[i-1], dp[i-2] +nums[i]);
    // dp[0] = nums[0], dp[1] = Math.max(nums[1], nums[0]);
    //
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[n];
        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-1], dp[i - 2] + nums[i]); //对于每到一下个房间有两种可能，1.偷当前房间， 2.不偷当前房间
        }
        return dp[n-1];
    }
}

class Solution {
	public int rob(int[] nums) {  
		int n = nums.length;  
		Integer[] memo = new Integer[n]; // 记忆化数组  
		return dfs(nums, 0, memo);  
	}  
  
	private int dfs(int[] nums, int i, Integer[] memo) {  
		if (i >= nums.length) return 0;  //超出边介
		if (memo[i] != null) return memo[i];  
		  
		// 偷当前房子  
		int take = nums[i] + dfs(nums, i + 2, memo);  
		// 不偷当前房子  
		int notTake = dfs(nums, i + 1, memo);  
		  
		memo[i] = Math.max(take, notTake);  
		return memo[i];  
	}
}