首页 > 编程语言 >C++动态规划经典试题解析之打家劫舍系列

C++动态规划经典试题解析之打家劫舍系列

时间:2023-08-06 17:01:36浏览次数:40  
标签:试题 idx int res 房间 C++ 问题 打家劫舍 dp

1.前言

力扣上有几道与打家劫舍相关的题目,算是学习动态规划时常被提及的经典试题,很有代表性,常在因内大大小小的社区内看到众人对此类问题的讨论。

学习最好的方式便是归纳总结、借鉴消化,基于这个目的,本文对此类问题也做了讲解,在一些优秀思想的基础上添加了个人观点。

闲话少说,进入正文,开始打家劫舍,看今晚收获几何?

2. 线性盗贼

2.1 问题描述

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

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

示例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。

2.2 问题分析

在打劫之前先不要急入进入房间,应该是先做全局的估算。

想象当盗贼从第一间房屋开始偷窃,他可以选择是偷还是不偷。偷还是不偷的选择不是源于他瞬时良心上的发现,而是收益的多少。如果只有一间房间,他会毫不犹豫的选择偷,这样才能带来今晚最大的收益。

下图所示为当只有一间房子时盗贼能获取到的最高金额。

27_0.png

如果有 2 间房屋,盗贼面对第一间房屋时会如何想呢?

收益固然重要,但是如果触发了报警系统,偷鸡不成蚀把米这样的赔本生意,肯定是不能做的。所以他的想法是可以偷,如果从此房间内的获取到的收益大于从另一个房间内获取到受益,否则,放弃当前房间,而选择进入第二间房间。

28.png

29.png

怎么知道偷还是不偷哪一个获取的收益最大。唯一法则就是比较,也就偷和不偷两者的受益取其大。如果只有 2 间房间,很容易通过比较得到最大收益,两间房间内选择最大的即可。

如果如下图有多个房间时,当盗贼面对第一个房间时,又怎么知道偷和不偷哪一种选择可以获取最大收益,他又不能占卜。

30.png

虽然盗贼不能未卜先知,但是,从数学角度而言,问题可以演变成间隔求和问题,把所有可能的值求和,然后取最大值。于上图而言,可以的求和方案有:

  • 2+9+1=12
  • 2+3=5
  • 7+3=10

选择最大求和值为12。时时记住,所有问题都是可以通过穷举得到的,回溯是一种典型的穷举思想,故此问题可以使用回溯算法求解所有的和,并取最大值的和。有兴趣者可自行完成。

方案不可能只有一种!

如前所述,当盗贼站在当前房间时,他可以选择偷或不偷。他是无法预知偷或不偷最终返回的收益那一个大,但是站在递归的角度,当前子问题依赖另两个子问题返回值。

Tips: 进入任意房间进行偷窃可认为是一个子问题。如果A子问题的值受B子问题值的影响,可称A依赖B子问题。

  • 如果偷,则不能偷相邻,将依赖下下一个子问题(房间)返回的结果。也就是说偷后的收益为当前房间内的金钱数加上下下一个子问题返回的金钱数。

31.png

  • 如果不偷,则可以偷相邻,将依赖直接相邻子问题返回的结果。也就是说偷后的收益为当前房间内的金钱数加上下一个子问题返回的金钱数。

31_1.png

  • 最后再比较偷或不偷中的最大值。递归的最大优点,把大问题分解成小问题。求解出小问题的值后再回溯出大问题的值。

代码实现:

#include <iostream>
#include <cstring> 
using namespace std;
//房间数量
int n;
//房间的金额
int m[100];
//结果
int res=0;
int djjs_(int idx) {
    //没有房间,得到 0
	if(idx>n)return 0;
	//偷, 进入下下个房间
	int t= m[idx]+djjs_(idx+2);
	//不偷,可以直接进行相邻房间
	int nt=djjs_(idx+1);
	return max(t,nt);
}
int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>m[i];
	}
	res= djjs_(1);
	cout<<res;
	return 0;
}

动态规划思想:

动态规划中的动态也可以理解为子问题的规模大小,本题的子问题便是当房间数量变化时所影响的,子问题不同,其值不同,但其最优结果可以帮助后续子问题的求到最优解。

  • 创建一维dp数组,第一个dp值存储当前子问题的最优值。当只一个房间时,选择偷。此dp或当前子问题可以获取到最优值。

