解题思路:很容易想到的是递归,遍历所有的路径,然后找出最大值,但是,可惜的是超时
从倒数第二行倒着看,会发现一个规律
举例:
1
5 6
8 9 10
7 4 3 2
先看倒数第二行
8 = max(7,4) + 8
9 = max(4,3) + 9
10 = max(3,2) + 10
接着向上一行
6 = max(9,10) + 6
5 = max(8,9) + 5
接着向上一行
1 = max(5,6) + 1
规律很明显
注意事项:
参考代码:
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][]arr = new int[n][n]; for (int i = 0;i < n; i++){ for (int j = 0; j <= i; j++){ arr[i][j] = in.nextInt(); } } for (int i = n-2; i >= 0; i--){ for (int j = 0; j <= i; j++){ arr[i][j]+=Math.max(arr[i+1][j],arr[i+1][j+1]); } } System.out.println(arr[0][0]); in.close(); } }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:635 |
矩形面积交 (C语言代码)浏览:1510 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:689 |
C语言训练-最大数问题 (C语言代码)浏览:633 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:619 |
【出圈】 (C语言代码)浏览:793 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1294 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |
Hello, world! (C++代码)浏览:1743 |
关于C语言变量位置的问题浏览:272 |