题目描述（简单难度）

一个数组，每个元素代表商店的存款，一个小偷晚上去偷商店，问最多能偷多少钱。有一个前提，不能偷相邻的商店，不然警报会响起。

思路分析

一道很典型的通过子问题去解决原问题的题目，所以可以通过递归以及动态规划解决。

如果我们需要求前家商店最多能偷多少钱，并且知道了前 n - 1 家店最多能偷的钱数，前 n - 2 家店最多能偷的钱数。

对于第 n 家店，我们只能选择偷或者不偷。

如果偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 2 家店最多能偷的钱数」加上「第 n 家店的钱数」。因为选择偷第家商店，第 n - 1 家商店就不可以偷了。

如果不偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 1 家店最多能偷的钱数」。

最终前 n 家商店最多能偷的钱数就是上边两种情况选择较大的值。

接下来就是递归出口或者说初始条件。

当，也就是只有一家店的时候，能偷的最大钱数就是当前店的钱数。

通过上边的分析，代码也就直接出来了。

然后就会意料之中的超时。

原因很简单，因为递归中会计算很多重复的解，解法方案的话我们就是把递归过程中的解存起来，第二次遇到的话直接返回即可。

有了上边的递归和之前的分析，其实动态规划也可以直接出来了。

用 dp[n] 数组表示前 n 天能够带来的最大收益。

dp[n] = Math.max(dp[n - 2] + nums[n - 1], dp[n - 1] )。

dp[0] = 0 以及 dp[1] = nums[0]。

接下来就是动态规划空间复杂度上的优化，比如，10题，，72题，等等都已经用过了。

原因就是我们更新 dp[i] 的时候，只需要以及 dp[i - 2] 的信息，再之前的信息就不需要了，所以我们不需要数组，只需要几个变量就可以了。

一道很典型的题，可以体会从递归 -> 递归加缓冲 -> 动态规划 -> 动态规划空间复杂度优化这一系列的过程，如果题目做的多了，最开始就可以直接想到最后的方法了。

添加好友一起进步~

如果觉得有帮助的话，可以点击给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情