题目

题目

思路 - 动态规划

• 只有一间房间，偷窃该房屋

• 只有两间房间，偷窃其中金额较高的房屋

• 大于两间，对于第k间房屋，有两个选项：

  1. 偷窃第k间房屋，那么就不能偷窃第k - 1间房屋，偷窃总金额为前k - 2间房屋的最高总金额与第k间房屋的金额之和
  2. 不能偷窃第k间房屋，偷窃总金额为前k - 1间房屋的最高总金额

  在这两个选项中偷窃总金额较大的选项，即为前k间房屋能偷窃的最高总金额
  

  状态转移方程：
  状态转移方程
  
  边界条件：
  边界条件

实现

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