平板板打家劫舍
转化子问题：
按顺序偷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]); } };
