LeetCode刷题（28）～打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

  

 

  
1
  
2
  
3
  
4
 

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

  

 

  
1
  
2
  
3
  
4
 

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

解答 By 海轰

提交代码（动态规划）

 int rob(vector<int>& nums) { int len=nums.size(); unordered_map<int,int> a; if(len==0) return 0; else if(len==1) return nums[0]; else if(len==2) return max(nums[0],nums[1]); else { int result; a[0]=nums[0]; a[1]=max(nums[0],nums[1]); for(int i=2;i<len;++i) { a[i]=max(nums[i]+a[i-2],a[i-1]); } } return a[len-1]; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

运行结果

思路
        在第n号房屋时，小偷获取的最大值是n号屋+前n-2获取最大值 与 前n-1号屋获取最大值 的较大值。

提交代码（动态规划+滚动数组）

int rob(vector<int>& nums) { int len=nums.size(); if(len==0) return 0; if(len==1) return nums[0]; int p=nums[0]; int q=max(nums[0],nums[1]); for(int i=2;i<len;++i) { int temp=q; q=max(p+nums[i],q); p=temp; } return q; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

运行结果

C++测试代码

#include <iostream>
#include<vector>
#include<unordered_map>
using namespace std;
// 方法一：动态规划
 int rob_1(vector<int>& nums) { int len=nums.size(); unordered_map<int,int> a; if(len==0) return 0; else if(len==1) return nums[0]; else if(len==2) return max(nums[0],nums[1]); else { int result; a[0]=nums[0]; a[1]=max(nums[0],nums[1]); for(int i=2;i<len;++i) { a[i]=max(nums[i]+a[i-2],a[i-1]); } } return a[len-1]; }
// 方法二：动态规划+滚动数组
int rob_2(vector<int>& nums) { int len=nums.size(); if(len==0) return 0; if(len==1) return nums[0]; int p=nums[0]; int q=max(nums[0],nums[1]); for(int i=2;i<len;++i) { int temp=q; q=max(p+nums[i],q); p=temp; } return q; }
int main()
{ vector<int> a; a.push_back(2); a.push_back(7); a.push_back(9); a.push_back(3); a.push_back(1); cout<<rob_2(a)<<endl; return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

题目来源

链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnq4km/
来源：力扣（LeetCode）

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107880677