House Robber

198 House Robber

Given a list of non-negative integers represent the money in house, determine the maximum amount of money you can rob but not rob 2 continuous house

• Space O(n)

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

• Space O(1)

  public int rob(int[] nums) {
    int curMax = 0;
    int preMax = 0;
    for(int n: nums){
        int tmp = curMax;
        curMax = Math.max(curMax, preMax + n);
        preMax = tmp;
    }
    return curMax;
  }

213. House Robber II

Same as house robber, but the first and the last house are connected

• Break the circle, find the max of dp[n-1], dp[n]

public int rob(int[] nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    return Math.max(helper(nums, 0, nums.length-1), helper(nums, 1, nums.length)); 
}

private int helper(int[] nums, int start, int end){
    int preMax = 0, curMax = 0;
    for(int i=start; i<end; i++){
        int tmp = curMax;
        curMax = Math.max(curMax, preMax + nums[i]);
        preMax = tmp;
    }
    return curMax;
}