有一个小偷，要偷东西。假设有n个房间，每个房间都有现金，下标为i的房间内的现金数是nums[i]。不能同时偷相邻的2个房间，其中第一个房间和最后一个房间是相邻的。那么这个小偷最多能偷到多少现金呢？
由于小偷不能同时偷第一个房间和最后一个房间，可以根据是否偷第一个房间进行分类讨论。
- 如果偷了下标为0的房间，那么就不能偷下标为1和n-1的房间，下标为2到n-2的房间情况未知。
- 如果没有偷下标为0的房间，那么下标为1到n-1的房间情况未知。
对于未知情况的房间，可以用动态规划的思路来思考。此时相当于，可以同时偷第一个房间和最后一个房间，其余条件不变。先确定一个状态表示。我们用f[i]表示：偷到下标为i的房间时，且必须偷下标为i的房间，最多能偷到的现金总数。用g[i]表示：偷到下标为i的房间时，不能偷下标为i的房间，最多能偷到的现金总数。此时状态转移方程就呼之欲出了。
- 如果下标为i的房间必须偷，那么下标为i-1的房间就不能偷，即f[i]=g[i-1]+nums[i]。
- 如果下标为i的房间不能偷，那么下标为i-1的房间情况未知，即g[i]=max(f[i-1],g[i-1])。
接着解决一些细节问题。根据状态转移方程，f[i]和g[i]都依赖下标为i-1的位置，所以要初始化f[0]=nums[0]，g[0]=0，防止越界。填表时应从左往右同时填表，这样能保证填某个位置的值时，前面的值已经准备好了。最后应返回max(f[n-1],g[n-1])。
class Solution
{
public:
int rob(vector<int>& nums)
{
return max(nums[0] + rob(nums, 2, nums.size() - 2), rob(nums, 1, nums.size() - 1));
}
private:
int rob(vector<int>& nums, int left, int right)
{
if (left > right)
return 0;
// 创建dp表
vector<int> f(nums.size());
auto g = f;
// 初始化
f[left] = nums[left];
// 填表
for (int i = left + 1; i <= right; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[right], g[right]);
}
};