一个专业的小偷,计划偷窃一个环形街道上沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums
,请计算 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [0]
输出:0
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int[] onDp = new int[nums.length];
int[] offDp = new int[nums.length];
Arrays.fill(onDp, -1);
Arrays.fill(offDp, -1);
onDp[0] = nums[0];
offDp[0] = 0;
int onMAx = getMax(onDp, nums.length - 2, nums);
int offMAx = getMax(offDp, nums.length - 1, nums);
return Math.max(onMAx, offMAx);
}
private int getMax(int[] dp, int index, int[] nums) {
if (dp[index] >= 0) {
return dp[index];
}
if (index == 1) {
dp[index] = Math.max(dp[0], nums[1]);
return dp[index];
}
if (index == 2) {
if (nums.length == 3) {
return Math.max(nums[0], Math.max(nums[1], nums[2]));
} else {
dp[index] = Math.max(dp[0] + nums[2], nums[1]);
}
return dp[index];
}
int pre = getMax(dp, index - 1, nums);
int prePre = getMax(dp, index - 2, nums);
int result = Math.max(pre, prePre + nums[index]);
dp[index] = result;
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)