题意理解

对于一个非负数组nums，我们从中选取若干个数，要求被选到的数不能相邻。问选到的数之和最大为多少。

方法一

动态规划
由于相邻的数字不能同时选，那么不确定的因素太多了，我们先要确定一个下来。使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的结果中肯定有某个数是最后一个被选到的数字，所以我们只要遍历一遍value，找到其最大值即可。

至于value[i]怎么求。我们假设已经知道之前每个位置上的value，value[i]则为nums[i]加上value[0]~value[i-2]之间的最大值，nums[i-1]是不能被选的。这样状态转移方程就很简单，且考虑了所有情况。

以[2,4,5,8,3]为例，示意图如下：

但是在求value[0]~value[i-2]之间的最大值时，如果再用一遍循环，会导致双重循环而超时。因此使用一个整型变量maxm记录之前value的最大值，进来一个新的value[i]直接更新即可。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        vector<int> value;
        //对于第i个房子，我们至少可以偷他一家
        for (int i=0;i<nums.size();i++)
        {
            value.push_back(nums[i]);
        }
        int ans = max(value[0],value[1]);
        //用一个maxm记录value[i-1]之前的最大值。
        int maxm = value[0];
        for (int i=2;i<nums.size();i++)
        {
            //更新maxm的值
            if ((i-2)>0) maxm = max(maxm, value[i-2]);
            value[i] += maxm;
            ans = max(ans, value[i]);
        }
        return ans;
    }
};

时间复杂度：$O(N)O(N)$。只对nums和value数组进行了一次遍历，长度均为N。
空间复杂度：$O(N)O(N)$。开辟了新数组value，长度和nums一样都为N。

方法二

动态规划
这次换一种思路。既然每个数字有2种情况，选或者不选，那么就使用一个二维数组dp，其行数为nums的大小，有2列（0表示不选，1表示选）。状态转移方程为：

$dp[i][0]=max(dp[i-1][0],dp[i-1][1])dp[i][0]\; =\; max(dp[i-1][0],dp[i-1][1])$
$dp[i][1]=dp[i-1][0]+nums[i]dp[i][1]\; =\; dp[i-1][0]\; +\; nums[i]$

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        vector<vector<int>> dp = vector<vector<int>>(nums.size(),vector<int>(2,0));
        dp[0][1] = nums[0];
        for (int i=1;i<nums.size();i++)
        {
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        //返回时在要在是否选择最后一个数中判断一下
        return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);
    }
};

时间复杂度：$O(N)O(N)$。只对nums数组进行了一次遍历，长度为N。
空间复杂度：$O(N)O(N)$。开辟了新的二维数组dp，列数是固定值为2。