DP三角形题解

解题思路:

注意事项:

参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int T=sc.nextInt();
       while (T>0) {
           int n = sc.nextInt();
           int a[][] = new int[n][n];
           for (int i = 0; i < n; i++) {
               for (int j = 0; j <= i; j++) {
                   a[i][j] = sc.nextInt();
               }
           }
           int dp[][] = new int[n][n];
           dp[0][0] = a[0][0];
           int b[] = new int[n];
           for (int i = 1; i < n; i++) {
               for (int j = 0; j <= i; j++) {
                   if (j != 0)
                       dp[i][j] = Math.max(dp[i - 1][j] + a[i][j], a[i][j] + dp[i - 1][j - 1]);
                   if (j == 0)
                       dp[i][j] = dp[i - 1][j] + a[i][j];
                   if (i == n - 1)
                       b[j] = dp[i][j];
               }
           }
           Arrays.sort(b);
           System.out.println(b[n - 1]);
           T--;
       }
   }
}