287. 数字三角形

难度

困难

题目描述

有一个由数字组成的三角形数塔，站在上一层的某个点，只能到达其下方左右的两个点。现在请找到一条从上到下的路径，使得路径上所有数字相加之和最大

输入

第一行输入一个数字 n代表数塔层数

接下来n行，按数塔图形，每行有一个或多个的整数，表示该层节点的值（节点值）

输出

输出一个整数，代表从上到下路径上所有数字相加和的最大值。

 

样例输入1

6
3
9 5
4 2 1
3 4 9 6
3 5 3 7 3
2 1 3 9 3 2

样例输出1

39

一道比较简单的动态规划题目

代码：

public class SZSJX {
    public static void main(String[] args) {
        Scanner s1 = new Scanner(System.in);
        int n = s1.nextInt();

        int[][] tri = new int[n + 1][n + 1];
        int[][] dp = new int[n + 1][n + 1];//当前位置获得的最大值

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                tri[i][j] = s1.nextInt();
            }
        }

        int maxsum = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + tri[i][j];
                maxsum = Math.max(maxsum, dp[i][j]);
            }
        }
        System.out.println(maxsum);
    }
}