AcWing 898. 数字三角形

解题思路

相关代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a[][] = new int[n+1][n+1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                a[i][j] = scanner.nextInt();

        int f[][] = new int[n+1][n+1];
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                f[i][j] = Integer.MIN_VALUE;

        /*
        *   f[i][j] 值表示的是最大值
        * */
        f[1][1] = a[1][1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<=n;j++){
                
                f[i][j]=Math.max(f[i-1][j-1],f[i-1][j])+a[i][j];
            }
        }
        
        int res=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            res=Math.max(res,f[n][i]);
        }
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35