293-打家劫舍(解决与拓展)

浅浅的花香味﹌ 2023-01-16 06:51 50阅读 0赞

## 打家劫舍 ##

## 题目如下 ##

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。  
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

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

**示例 2**：  
输入：\[2,7,9,3,1\]  
输出：12  
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  
偷窃到的最高金额 = 2 + 9 + 1 = 12 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 解题思路 ##

我们设dp(i)，从0，1,2, ,i,i+1,i+2,i+3, ,n-1;  
**dp(i)的i代表偷到第i家的时候，dp(i)代表从第0到第i家偷累计的最大金额值**  
我们假定0下标不放数据，从1开始放数据。i就是问题的规模。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
**i=0时，没一家可以偷。i=1,只有1家，把1号数据给你。**  
![在这里插入图片描述][20210424192623995.png_pic_center]

**当i=2，在这两家找出金额最大的那家给你偷。**  
![在这里插入图片描述][20210424192651823.png_pic_center]

**当i>2的时候，**  
![在这里插入图片描述][20210424192733649.png_pic_center]

## 解题代码 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int rob(const vector<int>& nums)
    {
        
    	if (nums.empty()) return 0;
    	vector<int> dp(nums.size());
    	if (nums.size() == 1)
    	{
        
    		return nums[0];
    	}
    	if (nums.size() == 2)
    	{
        
    		return std::max(nums[0], nums[1]);
    	}
    	dp[0] = nums[0];
    	dp[1] = std::max(nums[0], nums[1]);
    	int len = nums.size();
    	for (int i = 2; i < len; ++i)
    	{
        
    		dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
    	}
    	return dp[len - 1];
    }
    
    int main()
    {
        
    	vector<int>ar = {
         2,7,9,3,1 };
    	cout << rob(ar) << endl;
    	return 0;
    }

## 运行程序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

## 不用数组vector的形式的写法 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int rob(const vector<int>& nums)
    {
        
    	if (nums.empty()) return 0;
    	if (nums.size() == 1)
    	{
        
    		return nums[0];
    	}
    	int pre = 0;         //dp[i-2];
    	int cur = nums[0];	 //dp[i-1];
    	int len = nums.size();//长度
    	for (int i = 1; i < len; ++i)
    	{
        
    		int tmp = std::max(cur, pre + nums[i]);//临时量
    		pre = cur;
    		cur = tmp;
    	}
    	return cur;
    }
    
    int main()
    {
        
    	vector<int> ar = {
         2,7,9,3,1 };
    	cout << rob(ar) << endl;
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

## 拓展：找出有哪一家被小偷光顾过 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int rob(const vector<int>& nums, vector<bool>& X)
    {
        
    	if (nums.empty()) return 0;
    	vector<int> dp(nums.size());
    	if (nums.size() == 1)
    	{
        
    		X[0] = 1;
    		return nums[0];
    	}
    	if (nums.size() == 2)
    	{
        
    		if (nums[0] > nums[1])
    		{
        
    			X[0] = 1;
    			return nums[0];
    		}
    		else
    		{
        
    			X[1] = 1;
    			return nums[1];
    		}
    	}
    	dp[0] = nums[0];
    	if (nums[0] > nums[1])
    	{
        
    		X[1] = 1;
    		dp[1] = nums[0];
    	}
    	else
    	{
        
    		X[1] = 1;
    		dp[1] = nums[1];
    	}
    	int len = nums.size();
    	for (int i = 2; i < len; ++i)
    	{
        
    		dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
    	}
    	return dp[len - 1];
    }
    
    int main()
    {
        
    	vector<int> ar = {
         2,7,9,3,1 };
    	vector<bool> X(ar.size());
    	cout << rob(ar, X) << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/12effc1ec6a84e968a593cc96adda2ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/121479e9339f4bc6a74b64731f35c5cc.png
[20210424192623995.png_pic_center]: /images/20221022/282fdb5ac5624936be33d397d3358286.png
[20210424192651823.png_pic_center]: /images/20221022/869d4935fbb44c41ac33b51b9ba82a6a.png
[20210424192733649.png_pic_center]: /images/20221022/ae1bd6f3947f4a228614df1d75d86b3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/50082f8ee1654acb83b1756363529b7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/ac1869b75f8241cf90987eb3efab505c.png