题目链接：House Robber

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.

这道题的要求是一个强盗计划抢劫，要求不能连着抢劫两家，因为这样会触发报警器，惊动警察，计算最多能抢多少money。

典型的动态规划的题目，令dp[i]表示到第i家（抢劫或者不抢劫均可）的时候抢到money的最大值。由于不能连着抢劫2家，因此递推公式为：

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

即当前抢劫的最大值（dp[i]）为 到前一家时抢到的总money（dp[i-1]） 与 再前一家时（dp[i-2]）加上抢劫当前家抢到money（num[i]） 两者的最大值。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

同样，由于只用到了前一结果，因此可以用pre变量记录前一家的最大值，用cur记录当前最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution
{
public:
    int rob(vector<int> &num)
    {
        int pre = 0, cur = 0;
        for(int i = 0; i < num.size(); ++ i)
        {
            int temp = pre;
            pre = cur;
            cur = max(temp + num[i], pre);
        }
        return cur;
    }
};

还有一种其妙的做法，由于不能连着抢劫两家，也就是说，至少需要隔着1家进行抢抢劫，因此考虑区分奇偶数的情形：

  • 如果当前是偶数家，那么even = max(even+num[i], odd)；
  • 如果当前是奇数家，那么odd = max(odd+num[i], even)。

这样同为奇数或者偶数的就相当于隔了一家进行抢劫了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution
{
public:
    int rob(vector<int> &num)
    {
        int even = 0, odd = 0;
        for(int i = 0; i < num.size(); ++ i)
        {
            if((i & 1) == 0)
                even = max(even + num[i], odd);
            else
                odd = max(odd + num[i], even);
        }
        return max(even, odd);
    }
};