小虎Killer


私信TA

用户名:1328767672

访问量:399

签 名:

等  级
排  名 36396
经  验 365
参赛次数 1
文章发表 2
年  龄 0
在职情况 学生
学  校 内蒙古农业大学
专  业

  自我简介:

TA的其他文章

解题思路: 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 人评分

  评论区