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.
一个不太清晰的答案:

#define max(a,b) (((a) > (b)) ? (a):(b))
int rob(int* nums, int numsSize) 
{
    if(0 == numsSize)
        return 0;
    
    if(1 == numsSize)
        return nums[0];
    
    int a = 0;
    int b = 0;
    
    for(int i = 0 ;i < numsSize;i++)
    {
        if(i%2==0)
        {
            a = max(b,a+nums[i]);
        }
        else
        {
            b = max(a,b+nums[i]);
        }
    }
    
    return max(a,b);
    
    
}

思路非常清晰的答案:

#define max(a,b) (((a) > (b)) ? (a):(b))
int rob(int* nums, int numsSize) 
{
    if(0 == numsSize)
        return 0;
    
    if(1 == numsSize)
        return nums[0];
    nums[1] = max(nums[0],nums[1]);
    
    for(int i = 2;i < numsSize;i++)
    {
        nums[i] = max(nums[i - 1],nums[i-2] + nums[i]);
    }
    
    return nums[numsSize - 1];
    
}

上面的方法修改了数组的值,因此下面的解法可能更加实用:

#define max(a,b) (((a) > (b)) ? (a):(b))
int rob(int* nums, int numsSize) 
{
    int prev1 = 0;
    int prev2 = 0;
    int curr = 0;
    
    for(int i = 0;i < numsSize;i++)
    {
        curr = max(nums[i] + prev2,prev1);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return curr;
}

2021.02.17更新
时隔两年再次做这道题,发现上来就理解错了:

class Solution {
public:
    int rob(vector<int>& nums) {
        int sum_even = 0;
        int sum_odd = 0;
        for(int i = 0;i < nums.size();i+=2)
        {
            sum_even += nums[i];
        }

        for(int i = 1;i < nums.size();i+=2)
        {
            sum_odd += nums[i];
        }

        return max(sum_even,sum_odd);
    }
};

错误的以为,要么从第一个开始加,要么从第二个开始加,但是随便一个例子:[2,1,1,2],这个例子中最大值是第一个加最后一个元素,最大金额是4.因此需要分析更通用的解法。
首先我们看下上面C解法中的:

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 0) return 0;
        if(nums.size() == 1) return nums[0];

        nums[1] = max(nums[0],nums[1]);
        
        for(int i = 2;i < nums.size();i++)
            nums[i] = max(nums[i-1],nums[i-2] + nums[i]);
        
        return nums[nums.size() - 1];
    }
};

是不是有点动态规划的意思?尝试使用动态规划,代码如下:

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        
        //dp solution
        vector<int> dp(size,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2;i < size;i++)
        {
            dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
        }
        
        return dp[size - 1];
    }
};

进一步可以优化空间复杂度为O(1),AC code如下:

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        
        //dp solution
        int dp_0 = nums[0];
        int dp_1 = max(nums[0],nums[1]);
        
        for(int i = 2;i < size;i++)
        {
            int temp = dp_1;
            dp_1 = max(dp_1,dp_0 + nums[i]);
            dp_0 = temp;
        }
        
        return dp_1;
    }
};

labuladong公众号解法分析

经典动态规划-打家劫舍问题
首先我们按照抢或者不抢的思路,自顶向下动态规划实现代码:

class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums,0);
    }
private:
    int dp(vector<int>& nums,int start){
        if(start >= nums.size())
            return 0;
        
        int res = max(
            //不抢当前家
            dp(nums,start+1),
            //抢当前家
            dp(nums,start+2) + nums[start]
        );
        
        return res;
    }
};

运行出现超时:

Time Limit Exceeded
[114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240]

原因是重复计算了子问题,类似于费波那奇数列计算,这里我们可以使用一个缓存机制。

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> mem(nums.size(),-1);
        return dp(nums,mem,0);
    }
private:
    int dp(vector<int>& nums,vector<int>& mem,int start){
        if(start >= nums.size())
            return 0;
        
        if(mem[start] != -1)
            return mem[start];
    
        int res = max(
            //不抢当前家
            dp(nums,mem,start+1),
            //抢当前家
            dp(nums,mem,start+2) + nums[start]
        );
        //记忆化
        mem[start] = res;
        return res;
    }
};