(动态规划) 数字三角形 (加油淦！！！)

解题思路:很容易想到的是递归，遍历所有的路径，然后找出最大值，但是，可惜的是超时
从倒数第二行倒着看，会发现一个规律

举例：
1
5 6

8 9 10
7 4 3 2
先看倒数第二行
8 = max(7,4) + 8
9 = max(4,3) + 9
10 = max(3,2) + 10
接着向上一行
6 = max(9,10) + 6
5 = max(8,9) + 5
接着向上一行
1 = max(5,6) + 1
规律很明显

注意事项:

参考代码:

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][]arr = new int[n][n];
        
        for (int i = 0;i < n; i++){
            for (int j = 0; j <= i; j++){
                arr[i][j] = in.nextInt();
            }
        }
        
        for (int i = n-2; i >= 0; i--){
            for (int j = 0; j <= i; j++){
                arr[i][j]+=Math.max(arr[i+1][j],arr[i+1][j+1]);
            }
        }
        System.out.println(arr[0][0]);
        in.close();

    }
}