213. 打家劫舍 II

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

假设数组( extit{nums})的长度为 nn。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 ([0, n-2])；如果不偷窃第一间房屋，则偷窃房屋的下标范围是([1, n-1])。

对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 (n) 间房屋中可以偷窃到的最高总金额。

假设偷窃房屋的下标范围是 ([ extit{start}, extit{end}])，用( extit{dp}[i])表示在下标范围([ extit{start},i])内可以偷窃到的最高总金额，那么就有如下的状态转移方程：

[ extit{dp}[i] = max( extit{dp}[i-2]+ extit{nums}[i], extit{dp}[i-1]) ]

边界条件为：

[egin{cases} extit{dp}[ extit{start}] = extit{nums}[ extit{start}] & 只有一间房屋，则偷窃该房屋 \ extit{dp}[ extit{start}+1] = max( extit{nums}[ extit{start}], extit{nums}[ extit{start}+1]) & 只有两间房屋，偷窃其中金额较高的房屋 end{cases} ]

计算得到 ( extit{dp}[ extit{end}])即为下标范围([ extit{start}, extit{end}])内可以偷窃到的最高总金额。

分别取(( extit{start}, extit{end})=(0,n-2))和(( extit{start}, extit{end})=(1,n-1))进行计算，取两个 ( extit{dp}[ extit{end}])中的最大值，即可得到最终结果。

class Solution {
public:
    static const int N=110;
    int f[N];
    
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0],nums[1]);
        return max(robRange(nums,0,n-2),robRange(nums,1,n-1));
    }
    
    int robRange(vector<int>& nums,int st,int ed) {
        f[st]=nums[st];
        f[st+1]=max(nums[st],nums[st+1]);
        for(int i=st+2;i<=ed;i++)
            f[i]=max(f[i-2]+nums[i],f[i-1]);
        
        return f[ed];
    }
};