首页 > 编程语言 >试题 算法训练 数字三角形(本人粗暴解法+递推与记忆化搜索解法)

试题 算法训练 数字三角形(本人粗暴解法+递推与记忆化搜索解法)

时间:2024-03-31 23:04:45浏览次数:27  
标签:10 试题 int max dfs long 递推 解法 105

问题描述

  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
  径,使该路径所经过的数字的总和最大。
  ●每一步可沿左斜线向下或右斜线向下走;
  ●1<三角形行数≤100;
  ●三角形中的数字为整数0,1,…99;

输入格式

  文件中首先读到的是三角形的行数。

  接下来描述整个三角形

输出格式

  最大总和(整数)

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30

咱就是说,看到这个题目马上想到当前路径的值加到下一个路径的值,最后在取出最大的路径值就可以了。

方法简单粗暴,直接开始吧,首先来看看我的思路吧

以题目例子为例

70000
38000
81000
27440
45265

未标红的都是数组初始化的值,可以不管。

第一步是7,走到第二步,变化如下

70000
3+7=108+7=15000
81000
27440
45265

第三步则同理

70000
1015000
8+10=181+max(10,15)=160+16=1600
27440
45265

这里取max就是取当前路径步值最大的了,然后我们可以看到当前路径的首尾只能选一个,也就是j=1和j=i的情况,如上面中的8只能+10,0只能+16,而中间可以选两个,那么这个特殊判断一下就好了

以此类推,走完后,数值如下

70000
1015000
18161500
202520190
2430272624

如图所示,可以看到最大的就是那个30了

那么接下来看AC代码咯,一样的简单粗暴(有注释)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	int n,x;
	int d[105][105]={0};
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>d[i][j];
		}
	}
//正片开始	
	int qmax=d[1][1];  //初始化,也就是三角形的头部
	for(int i=2;i<=n;i++){  //从第二行开始
		for(int j=1;j<=i;j++){  //每列
			if(j!=1&&j!=i){    //中间那一块可以选两个
				d[i][j]+=max(d[i-1][j],d[i-1][j-1]);//加上大的那个
				qmax=max(qmax,d[i][j]);  //保证qmax是当前最大的
			}
			else{
				if(j==1){  //每行的首情况
					d[i][j]+=d[i-1][j];
					qmax=max(qmax,d[i][j]);  //这里也要保证qmax是最大的
				}
				else if(j==i){  //每行的尾情况
					d[i][j]+=d[i-1][j-1];
					qmax=max(qmax,d[i][j]); //这里也要保证qmax是最大的
				}
			}
			
		}
	}
	cout<<qmax;  //输出最大的qmax
}

上面的代码虽然已经能AC了,但咱们还是建议读者学习一下这个记忆化搜索。我们一步一步往下来呈现记忆化的过程。

上面AC的代码是按从顶往下的路径走法,可能复杂度为2^n次方,这个复杂度很不理想,虽然是暴力,但这个暴力还能在优化,优化后的复杂度可以为n^2。

我们首先来递推一下

如果按照从底向上的走法,那么就不需要考虑首尾的下标情况了,咱们直接看图

70000
38000
81000
2(max(4,5)+2=7)7(max(5,2)+7=12)4(max(2,6)+4=10)4(max(6,5)+4=10)0
4(4)5(5)2(2)6(6)5(5)

以此类推,最终变成

7(30)0000
3(23)8(21)000
8(20)1(13)0(10)00
2(7)7(12)4(10)4(10)0
4(5)5(5)2(2)6(6)5(5)

可以看到,最终我们只需要输出d[1][1]就ok了,省去了很多的麻烦

那么递推代码如下(也能AC):

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	int n, x;
	int d[105][105] = { 0 };
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> d[i][j];
		}
	}
	//正片开始
	for (int i = n-1; i >= 1; i--) {  //从倒数第二行开始
		for (int j = 1; j <= i; j++) {
			d[i][j] += max(d[i + 1][j], d[i + 1][j + 1]);
		}
	}
	cout << d[1][1];
}

可以看到代码少了很多,而且复杂度为n^2

那在递归搜索一下,代码会更简单(但会运行超时,只有57分)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, x;
int d[105][105] = { 0 }, r[105][105] = {0};
int dfs(int i, int j) {
	/*if (i == n)return d[i][j];
	return d[i][j] += max(dfs(i + 1, j), dfs(i + 1, j + 1));*/
	if (i == n)return d[i][j]; //递归到边界了,返回
	return r[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + d[i][j];
	
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> d[i][j];
		}
	}
	//正片开始
	//让d数组始终保持数字三角形的数据原状态,避免递归数据添加混乱
	for (int i = 1; i <= n; i++)r[n][i] = d[n][i];//r数组是从底往上走,这里先初始化底部的数据
	//但其实这个for的初始化赋值也可以省略掉,因为递归过程已经帮我们算进去了
	cout << dfs(1,1);
}

