这道题的dp状态很容易想到dp[i][0] 表示在第i间房不偷东西的金额，dp[i][1]表示在第i建房偷东西的金额。那转换方程很容易就有了。
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = nums[i-1] + dp[i-1][0];
边界状态也很容易就可以想到：
dp[0][0] = 0;
dp[0][1] = 0;
因为这题是首尾相连的，所以一种情况是偷第一家，另一种情况是偷最后一家。
public int rob(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
if(nums.length == 2){
return Math.max(nums[0], nums[1]);
}
int[][] dp = new int[nums.length +1][2];
dp[0][0] = 0;
dp[0][1] = 0;
for(int i = 1 ; i < nums.length ; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = nums[i-1] + dp[i-1][0];
}
int a = Math.max(dp[nums.length - 1][0],dp[nums.length - 1][1]);
dp[1][0] = 0;
dp[1][1] = 0;
for(int i = 2 ; i < nums.length + 1; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = nums[i-1] + dp[i-1][0];
}
int b = Math.max(dp[nums.length][0],dp[nums.length][1]);
return Math.max(a, b);
}
image.png
