我的书签
添加书签
移除书签题目描述（简单难度）
一个数组，每个元素代表商店的存款，一个小偷晚上去偷商店，问最多能偷多少钱。有一个前提，不能偷相邻的商店，不然警报会响起。
思路分析
一道很典型的通过子问题去解决原问题的题目，所以可以通过递归以及动态规划解决。
如果我们需要求前 n 家商店最多能偷多少钱，并且知道了前 n - 1 家店最多能偷的钱数，前 n - 2 家店最多能偷的钱数。
对于第 n 家店，我们只能选择偷或者不偷。
如果偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 2 家店最多能偷的钱数」加上「第 n 家店的钱数」。因为选择偷第 n 家商店，第 n - 1 家商店就不可以偷了。
如果不偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 1 家店最多能偷的钱数」。
最终前 n 家商店最多能偷的钱数就是上边两种情况选择较大的值。
接下来就是递归出口或者说初始条件。
当 n = 0，也就没有商店，那么能偷的最大钱数当然是 0 了。
当 n = 1，也就是只有一家店的时候，能偷的最大钱数就是当前店的钱数。
解法一 递归
通过上边的分析，代码也就直接出来了。 1. public int rob(int[] nums) { 2. return robHelpler(nums, nums.length); 3. } 4. 5. private int robHelpler(int[] nums, int n) { 6. if (n == 0) { 7. return 0; 8. } 9. if (n == 1) { 10. return nums[0]; 11. } 12. return Math.max(robHelpler(nums, n - 2) + nums[n - 1], robHelpler(nums, n - 1)); 13. }
然后就会意料之中的超时。
原因很简单，因为递归中会计算很多重复的解，解法方案的话我们就是把递归过程中的解存起来，第二次遇到的话直接返回即可。
1. public int rob(int[] nums) {
2. int[] map = new int[nums.length + 1];
3. Arrays.fill(map, -1);
4. return robHelpler(nums, nums.length, map);
5. }
6. 7. private int robHelpler(int[] nums, int n, int[] map) {
8. if (n == 0) {
9. return 0;
10. }
11. if (n == 1) {
12. return nums[0];
13. }
14. if (map[n] != -1) {
15. return map[n];
16. }
17. int res = Math.max(robHelpler(nums, n - 2, map) + nums[n - 1], robHelpler(nums, n - 1, map));
18. map[n] = res;
19. return res;
20. }
解法二 动态规划
有了上边的递归和之前的分析，其实动态规划也可以直接出来了。
用 dp[n] 数组表示前 n 天能够带来的最大收益。
dp[n] = Math.max(dp[n - 2] + nums[n - 1], dp[n - 1] )。
初始条件的话，
dp[0] = 0 以及 dp[1] = nums[0]。
1. public int rob(int[] nums) {
2. int n = nums.length;
3. if (n == 0) {
4. return 0;
5. }
6. if (n == 1) {
7. return nums[0];
8. }
9. 10. int[] dp = new int[n + 1];
11. dp[0] = 0;
12. dp[1] = nums[0];
13. for (int i = 2; i <= n; i++) {
14. dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
15. }
16. return dp[n];
17. }
接下来就是动态规划空间复杂度上的优化，比如 5题，10题，53题，72题 ，115 题 等等都已经用过了。
原因就是我们更新 dp[i] 的时候，只需要 dp[i - 1] 以及 dp[i - 2] 的信息，再之前的信息就不需要了，所以我们不需要数组，只需要几个变量就可以了。
1. public int rob(int[] nums) {
2. int n = nums.length;
3. if (n == 0) {
4. return 0;
5. }
6. if (n == 1) {
7. return nums[0];
8. }
9. 10. int pre = 0; //代替上边代码中的 dp[i - 2]
11. int cur = nums[0]; //代替上边代码中的 dp[i - 1] 和 dp[i]
12. for (int i = 2; i <= n; i++) {
13. int temp = cur;
14. cur = Math.max(pre + nums[i - 1], cur);
15. pre = temp;
16. }
17. return cur;
18. }
总
一道很典型的题，可以体会从递归 -> 递归加缓冲 -> 动态规划 -> 动态规划空间复杂度优化这一系列的过程，如果题目做的多了，最开始就可以直接想到最后的方法了。
添加好友一起进步~
如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^
如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情
