一、题目
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,能够偷窃到的最高金额。
二、思路
该题是一个典型的动态规划问题,屋子有n个(0~n-1),先不考虑第一个房屋和最后一个房屋紧挨着的问题,将偷窃n个房屋的问题划分为子问题,可以直观地想到:
1)到第i个房屋时,如果不进行偷窃,那就是0~i-1个房屋最大能偷窃多少
2)到第i个房屋时,如果进行偷窃,那就是0~i-2个房屋最大能偷窃多少,再加上第i个房屋的金额
可以写入状态转移方程:
再考虑到第一个房屋和最后一个房屋紧挨着的问题,该问题可切分为:拿第一个房屋(0~n-2)、拿最后一个房屋(1~n-1)、两个都不拿(1~n-2)。其实两个都不拿已经包含再前两种情况中了,那就可以切分为:拿第一个不拿最后一个(0~n-2)、不拿第一个拿最后一个(1~n-1)。做两次动态规划,即可获得结果。
三、代码
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) { // 先判断nums的长度,length等于1、2时候独立处理
return nums[0];
} else if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
// 两次dp的最大值
return Math.max(dpFunction(1, nums.length - 1, nums), dpFunction(0, nums.length - 2, nums));
}
public int dpFunction(int start, int end, int[] nums) {
int first = nums[start];
int second = Math.max(first, nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int t = Math.max(second, first + nums[i]); // 求取i处的最大值
first = second;
second = t;
}
return second;
}
}