Problem & Approach

  1. House Robber

The optimal approach is to use Dynamic Programming. As for this problem, when we deal with n-th house, we can choose it or leave it. But when we choose the nth house, the answer of (n-2)-th house can be used to get current answer; when leave n-th house, we can use (n-1)-th house’s answer as current one.

So, more specifically, the solution is dp[i] = max(dp[i - 1], dp[i - 2] + house[i]).

Suppose we have these houses {5,1,2,4}. We can start from left to right and use above concept to solve it. Then we can get this table:

0 1 2 3
5 5 = max(1, 5) 7 = max(2 + 5, 5) 9 = max(4 + 5, 7)

As shown in the table, in each column, the first element in the max means we choose current house, and the second one means don’t choose current one.

  1. House Robber II

The optimal approach is to use Dynamic Programming too. Given a list of houses, the point is to how to deal with the first house when we are thinking about the last house. So, we can define dp[i][0] means the last answer for sublist from 0 to index i and more importantly 0 means the first house isn’t chosen. And dp[i][1] is similar but 1 means the first house must be chosen.

Then,

if(index != len - 1){
    dp[i][0] = Math.max(dp[i - 2][0] + nums[i], dp[i - 1][0]);
    dp[i][1] = Math.max(dp[i - 2][1] + nums[i], dp[i - 1][1]);
} else {
    dp[i][0] = Math.max(dp[i - 2][0] + nums[i], dp[i - 1][0]);
    dp[i][1] = Math.max(dp[i - 2][1], dp[i - 1][1]);
}

Code

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