32.png

  • 面对第2间房子,在偷和不偷间选择。选择偷,则dp值等于dp[0]+m[2]=7,不偷,则为上一个子问题最优值的延续。在两者中选择最大值 7

33.png

  • 以此类推,对于后面的任一个房间而言,只需要选择是延续上一个子问题的最优值还是在当前房间的金额的基础上加上上上一个子问题的最优值。最终答案为:12

34.png

如上可知动态规划的状态转移方程:dp[i]=max( dp[i-1],m[i]+dp[i-2] )

编码实现:

#include <iostream>
#include <cstring> 
using namespace std;
//房间数量
int n;
//房间的金额
int m[100];
int dp[100]={0}; 
//结果
int res=0;
int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		dp[i]=max( dp[i-1],m[i]+dp[i-2] );
		res=max(res,dp[i]);
	}
    cout<<res;
	return 0;
}

3. 环形盗贼

3.1 问题描述

在上述问题的基础上,对问题稍做了一些演变,如果房间是环形的,即第一间房子和最后一间房子也是相邻的。求解盗贼能盗取到的最大值是多少?

根据题意可知,如果偷了第一间房子,则最后一间房子时不能偷的,反之,则可以。所以可以把此题目演变成2 个问题。

  • 假设没有最后一个房间时,求解盗取的最大值。

  • 假设没有第一个房间时,求解盗取的最大值。

然后再求解这两个问题中的的最大值。

举个例子,如有3个房间,房间内的金额分别为[1,2,3],此时盗贼能盗取的最大金额可分如下情况分析。

  • 假设没有最后一间房子。根据前文的动态规划原则,则最大收益为 2。如下图所示。

35.png

  • 假设没有第一间房子。则最大收益为3

36.png

  • 最后在23中选择最大值3,即为本题最终解。

编码实现:

#include <iostream>
#include <cstring> 
using namespace std;
//房间数量
int n;
//房间的金额
int m[100];
int dp[100]= {0};
//结果
int res=0;
int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>m[i];
	}
    memset(dp,0,sizeof(dp) );
	//没有最后一间房子
	for(int i=1; i<n; i++) {
		dp[i]=max( dp[i-1],m[i]+dp[i-2] );
		res=max(res,dp[i]);
	}
	 memset(dp,0,sizeof(dp) );
	//没有第一间房子
	for(int i=2; i<=n; i++) {
		dp[i]=max( dp[i-1],m[i]+dp[i-2] );
		res=max(res,dp[i]);
	}
	cout<<res;
	return 0;
}

4.树上盗贼

问题到此,房间即不是一排,也不是环形,现在房子都挂在一棵二叉树上。且要求同一个边上的两间房子不能同时偷盗。

示例 1: 输入:[3,2,3,null,3,null,1]

40.png

输出:7

题目变成了典型的树型动态规划问题,可以直接套用树型动态规划的通用求解模板。

