在上次打劫完一条街道之后, 窃贼又发现了一个新的可以打劫的地方, 但这次所有的房子围成了一个圈, 这就意味着第一间房子和最后一间房子是挨着的. 每个房子都存放着特定金额的钱. 你面临的唯一约束条件是: 相邻的房子装着相互联系的防盗系统, 且 当相邻的两个房子同一天被打劫时, 该系统会自动报警.
给定一个非负整数列表, 表示每个房子中存放的钱, 算一算, 如果今晚去打劫, 你最多可以得到多少钱 在不触动报警装置的情况下.
注意事项
这题是 House Robber 的扩展, 只不过是由直线变成了圈
样例
给出 nums = [3,6,4], 返回 6, 你不能打劫 3 和 4 所在的房间, 因为它们围成一个圈, 是相邻的.
思路: 动态规划, 从第 I 题可以得出递推关系式为 A[i] = max(A[i-1],A[i-2]+A[i]); 这里由于这题变成了一个圈, 所以头尾两个数不能同时取到, 所以把这个圈分成 [0,n-1] 和[1,n]两部分分别计算所能得到的最大值然后取较大值就可以了.
- class Solution {
- public:
- /**
- * @param nums: An array of non-negative integers.
- * @return: The maximum amount of money you can rob tonight
- */
- int houseRobber2(vector<int> &nums) {
- // write your code here
- int size = nums.size();
- if(size == 0) return 0;
- if(size == 1) return nums[0];
- vector<int> L(size,0);// 两个数组做动态规划
- vector<int> R(size,0);
- L[1] = nums[0];// 初始化
- R[1] = nums[1];
- for(int i=2;i<size;++i){// 递推公式, 注意 nums 中数的顺序先后
- L[i] = max(L[i-2]+nums[i-1],L[i-1]);
- R[i] = max(R[i-2]+nums[i], R[i-1]);
- }
- return max(L[size-1],R[size-1]);// 取较大值
- }
- };
来源: http://www.bubuko.com/infodetail-2563663.html