leetcode-house-robber-ii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/house-robber-ii/

　　一个强盗可以对一条环上每户人家进行抢劫，每家可以获得不同数量的钱财，但是要求相邻的两家不能同时抢劫，问强盗最多可以抢到多少钱财

题目分析

　　这个题是house robber的变形，之前house robber的解题思路是这样的：

　　跟背包问题思路有点像，用m数组表示处理完第i家以后获得的最大价值，v代表每家的价值。当强盗走到第i家门前时，他的选择是抢或者不抢。如果抢劫的话，那么他能获得的价值是m[i - 2] + v[i]，即便第i-1家已经抢过，也可以重置一下，不抢第i-1家，抢第i家。如果不抢的话，那么就是m[i-1]，转移方程为：

m[i] = max{m[i-1],m[i-2]+v[i]}

　满足动态规划的条件：最优子结构性质，m[i]是最优方案，那么m[j] (任意 j<i) 也一定是最优方案

　　成环以后要求不变，抢劫的不能相邻，要把环的问题化成直线，把第0户人家和第n-1户人家拆开，因为最后的方案中一定是不能同时选择第0户和第n-1户，因此最后的最优方案一定在抢劫0~(n-2)户，和抢劫1~(n-1)户的最优解中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rob(vector<int>& nums) {
        int s = nums.size();
        if(s == 0) return 0;//注意边界处理
        if(s == 1) return nums[0];//注意边界处理
        if(s == 2) return (nums[0] > nums[1]) ? nums[0] : nums[1];//注意边界处理
        int v1 = robRange(nums, 1, s - 1);
        int v2 = robRange(nums, 0, s - 2);
        return (v1 > v2) ? v1 : v2;
    }
private:
    int robRange(vector<int>& num, int l, int r) {
        int prepre = 0, pre = 0;
        for(int i = l; i <= r; i++) {
            int maxv = std::max(prepre + num[i], pre);
            prepre = pre;
            pre = maxv;
        }
        return pre;
    }
};

　　这里的解法仅仅是求出了最优值，没有对中间的具体抢劫方案进行记录，时间复杂度O(n)，额外空间复杂度是O(1)