题目描述

这是一场有预谋的盗窃活动。现在一条路上有一排房间，每个房间都有一些钱。盗窃不能同时出现在两个相邻的房间，否则会触发警报。

现在给定这些房间的钱的数量，问在不触动警报的情况下最多能拿到多少钱。

样例

Example 1:

Input: [1,2,3,1]
Output: 4
解释: 盗窃房间 1 (钱数 = 1) 然后盗窃房间 3 (钱数 = 3).
             盗窃的钱数总和 = 1 + 3 = 4.


Example 2:

Input: [2,7,9,3,1]
Output: 12
解释: 盗窃房间 1 (钱数 = 2), 盗窃房间 3 (钱数 = 9) 然后盗窃房间 5 (钱数 = 1).
             盗窃的钱数总和 = 2 + 9 + 1 = 12.

C++ 代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n+1),g(n+1);
        for(int i=1;i<=n;i++)
        {
            f[i]=max(f[i-1],g[i-1]);
            g[i]=f[i-1]+nums[i-1];
        }
        return max(f[n],g[n]);
    }
};