题目需要注意的点

这道题我认为最容易错的点就是边界问题，并且如果是JAVA，容易有溢出问题。

一般就是就是向下走，和向上爬两种思路，向上爬的思路可以不需要考虑边界问题。

而当向下走的时候，需要考虑边界问题。也就是对于f[2][1]的时候，f[1]f[0]并没有设置这个值，默认为0，题中的数字有负数，则会出现错误的最大值。需要对于f进行重置，置为Integer.MIN_VALUE.

JAVA中最最容易错的点

：如果f[i][j]= Math.max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j])其中的f[i - 1][j - 1]如果为Integer.MIN_VALUE,并且a[i][j] = 负数时候，会溢出！！！需要写成 Math.max(f[i - 1][j - 1] + f[i - 1][j]);

向下走

JAVA 代码

import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        int[][] a = new int[510][510];
        int[][] f = new int[510][510];
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        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++) {
            for (int j = 0; j <= i + 1; j++) {
                f[i][j] = Integer.MIN_VALUE;
            }
        }
        f[1][1] = a[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                f[i][j] = Math.max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
                // 一定要注意，先取MAX，再求和
            }
        }
        int res = Integer.MIN_VALUE;
        for (int k = 1; k <= n; k++) {
            res = Math.max(res, f[n][k]);
        }
        System.out.println(res);
    }

算法2 向上爬👴

JAVA 代码

import java.util.Scanner;

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

        for (int i = n; i >= 1; i--) {
        //从最后一排开始走，从下往上。
            for (int j = 1; j <= i; j++) {
                f[i][j] = Math.max(f[i + 1][j + 1], f[i + 1][j]) + a[i][j];
            }
        }

        System.out.println(f[1][1]);
    }
}

降维

对于LeetCode这个题的要求需要达到$O(N)$的空间，所以需要用滚动数组来处理，关于滚动数组有个处理技巧，如果上一层是j,j+1, 那么j直接顺序枚举即可。如果上一层是j,j-1,那么需要保证j是在j-1之前更新，于是就需要倒序枚举。

import java.util.Scanner;

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

        for (int i = n; i >= 1; i--) {
        //从最后一排开始走，从下往上。
            for (int j = 1; j <= i; j++) {
                f[j] = Math.max(f[j + 1], f[j]) + a[i][j];
            }
        }

        System.out.println(f[1]);
    }
}

心得

个人感觉第二种相对难想一些，但省去了讨论边界以及最后再求最大值。如果有问题，小伙伴们可以多多讨论哈!