线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列

AcWing 898. 数字三角形

1.题目

 898. 数字三角形

2.思路

DP问题首先考虑状态转移方程，定义一个集合f ( i , j) ，表示从第一个数字（1,1）走到第 i行，第 j列（i , j）的所有方案的集合，那么我们要求的就是其中方案的整数之和的最大值。

这个点可以由左上方(i−1 , j)走过来，即f( i-1, j)+a(i , j)
这个点也可以由右上方(i−1,j−1)走过来，即f( i-1, j-1)+a(i , j)
所以状态转移方程就是f（i , j）=max{ f( i-1, j) , f( i-1, j-1) } + a(i , j)

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

3.Ac代码

思路一

import java.util.Arrays;
import java.util.Scanner;public class Main {static int N=510;static int [][]a=new int[N][N];  //存储每一层数字static int [][]f=new int[N][N];  //从第一个数字走到第 i行，第 j列元素的方案集合public static void main(String[] args)  {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];}}int res=Integer.MIN_VALUE;for(int i=1;i<=n;i++){res=Math.max(res,f[n][i]);}System.out.println(res);}
}

思路二

import java.util.Arrays;
import java.util.Scanner;public class Main {static int N=510;static int [][]a=new int[N][N];  //存储每一层数字static int [][]f=new int[N][N];  //从第一个数字走到第 i行，第 j列元素的方案集合public static void main(String[] args)  {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]);}
}

AcWing 895. 最长上升子序列

1.题目

 895. 最长上升子序列

2.思路

首先还是考虑状态表示，定义一个fi 表示从第一个数开始算，以第 i个数结尾的最长上升子序列，如果我们选第1个数，那么对应的就是f1
如果我们选第2个数，那么对应的就是f2
如果我们选第j个数，那么对应的就是f j
所以状态转移方程就是f i=max （f i +1)

3.Ac代码

import java.util.Scanner;public class Main {static int N=1010;static int []a=new int[N];  //存储数组static int []f=new int[N];  //fi 表示从第一个数开始算，以第 i个数结尾的最长上升子序列public static void main(String[] args)  {Scanner sc=new Scanner(System.in);int n=sc.nextInt();for (int i = 1; i <=n; i++) {a[i]=sc.nextInt();}int res=0;for (int i = 1; i <=n; i++) {f[i]=1;for (int j = 1; j < i; j++) {if(a[j]<a[i]){f[i]=Math.max(f[i],f[j]+1);}}res=Math.max(res,f[i]);}System.out.println(res);}
}

感谢你能看完，如果对你有帮助的话，点个赞支持下