Java实现输出数字三角形实例代码
作者:盛世如念 发布时间:2023-08-25 02:09:51
标签:java,数字,三角形
题目:
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 nn,表示数字三角形的层数。
接下来 nn 行,每行包含若干整数,其中第 ii 行表示数字三角形第 ii 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
题解:
相对于二维数组来看,每一个数只能往下放或者右下方走,发现从下往上走更加方便实现。我们反向思考,从下或者右下方走,如果我们每次都知道了某数的下放和右下方谁最大了呢?
每次从最后行的相邻两个数比较谁最大,把每次最大的加到第一个数的上方,这样数组的第一行第一个数就是最大值了。
例如:
代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int nums[][] = new int[n][];
for(int i = 0;i<n;i++){
nums[i] = new int[i+1];
for(int j = 0;j<i+1;j++){
nums[i][j] = sc.nextInt();
}
}
for(int i =n-1 ;i>0;i--){
for(int j = 0;j<nums[i].length-1;j++){
nums[i-1][j] += Math.max(nums[i][j],nums[i][j+1]);
}
}
System.out.println(nums[0][0]);
}
}
来源:https://blog.csdn.net/wasane/article/details/122550949
0
投稿
猜你喜欢
- 第一种方法:string s=abcdeabcdeabcde;string[] sArray=s.Split(c) ;foreach(str
- 1.引入AOP依赖<dependency>
- 使用场景EntityListeners在jpa中使用,如果你是mybatis是不可以用的它的意义对实体属性变化的跟踪,它提供了保存前,保存后
- 在logback.xml中加上该配置,包名如:com.xxx<logger name="packageName"
- 简介前提条件:确保本机已经安装 VS Code。确保本机已安装 SSH client, 并且确保远程主机已安装 SSH server。VSC
- 在类中自定义的“函数”称为“方法”,由于C#是完全面向对象的
- springboot项目启动慢的问题排查springboot项目,随着时间的推移,启动耗时逐步增加,从几分钟慢慢的达到30多分钟,有点恐怖!
- 需求说明实际操作过程中,从D盘根目录下的ak.txt读取文件写入D盘根目录下的hello.txt文件内实现思路写两个方法,一个用于读取目标文
- 如果不知道,类的静态变量存储在那? 方法的局部变量存储在那? 赶快收藏Java内存区域主要可以分为共享内存,堆、方法区和线程私有内存,虚拟机
- java 实现MD5加密算法的简单实例实现代码:import java.security.NoSuchAlgorithmException;
- 前言空间分配要点有:一是空间分配的连续性;二是动态内存申请;三是防止程序执行中出现异常错误。提示:开始讲解了嗷~后续会根据精力持续更新嗷!!
- Android基础教程数据存储之文件存储将数据存储到文件中并读取数据1、新建FilePersistenceTest项目,并修改activit
- feign传输List的坑无法直接传输List错误方法1@RequestMapping(value = "/stat/mercha
- 尝试了各种防止中文乱码的方式,但是还是乱码;最后还是细节问题导致;解决方式:以及俩种方式是百度的,我的问题不是这俩块1.在requestMa
- 什么是ByteBuddyByteBuddy是一个java的运行时代码生成库,他可以帮助你以字节码的方式动态修改java类的代码。为什么需要B
- 在编写ui界面时因为手机分辨率大小不同,所以展现出来的效果也是不同的,这个时候就需要考虑适配器,让根据手机分辨率自动适配相应尺寸来展示界面,
- Android版本更新实例详解1、导入xutils的jar包 2、在AndroidManifest.xml中添加权限 3、选择下载的路径,和
- 前言对于 InterruptedException,一种常见的处理方式是 “生吞(swallow)” 它 —— 捕捉它,然后什么也不做(或者
- 1.map遍历快速实现边距,文字自适应改变大小Container( // padding: EdgeI
- Android的消息机制几乎是面试必问的话题,当然也并不是因为面试,而去学习,更重要的是它在Android的开发中是必不可少的,占着举足轻重