题目描述

JAVA 代码

时间复杂度: 状态 * 转移
O(n^2)的

import java.util.*;
import java.io.*;

class Main{
    static int N = 510, INF = Integer.MAX_VALUE;
    //这里最好设置成long型. 不然会溢出
    static long[][] a= new long[N][N], f = new long[N][N];

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

        //a[][] 从下标 “1” 开始. 与 f[][] 一致. 
        for(int i=1; i<=n; i++){
            for(int j=1; j<=i; j++){
                a[i][j] = sc.nextInt();
            }
        }

        for(int i=0;i<=n; i++){
            //这里有个trick: 在边界的 
            //左半边or右半边, 不存在的越界一位的.
            //也会被计算在内, 所以也要设成 -INF.
            for(int j=0; j<=i+1; j++){
                f[i][j] = -INF;
            }
        }

        //设置头节点. 
        f[1][1] = a[1][1];
        for(int i=2; i<=n;i++){
            for(int j=1;j<=i;j++){
                //状态转移方程.
                //个人理解：
                //算上一层左边节点, 和上一层右边节点. 谁大.
                //再加上本节点. ok~
                f[i][j] = Math.max(f[i-1][j-1]+ a[i][j], f[i-1][j]+ a[i][j]);
            }
        }

        long res = 0;
        for(int i=0;i<n;i++)res= Math.max(res, f[n][i]);
        System.out.println(res);

    }
}