2020年蓝桥杯省赛 数字三角形 ------动态规划

。。。。。。。。。

import java.util.Scanner;
public class Main{
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        int n= input.nextInt();
        int [][]ant=new int[n][n];
        int [][]dp=new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                ant[i][j]= input.nextInt();
            }
        }
        dp[0][0]=ant[0][0];
        for(int i=1;i<n;i++)
        {
            dp[i][0]=dp[i-1][0]+ant[i][0];
        }
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i][j]=ant[i][j]+Math.max(dp[i-1][j],dp[i-1][j-1]);
            }
        }
        if(n%2!=0)
        {
            System.out.println(dp[n-1][n/2]);
        }
        else{
            System.out.println(Math.max(dp[n-1][n/2],dp[n-1][n/2-1]));
        }
    }
}