特性

典型的动态规划问题
但是我们需要注意的是 这个题目和198有所不同的地方是这个题目首位是相连的
就是说第一个和最后一个不能同时选择
所以我们可以分成两种情况来进行讨论 第一种是不选最后一个的最大值 第二种是不选第一个的最大值然后取一个最大就行

求解

将问题分成两个小问题之后就非常简单了 就像力扣198一样解决
这个题目是典型的DP问题 需要解决的也是最大值的问题
所以我们每个状态存储的就是每个状态的最大值 一个变量i用来存储前i个物品当中选择
下面 你可要听好了
对于第n间房子 f[n]难道一定代表着n被偷了吗 其实并没有
当第n间房子被偷了的时候 n + 1间房子最大值就是f[n]
当第n间房子没有被偷的时候 n + 1间房子最大值应该是f[n - 1] + nums[n + 1];
所以我们的状态转移方程也就自然而然的出来了
就是 f[n] = max(f[n - 1], f[n - 2] + nums[n]);
所以我们的特判范围也就出来了 对于每一组的前两个我们需要进行特判 而在原题目当中
因为我们是要分成去头去尾两组来进行判断的 也就是我们需要进行特判l < 4的全部情况

class Solution {
public:
    int f[1010];
    int ans;
    int rob(vector<int>& nums) {u
        int l = nums.size();
        if(l == 1)
        {
            ans = nums[0];
        }
        else if(l == 2)
        {
            ans = max(nums[0], nums[1]);
        }
        else if(l == 3)
        {
            ans = max(nums[0], nums[1]);
            ans = max(ans, nums[2]);
        }
        else
        {

            f[0] = nums[0], f[1] = max(nums[0], nums[1]);
            for(int i = 2; i < l - 1; i ++ )
            {
                f[i] = max(f[i - 1], f[i - 2] + nums[i]);
            }
            ans = f[l - 2];
            memset(f, 0, sizeof f);
            f[1] = nums[1], f[2] = max(nums[1], nums[2]);
            for(int i = 3; i < l; i ++ )
            {
                f[i] = max(f[i - 1], f[i - 2] + nums[i]);
            }
            ans = max(ans, f[l - 1]);
        }
        return ans;
    }
};