线性DP算法的实现

题目需要注意的点
这道题我认为最容易错的点就是边界问题，并且如果是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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法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]);
}
1
2
3
4
5
6
7
8
9

}
降维
对于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]);
}
1
2
3
4
5
6
7
8
9

}
好像没有看见一维版本（见第二份代码），故补充一份题解。
从上往下，朴素版
#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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

}
从上往下，空间优化版，一维
#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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

}
从下往上，无法优化成一维，因为需要预先读入全部数值
#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]);
1
2
3
4
5
6

}