leetcode-house-robber

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/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) 也一定是最优方案

代码

1
2
3
4
5
6
7
8
9
int robRange(vector<int>& num, int l, int r) { //抢劫范围是l~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)