解题思路: DP

注意事项:

参考代码:

import java.util.Scanner;


public class 数字塔从上到下所有路径中和最大的路径DP {


public static void main(String[] args) {

Scanner input = new Scanner(System.in);

int m = input.nextInt();

while(m -- > 0){

int n = input.nextInt();

int a[][] = new int [n][n];

for(int i = 0;i < n;i++){

for(int j = 0;j <= i;j ++){

a[i][j] = input.nextInt();

}

}

System.out.println(max(a));

}

}


public static int max(int[][] a){


int max = 0;

int [][] dp = new int[a.length][a.length];

dp[0][0] = a[0][0];

for (int i = 1; i < a.length; i++) {

for (int j = 0; j <= i; j++) {


if (j == 0) {

dp[i][j] = dp[i - 1][j] + a[i][j];

}else {


dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];


}

max = Math.max(max, dp[i][j]);


}

}

return max;



}


}


点赞(0)
 

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论