题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

    7
  3   8
8   1   0

2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000

从上向下迭代

需要枚举最后一行数据以确定最大值

时间复杂度 $O(n^2)$ ，需要$n^2$额外空间

Java 代码

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] arr=new int[n][n];
        //dp表示，到达dp[i][j]所经历的最大路径
        int[][] dp=new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            String[] t=br.readLine().split(" ");
            for(int j=0;j<i;j++){
                arr[i-1][j]=Integer.parseInt(t[j]);
            }
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(i>0){
                    dp[i][j]=-10001;
                }
            }
        }
        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])+arr[i-1][j-1];
            }
        }
        int res=-10001;
        for(int i=1;i<=n;i++){
            res=Math.max(res,dp[n][i]);
        }
        System.out.print(res);
    }
}

从下向上迭代

最后输出dp[0][0]即可

时间复杂度 $O(n^2)$，需要$n^2$额外空间

Java 代码

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] arr=new int[n][n];
        //dp表示，到达dp[i][j]所经历的最大路径
        int[][] dp=new int[n][n];
        for(int i=1;i<=n;i++){
            String[] t=br.readLine().split(" ");
            for(int j=0;j<i;j++){
                arr[i-1][j]=Integer.parseInt(t[j]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i<n-1){
                    dp[i][j]=-20001;
                }else{
                    dp[i][j]=arr[i][j];
                }
            }
        }
        for(int i=n-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[i][j]=Math.max(dp[i+1][j+1],dp[i+1][j])+arr[i][j];
            }
        }
        System.out.print(dp[0][0]);
    }
}

空间优化

最后输出dp[0][0]即可

时间复杂度 $O(n^2)$，需要$n$额外空间

Java 代码

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] arr=new int[n][n];
        for(int i=1;i<=n;i++){
            String[] t=br.readLine().split(" ");
            for(int j=0;j<i;j++){
                arr[i-1][j]=Integer.parseInt(t[j]);
            }
        }
        //dp表示，到达dp[i][j]所经历的最大路径
        int[] dp=new int[n+1];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[j]=Math.max(dp[j],dp[j+1])+arr[i][j];
            }
        }
        System.out.print(dp[0]);
    }
}