原题链接
比子母题House Robber多了一个条件：偷了0以后，第n-1间房子不能偷。
转换思路为求偷盗【0，n-1）之间，以及【1，n）之间的最大值。
用两个DP，分别保存偷不偷第0间房的情况。
Runtime: 0 ms, faster than 100.00%
class Solution { public: int rob(vector<int> &nums) { int res = 0; int len = nums.size(); if (len <= 0) return res; if (len == 1) return nums[0]; if (len == 2) return (nums[0] > nums[1] ? nums[0] : nums[1]); int dp1[len]; int dp2[len]; // rob 0 dp1[0] = nums[0]; dp1[1] = max(nums[1], dp1[0]); for (int i = 2; i < len - 1; i++) { dp1[i] = max(dp1[i - 2] + nums[i], dp1[i - 1]); } //rob 1 dp2[0] = 0; dp2[1] = nums[1]; dp2[2] = max(nums[2], dp2[1]); for (int i = 3; i < len; i++) { dp2[i] = max(dp2[i - 2] + nums[i], dp2[i - 1]); } return max(dp1[len - 2], dp2[len - 1]); } };
转载于:https://www.cnblogs.com/ruoh3kou/p/9914028.html
相关资源：数据结构—成绩单生成器