hdu2084数塔

思路:从顶层走到底层可以变为从底层走到顶层，dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])

import java.util.Scanner;

public class hdu2084 {

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        for (int ii = 0; ii < x; ii++) {
            int n = sc.nextInt();
            int[][] aa = new int[n+1][n];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < i; j++) {
                    aa[i][j] = sc.nextInt();                
                }                
            }            
            for (int i = n; i > 0; i--) {
                for (int j = 0; j < i-1; j++) {
                    aa[i-1][j] += Math.max(aa[i][j], aa[i][j+1]);                
                }    
            }
        System.out.println(aa[1][0]);
        }
        sc.close();
    }
}