[198. 打家劫舍]
描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
题目标签：数组，动态规划（DP）
这道题属于DP（动态规划）题目中比较入门的题目了
首先从单个房间考虑：
假设是ABC三个房间
考虑A房间：
- 1:被偷
那么在A的左边和右边必不可能被偷 - 2:不被偷
那么在A的左边和右边可能会被偷也有可能不被偷(反正就是对于房间A来说 A自己不被偷就完事了)
从上面可以看出当前房间有且只有被偷与不被偷这两个状态
那么定义一个DP数组 长度与nums（房间数）相同
定义：DP[X]
X为当前的房间号
DP[X] 表示 假设有x个连续的房间，小偷能偷到的最大金额
状态转移方程：
DP[X] = MAX(DP[X-2]+nums[X],DP[X-1]) X>2
DP[X] =nums[X] X==1;
DP[X] = MAX(nums[X-1],nums[X-2]) X==2;
用例解释：
nums= [2,7,9,3,1]
dp = [0,0,0,0,0]
最后的答案就在dp数组的最后一个位置上
（心细的人就发现了，其实DP数组每次起到作用的就是前一个房间以及前两个房间的值，这样可以对dp数组进行空间上的优化 将空间复杂度降到O（1））
代码块（优化前）
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
vector<int> dp (nums.size(),0);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2 ; i < nums.size() ; i++)
{
dp[i] = max(nums[i] + dp[i-2],dp[i-1]);
}
return dp[nums.size()-1];
}
};
时间复杂度O（n），空间复杂度O(n)
代码块（优化后）
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
vector<int> dp (nums.size(),0);
int a = nums[0];
int b = max(nums[0],nums[1]);
int temp = 0;
for(int i = 2 ; i < nums.size() ; i++)
{
temp = b;
b = max(nums[i] + a,b);
a = temp;
}
return b;
}
};
时间复杂度O（n），空间复杂度O(1)
[213. 打家劫舍 2]
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
会做上面那道题的话，这道题其实本质也跟上面差不多，唯独不一样的地方就是房间数组变成了一个循环数组，仔细思考其实可以发现，这道题影响最大的就是第一个房间和最后一个房间，因为：如果偷了第一个房间那么最后一个房间是不能偷的，如果要偷最后一个房间，那么第一个房间是不可偷的，其实就可以将这道题化解成：
- 1.小偷偷第一个房间的东西，且不偷最后一个房间的东西获得的总价值X1
- 2.小偷不偷第个房间的东西，且偷最后一个房间的东西获得的总价值X2
（这道题有个逻辑上的bug就是只有两家的时候选大的那个偷，这个可以忽略掉）
最后的答案就是MAX（X1，X2）就可以得出结果了
说白了就是分别记录两个dp数组dp1，dp2，然后分别求出答案，然后取一个最大值就好了，区别就在于对数组进行初始化的时候有些许的变化
可以分成两部来做
- 1.小偷偷第一家：dp1[0] = nums[0],dp1[1] =dp1[0] (因为默认偷第一家，那么第二家就必定是不可偷的)
- 2.小偷不偷第一家：dp2[0] = 0,dp2[1] = nums[1] (因为默认不偷第一家，那么第二家就必定是可偷的)
可能有人问了 为什么第二家肯定要偷呢
注意dp数组的定义：dp[x] = 假设有x个连续的房间，小偷能偷到的最大金额。所以： 当x==2时，dp[1] 可以翻译成：假设有2个连续的房间，且小偷不偷第一家，小偷能偷到的最大金额。
代码块
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
vector<int> dp1 (nums.size(),0);
vector<int> dp2 (nums.size(),0);
//抢第一家
dp1[0] = nums[0];
dp1[1] = dp1[0];
for(int i = 2 ; i < nums.size()-1 ; i++)
{
dp1[i] = max(nums[i] + dp1[i-2],dp1[i-1]);
}
//不抢第一家
dp2[0] = 0;
dp2[1] = nums[1] ;
for(int i = 2 ; i < nums.size(); i++)
{
dp2[i] = max(nums[i] + dp2[i-2],dp2[i-1]);
}
return max(dp1[nums.size()-2],dp2[nums.size()-1]);
}
};
时间复杂度O（n），空间复杂度O(n)
