蓝桥杯 算法训练 ALGO-124 数字三角形
2024-09-01 00:55:13
算法训练 数字三角形
时间限制:1.0s 内存限制:256.0MB
问题描述
(图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径,使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走;
●1<三角形行数≤100;
●三角形中的数字为整数0,1,…99;
.
(图3.1-1)
径,使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走;
●1<三角形行数≤100;
●三角形中的数字为整数0,1,…99;
.
(图3.1-1)
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和(整数)
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
题目解析:
将数字三角形放在二维数组中。从倒数第二行开始逐行往上,每个数都加上它的下一行同一列和下一行右列中最大的那一个数。
路径最大和即为数组中第一个数。
示例代码:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader; public class Main {
private static int row; //行数
private static int[][] arr;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
row = Integer.parseInt(br.readLine());
arr = new int[row][row]; for(int i = 0; i < row; i++){
String[] str = br.readLine().split(" ");
for(int j = 0; j <= i; j++){
arr[i][j] = Integer.parseInt(str[j]);
}
} int maxSum = maxSum(row,arr); System.out.println(maxSum);
}
/**
* 最大和
* @param row 行数
* @param arr 数组
* @return 该路径的最大和
*/
private static int maxSum(int row, int[][] arr) {
for(int i = row-2; i >= 0; i--){
for(int j = 0; j <= i; j++){
arr[i][j] += maxNum(arr[i+1][j] , arr[i+1][j+1]);
}
}
return arr[0][0];
} /**
* 求两个数中的最大数
* @param a
* @param b
* @return 最大数
*/
private static int maxNum(int a, int b) {
return a>b?a:b;
}
}
最新文章
- NSString NSUrl 相互转化
- C# 枚举(enum)
- Win10 + VS2015 下编译 Qt5.6.0
- iOS - Swift iOS 开发体系
- sp.ui.rte.js参数错误
- php操作Memcache示例
- asp.net验证码及怎么获取里面的数值(整合)
- 正整数从1到N,输出按照字典序排序的前K个数
- 2^x mod n = 1 【杭电-HDOJ-1395】 附题
- liunx 平台下软件包管理
- 为Windows资源管理器右键菜单添加菜单项
- Spring详解(四)------注解配置IOC、DI
- CentOS6.9中挂载NTFS移动硬盘
- 5.python函数
- BZOJ_1042_[HAOI2008]硬币购物_容斥原理+背包
- ILRuntime_NewbieGuide—导读
- oracle数据库 查看被锁定表及解锁方法
- Python平时代码的一些知识
- 011 pandas的常见操作
- 适用于 Windows 7 SP1、Windows Server 2008 R2 SP1 和 Windows Server 2008 SP2 的 .NET Framework 4.5.2 仅安全更新说明:2017 年 9 月 12 日