题目
题目
思路 - 动态规划
只有一间房间，偷窃该房屋
只有两间房间，偷窃其中金额较高的房屋
-
大于两间，对于第k间房屋，有两个选项：
- 偷窃第k间房屋，那么就不能偷窃第k - 1间房屋，偷窃总金额为前k - 2间房屋的最高总金额与第k间房屋的金额之和
- 不能偷窃第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];
}
}