#include <iostream>
#include <cstring>
using namespace std;
int dp_[100][2];
//一维数组描述二叉树节点之间的关系,-1表示没有子节点,把普通二叉树模拟成完全二叉树
int m_[]= {0,3,2,3,-1,3,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int res=0;
void treeDp(int idx) {
	if(m_[idx]==-1)return;
	//不偷
	dp_[idx][0]=0;
	//偷
	dp_[idx][1]=m_[idx];
    //深度搜索子节点
	for(int i=0; i<2; i++) {
         //计算子节点位置
		int sid=idx*2+i;
		if(m_[sid]==-1)continue;
		//基于子节点深度搜索
		treeDp(sid) ;
		//不偷,查找子节点上偷与不偷的最大值
		dp_[idx][0] += max(dp_[sid][0],dp_[sid][1]);
         res=max(res,dp_[idx][0]);
		//偷,添加子节点不偷时的状态值
		dp_[idx][1]+=dp_[sid][0];
         res=max(res,dp_[idx][1]);
	}
}
int main(int argc, char** argv) {
	treeDp(1);
	cout<<res;
}

另有一种使用递归的简易算法:

#include <iostream>
using namespace std;
//树节点类型
struct TreeNode {
	int tid;
	int val;
	int left;
	int right;
};
//已经节点及关系
TreeNode m[5]= { {1,3,2,3 },{ 2,2,-1,4, },{3,3,-1,5 },{ 4,3,-1,-1},{5,1,-1,-1 } };

/* 返回一个 pair
*   first  不偷时得到的最大钱数
*   second 偷时得到的最大钱数
*/
pair<int,int> dp(int root) {
	if (root == -1) {
		pair<int,int> p= {0,0};
		return p;
	}
    //进入左树
	pair<int,int> left = dp( m[root-1].left );
    //进入左树
	pair<int,int> right = dp( m[root-1].right);
	// 抢,下家就不能抢了
	int rob =  m[root-1].val + left.first + right.first;
	// 不抢,下家可抢可不抢,取决于收益大小
	int not_rob = max(left.first, left.second)+ max(right.first, right.second);
	pair<int,int> res= {not_rob, rob};
	return res;
}

int rob(int root) {
	pair<int,int> res= dp(root);
	return max(res.first, res.second);
}

int main(int argc, char** argv) {
	int res=rob(1);
	cout<<res;
	return 0;
}

5. 总结

本文讲解了三版本的打家劫舍题目,这三个版本难度呈上升趋势,但其内在本质是差不多。抽研出其求解的核心思想,并且能分析其特征,归纳出一类型问题,则无论题目描述如何变化,便也是能快速找出解决问题的算法。

标签:试题,idx,int,res,房间,C++,问题,打家劫舍,dp
From: https://blog.51cto.com/gkcode/6985329

相关文章

  • 最低通行费C++
    题目描述】一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动。他要从网格的左上角进,右下角出。每穿越中间1个小方格,都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时,都需要缴纳一定的费用。这个商人期望在规定时间内用最少......
  • 怪盗基德的滑翔翼C++
    题目描述】怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的......
  • 【面试经验分享】MySQL数据库面试题:如何定位慢查询?
    面试官:MySQL中,如何定位慢查询?候选人:嗯~,我们当时做压测的时候有的接口非常的慢,接口的响应时间超过了2秒以上,因为我们当时的系统部署了运维的监控系统Skywalking,在展示的报表中可以看到是哪一个接口比较慢,并且可以分析这个接口哪部分比较慢,这里可以看到SQL的具体的执行时间,所以可以......
  • 前端学习笔记202306学习笔记第三十七天-经典面试题1
       ......
  • C++中BigEden、SmallEden编码
    基本概念大端小端表示,一个数字在内存中或硬盘上记录时,是高位在前或在后,高位在前就是大端(BigEden),在后就是小端(samllEden)。我们日常记录和代码里定义一千二百三四如:inta=1234;就是大端记录。如果是小端的一千二百三十四:就是"4321"了。 通常应用一般而言,平台使用的大......
  • C++_函数模板
    函数模板》是不进行编译的,因为类型还不知道模板的实例化》函数调用点进行实例化:在函数调用点,编译器用用户指定的类型,从原模板实例化一份函数代码出来模板函数》才是要被编译器所编译的模板类型参数typename/class模板非类型参数模板的实参推演》可以根据用户传......
  • stm32用keil5新建C/C++写硬件串口模块的套路
    新建文件:写代码:就在这里开始写initSerial了..........
  • C/C++ 数据结构-直接选择排序
    #include<iostream>#include<Windows.h>usingnamespacestd;voidswap(int*num1,int*num2){inttemp=*num1;*num1=*num2;*num2=temp;}intmain(){intret[]={161,156,170,164,158,180,159,185,172,176};intlen=......
  • 高级 / 资深前端面试题集锦
    以下是一线互联网公司高级前端面试题总结,包括百度、腾讯、网易、字节、知乎、京东、滴滴,小米,感兴趣的欢迎留言交流。1、请简述JsBridge2、请说一下SSR的单机QPS3、请说一下eggJs的初始化原理4、前端错误如何捕获,promise的错误是如何捕获的5、vue的domdiff算法6、vue的Chil......
  • C/C++ 数据结构五大核心算法之贪心算法_钱币找零问题
    贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架,......