题意理解

对于一个非负数组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]为例,示意图如下: alt

但是在求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[i1][0],dp[i1][1])dp[i][0] = max(dp[i-1][0],dp[i-1][1])
dp[i][1]=dp[i1][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。