题目需要注意的点
这道题我认为最容易错的点就是边界问题，并且如果是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)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]); }
}
好像没有看见一维版本（见第二份代码），故补充一份题解。
从上往下，朴素版
#include using namespace std; const int N=510,INF=1e9; int n; int a[N][N]; //保存每个位置的值 int f[N][N]; //f[i][j]表示从(1,1)走到(i,j)的所有路径中，总和最大的那一条路径的总和 int main() { scanf(“%d”,&n);
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=0;j<=i+1;j++) //注意这里j从0到i+1,因为对于边界点,它的上一层只有一条路径通向它 f[i][j]=-INF; //初始化近似为-∞ f[1][1]=a[1][1]; //由f[i][j]的定义，(1,1)点的f值就是本身 for(int i=2;i<=n;i++) //这样，我们从第二层开始枚举至第n层 for(int j=1;j<=i;j++) f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; int res=-INF; for(int i=1;i<=n;i++) res=max(res,f[n][i]); //最大值在第n层的某一个点取得 printf("%d",res); return 0;
}
从上往下，空间优化版，一维
#include using namespace std; const int N=510,INF=1e9; int n; int f[N],a[N]; //f[j]表示从(1,1)走到(n,j)的所有路径中，总和最大的那一条路径的总和 int main() { scanf(“%d”,&n);
for(int j=0;j<=n+1;j++) //注意这里j从0到i+1,因为对于边界点,它的上一层只有一条路径通向它 f[j]=-INF; //初始化近似为-∞( 也可以memset(f,0xc0,sizeof f) ) scanf("%d",&f[1]); //由f[i][j]的定义，(1,1)点的f值就是本身 for(int i=2;i<=n;i++) //这样，我们从第二层开始枚举至第n层 { for(int j=1;j<=i;j++) scanf("%d",&a[j]); //读入每层的值（不能与下面合并，因为下面是逆向的） for(int j=i;j>=1;j--) f[j]=max(f[j-1],f[j])+a[j]; } int res=-INF; for(int i=1;i<=n;i++) res=max(res,f[i]); //最大值在第n层的某一个点取得 printf("%d",res); return 0; }
从下往上，无法优化成一维，因为需要预先读入全部数值
#include using namespace std; const int N=510; int f[N][N]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ scanf(“%d”,&f[i][j]); } }
for(int i=n;i>=1;i--){ for(int j=i;j>=1;j--){ f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j]; } } printf("%d",f[1][1]); }