dfs中注释的是我一开始写的递归,但发现数据好像被重复计算,导致数据加进去会有误,所以搞了一个辅助数组r

那为什么会超时呢,因为有大量的重复计算,此时,我们只需要小小的加一个记忆化的代码就ok了

也就是当r[i][j]>0的时候直接return 因为r[i][j]已经被max()中计算过了,不需要在回头算

代码如下(AC):

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, x;
int d[105][105] = { 0 }, r[105][105] = {0};
int dfs(int i, int j) {
	if (r[i][j])return r[i][j];//记忆,默认为0,大于0说明已经算过了
	if (i == n)return d[i][j]; //递归到边界了,返回
	return r[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + d[i][j];
	
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> d[i][j];
		}
	}
	//正片开始
	cout << dfs(1,1);
}

复杂度为n^2

标签:10,试题,int,max,dfs,long,递推,解法,105
From: https://blog.csdn.net/weixin_67024935/article/details/137050192

相关文章

  • 史上最全Java核心面试题(带全部答案)2024年最新版
    今天要谈的主题是关于求职,求职是在每个技术人员的生涯中都要经历多次。对于我们大部分人而言,在进入自己心仪的公司之前少不了准备工作,有一份全面细致面试题将帮助我们减少许多麻烦。在跳槽季来临之前,特地做这个系列的文章,一方面帮助自己巩固下基础,另一方面也希望帮助想要换工......
  • Android 12 第一次运行就报错,Android面试题集锦在这里
    以前加上intent-filter的话,exported就默认是true。Android 12之后开始强制大家声明exported属性**。**例如:<application<activityandroid:name=“.actvitiy.MainActivity”android:exported=“true”<activityandroid:name=“.actvitiy.SchemeActivity”android:e......
  • Mybatis相关面试题详细总结
    什么是MyBatis?MyBatis是一种开源的Java持久化框架,它通过XML或注解方式将对象与数据库表进行映射,提供了简单而强大的数据库访问功能。MyBatis的优点是什么?简单易用:MyBatis提供了直观的XML配置和注解,使得数据库操作变得简单而直观。灵活性:MyBatis允许开发人员编写自定义SQL......
  • 腾讯这10道算法面试题,看完跪了。。。
    节前,我们星球组织了一场算法岗技术&面试讨论会,邀请了一些互联网大厂朋友、参加社招和校招面试的同学,针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。汇总合集:《大模型面试宝典》(2024版)发布!......
  • (二)计算机数值方法之Cholesky分解法
    数学问题:利用Cholesky分解法解决线性方程问题Ax=b,其中(A,b)分别为:解决代码:​#include"windows.h"#include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream>#include<iomanip>#include<math.h>usingnamespacest......
  • SpringMVC常见面试题
    1:Springmvc执行流程回答:版本1:视图版本,jsp用户发送出请求到前端控制器DispatcherServletDispatcherServlet收到请求调用HandlerMapping(处理映射器)HandlerMapping找到具体的处理器,生成处理器对象及处理器拦截器(如果有),再一起返回给DispatcherServletDispatcherServlet调......
  • 【Java编程】【算法面试题】【数组轮转】给定一个整数数组 nums,将数组中的元素向右轮
    原题:给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。例如:nums=[1,0,-1,2,3]k=1预期结果:nums=[3,1,0,-1,2]k=2预期结果:nums=[2,3,1,0,-1]以此类推。。。【本文思路解析】:1.不实用额外的数组,会多一部分开销;2.每次轮转,位置移动1位,共计移......
  • 面试题:JVM 调优
    一、JVM参数设置1.tomcat的设置vm参数修改TOMCAT_HOME/bin/catalina.sh文件,如下图JAVA_OPTS="-Xms512m-Xmx1024m"2.springboot项目jar文件启动通常在linux系统下直接加参数启动springboot项目nohupjava-Xms512m-Xmx1024m-jarxxxx.jar--spring.pro......
  • 【Java编程】【算法面试题】【数组合并】以数组 intervals 表示若干个区间的集合,其中
    原始题目:以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。......
  • 面试题:Spring Boot Starter的功能与使用场景
    SpringBootStarter是SpringBoot框架为了简化项目的初始化和配置工作而设计的一种模块化依赖管理方式。它主要具有以下几个关键功能和使用场景:功能:1.依赖管理每个Starter都是一组相关的依赖项集合,这些依赖项都是为了实现特定功能而预先配置好的。例如,`spring-boo......