题目描述

最长公共子序列

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[][] f = new int[N][N];
    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        //java 中按行读..没法后移一位. 
        char[]  a = in.readLine().toCharArray();
        char[]  b = in.readLine().toCharArray();

        //方法一：将a[] b[] 前移一位.  
        for(int i=1; i<=n;i++){
            for(int j=1;j<=m;j++){
                //判断前两种情况. 01 10的情况
                f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
                //都包含 11的情况则比较 f[i][j], f[i-1][j-1]+1
                if(a[i-1]==b[j-1])//[i,j]被包含进来需要二者想等
                    f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
            }
        }

        System.out.println(f[n][m]);
    }
}

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[][] f = new int[N][N];
    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        //java 中按行读..没法后移一位. 
        char[]  a = in.readLine().toCharArray();
        char[]  b = in.readLine().toCharArray();

        //方法二： 将f[][] 后移一位. 不太友好, 有点难看
        for(int i=0; i<n;i++){
            for(int j=0;j<m;j++){
                //判断前两种情况. 01 10的情况
                f[i+1][j+1] = Math.max(f[i][j+1], f[i+1][j]);
                //都包含 11的情况则比较 f[i][j], f[i-1][j-1]+1
                if(a[i]==b[j])//[i,j]被包含进来需要二者想等
                    f[i+1][j+1]=Math.max(f[i+1][j+1],f[i][j]+1);
            }
        }

        System.out.println(f[n][m]);
    }
}

打印方便理解输出代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[][] f = new int[N][N];
    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        //java 中按行读..没法后移一位. 
        char[]  a = in.readLine().toCharArray();
        char[]  b = in.readLine().toCharArray();

        //方法一：将a[] b[] 前移一位.  
        for(int i=1; i<=n;i++){
            for(int j=1;j<=m;j++){
                //判断前两种情况. 01 10的情况
                f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
                System.out.println("i = "+ i + "   j = " + j);
                System.out.println("f[i-1][j] = "+ f[i-1][j] + "   f[i][j-1] = " + f[i][j-1]);
                System.out.println("-------------IF判断外------------------");
                //都包含 11的情况则比较 f[i][j], f[i-1][j-1]+1
                if(a[i-1]==b[j-1]){
                    f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
                    System.out.println("f[i][j] = "+ f[i][j] + "   f[i-1][j-1]+1 = " + f[i-1][j-1]+"+"+1);    
                    System.out.println("-------------IF判断内------------------");
                }
                System.out.println("-------------j循环++ ------------------");
                System.out.println();
            }
            System.out.println("-------------i循环++ ------------------");
        }

        System.out.println(f[n][m]);
    }
}

i = 1 j = 1
f[i-1][j] = 0 f[i][j-1] = 0
-------------IF判断外------------------
f[i][j] = 1 f[i-1][j-1]+1 = 0+1
-------------IF判断内------------------
-------------j循环++ ------------------

i = 1 j = 2
f[i-1][j] = 0 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 1 j = 3
f[i-1][j] = 0 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 1 j = 4
f[i-1][j] = 0 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 1 j = 5
f[i-1][j] = 0 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

-------------i循环 ------------------
i = 2 j = 1
f[i-1][j] = 1 f[i][j-1] = 0
-------------IF判断外------------------
-------------j循环 ------------------

i = 2 j = 2
f[i-1][j] = 1 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 2 j = 3
f[i-1][j] = 1 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 2 j = 4
f[i-1][j] = 1 f[i][j-1] = 1
-------------IF判断外------------------
-------------j循环++ ------------------

i = 2 j = 5
f[i-1][j] = 1 f[i][j-1] = 1
-------------IF判断外------------------
f[i][j] = 2 f[i-1][j-1]+1 = 1+1
-------------IF判断内------------------
-------------j循环++ ------------------

-------------i循环 ------------------
i = 3 j = 1
f[i-1][j] = 1 f[i][j-1] = 0
-------------IF判断外------------------
-------------j循环 ------------------

i = 3 j = 2
f[i-1][j] = 1 f[i][j-1] = 1
-------------IF判断外------------------
f[i][j] = 2 f[i-1][j-1]+1 = 1+1
-------------IF判断内------------------
-------------j循环++ ------------------

i = 3 j = 3
f[i-1][j] = 1 f[i][j-1] = 2