LeetCode动态规划—打家劫舍从平板板到转圈圈（198、213）

平板板打家劫舍

转化子问题：

按顺序偷n间房子，就是考虑偷前n-1间房子还是偷前n-2间房子再偷第n间房子。

列出公式：

res[n] = max{ res[n-1] , 数组中最后一个数据+res[n-2] } （res是前k个房子中偷盗最多的钱的数组）

所以对于第n个数组数据依赖于前n-1和n-2的数据。可以得出dp数组从左到右计算。

同时对于动态规划问题，写dp数组时，要主动的定义好开头。

res[0] = 0

res[1] = nums[0]

同时注意可以增加边界条件，减少花费时间。当只有一家时偷这家结束，或者当只有两家时偷钱最多的一家结束。

class Solution {
public:
    int rob(vector<int>& nums) {
        int length = nums.size();
        if(length == 1)
            return nums[0];
        vector<int> res(length+1,0);
        res[0] = 0;
        res[1] = nums[0];
        for(int i = 2;i <= length;i++)
        {
            res[i] = max(res[i-1],nums[i-1]+res[i-2]);
        }
        return res[length];
    }
};

转圈圈打家劫舍（进阶版）

现在这个小区里面是环形的，就是将首尾变成相邻问题。

那就是偷到最后一家时还要考虑是否前面偷了第一家。但是对于动态规划的dp数组，无法记录是否偷了第一家。

那就考虑将问题分解成两个子问题。

对于第一家和最后一家，将选择一家偷。就分解成偷前n-1家或者第2到第n家的平板板打家劫舍中选最高的结果偷。

列出公式

max{ 忽略第n家，res[n-1] ,忽略第1家，ans从第2家开始偷到第n家}

（res[n-1] = nums[:n-1] ans[n] = nums[1:])

降低空间占用，可以考虑用同一个dp数组，计算完将res[length-1]保存下来，更新res数组。

class Solution {
public:
    int rob(vector<int>& nums) {
        int length = nums.size();
        if(length == 1)
            return nums[0];
        vector<int> res(length+1,0);
        vector<int> ans(length+1,0);
        res[1] = nums[0];
        for(int i = 2;i < length;i++)
        {
            res[i] = max(res[i-1],nums[i-1]+res[i-2]);
            ans[i] = max(ans[i-1],nums[i-1]+ans[i-2]);
        }
        ans[length] = max(ans[length-1],nums[length-1]+ans[length-2]);
        return max(res[length-1],ans[length]);
    }
};