三角形题解（动态规划）

解题思路: 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;

}

}