Java50分 MLE求助!!!
查看原帖
Java50分 MLE求助!!!
1263951
Ss1132313926楼主2024/3/5 10:45
import java.io.IOException;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int []arr1=new int[n];
        int []arr2=new int[n];

        for(int i=0;i<n;i++){
            arr1[i]=scanner.nextInt();
        }

        for(int i=0;i<n;i++){
            arr2[i]=scanner.nextInt();
        }
        int [][]dp=new int[n][n];
        
        //初始化
        dp[0][0]=arr1[0]==arr2[0]?1:0;
        for(int i=1;i<n;i++){
            if(arr1[i]==arr2[0]){
                dp[i][0]=1;
            }else {
                dp[i][0]=dp[i-1][0];
            }
        }
        for(int j=1;j<n;j++){
            if(arr2[j]==arr1[0]){
                dp[0][j]=1;
            }else {
                dp[0][j]=dp[0][j-1];
            }
        }
        
        //递推
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                int p1 =dp[i][j-1];
                int p2 =dp[i-1][j];
                int p3=arr1[i]==arr2[j]?(1+ dp[i-1][j-1]):0;
                dp[i][j]=Math.max(p1,Math.max(p3,p2));
            }
        }
        System.out.println(dp[n-1][n-1]);
        

    }


}
2024/3/5 10:45
加载中...