解题思路
两种思想，动态规划和记忆化搜索
1.动态规划
动态规划，定义一个数组memo[n+1], 其中memo[0]表示一个店也没有，固定值为0；memo[1]表示洗劫到了第一个店，是固定值，毕竟就一个店，有多少拿多少。注意这里的定义，表示洗劫到了第几个店，当然这个店洗不洗，不一定，至少到这个店了。
假如到了第n个店，会有两种情况：
a. 洗劫：那么就要求第n-1个不能洗，于是洗劫值为当前店nums[n] 和 前n-2个店的最大值之和;
b. 不洗劫，那么就是说我要求前n-1个店洗劫最大值，毕竟不洗劫第n个，那么说明第n-1个是允许被洗劫的。 这两种情况求最大的一个就是memo[n] 的值。
举一个具体的例子：比如说n = 2; 那么有两种情况：
a. 洗劫第二个店，那么就要求n-1个也就是第一个不能洗劫，于是就是求前n-2个最大值再加上第二个店的值：也就是memo[0] +nums[2]
b. 不洗劫第二个店：那么第一个是可以洗劫的，也可以不洗，所以我们可以求前n-1个的最大值
2. 记忆化搜索
动态规划是自下而上计算，那么记忆化搜索就是自上而下去计算，我们考虑到了第n个店，洗劫还是不洗劫两种情况：若洗，就要用nums[n] 加上前n-2个最大值; 要是不洗，那么就求前n-1个最大值即可。本质和动态规划一样，就是一个自上而下(记忆化搜索)，一个自下而上(动态规划)
代码
// 记忆化搜索 class Solution { private: vector<int> memo; int fun(vector<int>& nums, int n) { if (n == 0) return 0; if (n == 1) return nums[0]; if (memo[n] == -1) { memo[n] = max(fun(nums, n-1), nums[n-1] + fun(nums, n-2)); } return memo[n]; } public: int rob(vector<int>& nums) { memo = vector<int>(nums.size()+1, -1); return fun(nums, nums.size()); } }; // 动态规划 class Solution { private: vector<int> memo; int fun(vector<int>& nums) { memo[0] = 0; // 表示没有店铺 memo[1] = nums[0]; // 第一个店 for (int i = 2; i <= nums.size(); i++) { int a = memo[i-1]; int b = memo[i-2] + nums[i-1]; // 注意，这里的nums[i-1] 表示第i个店铺，毕竟nums的下标从0开始 memo[i] = a > b ? a : b; } return memo[nums.size()]; } public: int rob(vector<int>& nums) { memo = vector<int>(nums.size()+1); return fun(nums); } };
