数字三角形-java-动态规划

解题思路:

    “向左下走的次数与向右下走的次数相差不能超过 1”，所以你无论怎么走，终点都必定落在最后一行的中间位置

        最后一行是偶数行，那就是落在中间两个数

        奇数行，那就是中间那个数

        所以我是从下往上开始动态规划

        不能走的点设置成false就行，一开始只有最后一行的中间的数才是true，然后逐步往上更新能走的点
注意事项:

参考代码:

import java.util.Scanner;

public class Main{
    private static int[][] arr = new int[100][100];
    private static boolean[][] flag = new boolean[100][100];
    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j = 0; i--) {
            for (int j = 0; j <= i; j++) {
                boolean tempFlag = false;
                int left = 0;
                int right = 0;
                if (flag[i+1][j]) {
                    tempFlag = true;
                    left = arr[i+1][j];
                }
                if(flag[i+1][j+1]){
                    tempFlag = true;
                    right = arr[i+1][j+1];
                }
                if(tempFlag){
                    flag[i][j] = true;
                    arr[i][j] += Math.max(left,right);
                }
            }
        }

//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j <= i; j++) {
//                System.out.print(arr[i][j] + " ");
//            }
//            System.out.println();
//        }
        System.out.println(arr[0][0]);
    }
}