题目：题目链接

思路：看他的related topics。然后动态规划做。
这一看就是一维的，为什么因为二维的我不会，你也就看不到这篇题解了。嘿嘿
咱们令dp[i]表示前i个房子能偷的最大值。那么此时有两种情况：要么选第i个房子，那i-1就不能选，只能加上dp[i-2]。要么不选第i个房子，那么就可以是dp[i-1]。因为数组都大于0，所以肯定不存在选择dp[i-3]的情况，然后跳过第i-1个房子的情况。所以就是这两种情况，取最大值就可以了。
可以得到状态转移方程：
d p [ i ] = m a x ( d p [ i − 2 ] + n u m s [ i ] + d p [ i − 1 ] ) dp[i] = max(dp[i-2]+nums[i] + dp[i-1]) dp[i]=max(dp[i−2]+nums[i]+dp[i−1])
边界情况： d p [ 0 ] = 0 dp[0]=0 dp[0]=0 ， d p [ 1 ] = n u m s [ 0 ] dp[1]=nums[0] dp[1]=nums[0]
注意dp[i]是指第i个房子，从1开始的。(日常计数法)
而nums[i]是从0开始的(计算机计数法)
所以dp[i]对应的实际是前nums[i-1]个房子所拥有的最大值。
上代码：

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

空间复杂度是O(n),那咱们再和斐波那契数列数列一样优化一下：

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

这样时间复杂度是O(n),空间就是O(1)了。完美。

加油加油！！！