• 链状

    输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
   偷窃到的最高金额 = 2 + 9 + 1 = 12 。
    解析:动态规划。1dp[i]为偷第i家时最大金额。2若是0，1的情况作出特殊说明，减少计算。3dp[i] = Math.max(dp[i-1],dp[i-2]+nums[])
    class Solution {
  public int rob(int[] nums) {
      //0的情况
      if(nums.length == 0){
          return 0;
      } 
       //1的情况，减少计算
      if(nums.length == 1){
          return nums[0];
      }
      int[] dp = new int[nums.length+1];
      dp[1] = nums[0];
      for(int i=2;i<=nums.length;i++){
      //递推关系式
          if(dp[i-2]+nums[i-1] > dp[i-1]){
              dp[i]=dp[i-2]+nums[i-1];
          }else{
              dp[i] = dp[i-1];
          }
      }
      return dp[nums.length];
  }
}

  • 环状

    输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
    解析:其实递推方程是一样的。我们可以用两个数组来记录两种情况。初始化不一样，得出两种情况。
    import java.util.*;
class Solution {
  public int rob(int[] nums) { 
      int m =nums.length;
      if(m == 0){
          return 0;
      }
      if(m == 1){
          return nums[0];
      }
      int[] dp0 = new int[m+1];//不偷第一间,dp[i]为偷第i间的能获取最大金额
      int[] dp1 = new int[m+1];//偷第一间
      dp0[1] = 0;
      dp0[2] = nums[1];
      dp1[1] = nums[0];
      dp1[2] = nums[0];
      for(int i = 2;i<=m;i++){
          dp0[i] = Math.max(dp0[i-1],dp0[i-2]+nums[i-1]);
          dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
      }
      return Math.max(dp0[m],dp1[m-1]);//偷了第一间之后，不能偷第m间，返回的是m-1间。
  }
}