闫氏dp分析法
不做优化的代码(超时)
import java.io.*;
import java.util.*;
public class Main{
static int N = 3010;
static int[][] f = new int[N][N];
static int[] a = new int[N];
static int[] b = new int[N];
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();
for(int i = 1;i<=n;i++)
b[i] = sc.nextInt();
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++){
f[i][j] = f[i-1][j];
if(a[i] == b[j]){
f[i][j] = 1;
for(int k = 1;k<j;k++)
if(b[k]<b[j]) f[i][j] = Math.max(f[i][j],f[i-1][k]+1);
}
}
int max = 0;
for(int i = 1;i<=n;i++) max = Math.max(max,f[n][i]);
System.out.println(max);
}
}
优化
第三层循环发现是在求f[i-1][1~j-1]前缀的最大值
在求的时候可以用一个变量来代替
import java.io.*;
import java.util.*;
public class Main{
static int N = 3010;
static int[][] f = new int[N][N];
static int[] a = new int[N];
static int[] b = new int[N];
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();
for(int i = 1;i<=n;i++)
b[i] = sc.nextInt();
for(int i = 1;i<=n;i++){
int maxv = 0;
for(int j = 1;j<=n;j++){
f[i][j] = f[i-1][j];
if(a[i] == b[j]) f[i][j] = Math.max(maxv+1,f[i][j]);
if(a[i] > b[j]) maxv = Math.max(maxv,f[i-1][j]);
//求f[i-1][1~j]前缀的最大值
}
}
int max = 0;
for(int i = 1;i<=n;i++) max = Math.max(max,f[n][i]);
System.out.println(max);
}
}