【Leetcode】198. House Robber（DP）（2019年拼多多春招实习题参考）（经典抢劫问题）

柔光的暖阳◎ 2022-01-31 03:55 162阅读 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**.

**Example 1:**

Input: [1,2,3,1]
    Output: 4
    Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
                 Total amount you can rob = 1 + 3 = 4.

**Example 2:**

Input: [2,7,9,3,1]
    Output: 12
    Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
                 Total amount you can rob = 2 + 9 + 1 = 12.

题目大意：

很经典的题目了，抢劫问题。

给出一个数组，表示可以获得的金钱数，唯一限制就是我们不可以同时获得相邻两个部分的金钱，求解我们可以获得的最大金钱数。

解题思路：

看见这种只给个数组的就知道需要DP的思想，最怕你上去就用搜索。

从前向后遍历时，我们发现当前位置是不会偷取它的前一个位置，前两个和前三个位置是我们参考的对象，那如果再往前呢？

我们会发现此时忽略了前第二个位置，导致数据更小。

所以我们DP的规则为

tmp\[i\] += max(tmp\[i-2\], tmp\[i-3\]);

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70][]

如果向前遍历三个节点的话就会产生不必要的计算，如上图所示。

class Solution {
    public:
        int rob(vector<int>& nums) {
            vector<int> tmp(nums.begin(), nums.end());
            if(nums.size()==0) return 0;
            if(nums.size()==1) return nums[0];
            int ans = max(nums[0], nums[1]);
            for(int i=2; i<nums.size(); i++){
                if(i==2){
                    tmp[i] += tmp[i-2];
                }else{
                    tmp[i] += max(tmp[i-2], tmp[i-3]);
                }
                ans = max(ans, tmp[i]);
            }
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70]: /images/20220131/44eb4708edf34179b274428c30da04a3.png