力扣原題鏈接，點擊跳轉。

有一個小偷，要偷東西。假設有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]);}
};