House Robber--LeetCode

本是古典何须时尚 2022-08-07 13:52 15阅读 0赞

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and**it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight**without alerting the police**.

## 题目大意： ##

你是一名专业强盗，计划沿着一条街打家劫舍。每间房屋都储存有一定数量的金钱，唯一能阻止你打劫的约束条件就是：由于房屋之间有安全系统相连，如果同一个晚上有两间相邻的房屋被闯入，它们就会自动联络警察，因此不可以打劫相邻的房屋。

给定一列非负整数，代表每间房屋的金钱数，计算出在不惊动警察的前提下一晚上最多可以打劫到的金钱数。

## 解题思路： ##

动态规划（Dynamic Programming）

状态转移方程：

dp\[i\] = max(dp\[i - 1\], dp\[i - 2\] + num\[i - 1\])

其中，dp\[i\]表示打劫到第i间房屋时累计取得的金钱最大值。

时间复杂度O(n)，空间复杂度O(n)

另外一个解题思路：对于当前这一家，我可以选择要还是选择不要，对于选择不要的，那么就看前面要和不要的最大值，选择要，只能选择前面一家不要然后加上当前的值

int rob(vector<int> &num) {
        vector<vevtor<int> > rob(2);
        rob[0].assign(num.size(),0); //代表不要当前的 
        rob[1].assign(num.size(),0); //代表要当前的 
        rob[1][0]=num[0];
        int sum =0;
        for(int i=1;i<num.size();i++)
        {
            rob[0][i] = max(rob[0][i-1],rob[1][i-1]);
            rob[1][i] = rob[0][i-1]+num[i];    
        }
        sum = max(rob[0][num.size()-1],rob[1][num.size()-1]); 
        return sum;        
    }

PS:像这种题目，使用到了动态规划的思想，在具体的实现中使用的数组来记录，但是最终的结果是使用一个值，那么就可以使用两个临时变量来代替。