dp.java

来自「算法导论上机作业java实现」· Java 代码 · 共 71 行

public class Dp
{
	
	public static int[][]  LCS_Length(String X,String Y)
	{
		int m = X.length()+1;
        int n = Y.length()+1;
		int[][] c = new int [m][n];
		int[][] b = new int [m][n];
         
         for(int i=0;i<m;++i)
        	 c[i][0] = 0;
         for(int j=0;j<n;++j)
        	 c[0][j] = 0;
         for(int i=1;i<m;++i)
         {
        	 for(int j=1;j<n;++j)
        	 {
        		 if(X.charAt(i-1) == Y.charAt(j-1))
        			 {
        			 c[i][j] = c[i-1][j-1] + 1;
        			 b[i][j] = 1;
        			 }
        		 else
        			 if(c[i-1][j] >= c[i][j-1])
        			 {
        				 c[i][j] = c[i-1][j];
        				 b[i][j] = 2;
        			 }
        			 else
        			 {
        				 c[i][j] = c[i][j-1];
        				 b[i][j] = 3;
        			 }
        	 }
        	
         }
         return b;
	}
         
        public static void Print_Lcs(int[][] b,String X,int i,int j)
        {
        	if(i == 0 || j==0)
        		return ;
        	else
        		if(b[i][j] == 1)
        		{
        			Print_Lcs(b,X,i-1,j-1);
        			System.out.print(X.charAt(i-1));
        		}
        		else
        			if(b[i][j] == 2)
        				Print_Lcs(b,X,i-1,j);
        			else
        				Print_Lcs(b,X,i,j-1);
        }



	
	public static void main(String[] args) 
	{
	   String X = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD";
	   String Y = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG";
	   Print_Lcs( LCS_Length(X,Y),X,X.length(),Y.length());
	   
	}
}