最长公共子序列

最长公共子序列

动态规划

一 问题分析

二 代码实现

package lcsLenth;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;

public class bin
{

    public static void main(String[] args) throws IOException
    {
          char []x= {'0','A','B','C','B','D','A','B'};
          char []y= {'0','B','D','C','A','B','A'};
          lcsLenth myLcsLenth=new lcsLenth(x, y);
    }

}
class lcsLenth
{
    char []x;
    char []y;
    int c[][];
    int b[][];
    String con="";
    public lcsLenth(char []x,char []y) throws IOException
    {
        this.x=x;
        this.y=y;
        this.c=new int[x.length][y.length];
        this.b=new int[x.length][y.length];
        lcsLenth();
        backtrace(x.length-1,y.length-1);
        display();
    }
    public void lcsLenth()
    {
        
        // case1:
        for(int i=0; i<x.length; i++)
        {
            c[i][0]=0;
        }
        for(int j=0; j<y.length; j++)
        {
            c[0][j]=0;
        }
        for(int i=1; i<x.length; i++)
        {
            for(int j=1; j<y.length; j++)
            {
                if(x[i]==y[j])
                {
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else
                {
                    if(c[i][j-1]>=c[i-1][j])
                    {
                        c[i][j]=c[i][j-1];
                        b[i][j]=2;
                    }
                    else 
                    {
                        c[i][j]=c[i-1][j];
                        b[i][j]=3;
                    }
                }
            }
            
        }
        
        
    }
    public void backtrace(int i, int j)
    {
        if(i>0&&j>0)
        {
            switch (b[i][j])
            {
            case 1:
                backtrace(i-1, j-1);
                con=con+x[i];
                break;
            case 2:
                backtrace(i, j-1);
                break;
            case 3:
                backtrace(i-1, j);
                break;
            }
        }
    }
    public void display() throws IOException
    {
    	BufferedWriter fout=new BufferedWriter(new FileWriter("out.txt"));
    	fout.write("c[i][j]");
    	fout.newLine();
    	for(int i=0; i<x.length; i++)
    	{
    		for(int j=0; j<y.length; j++)
        	{
    			fout.write(""+c[i][j]+"	");
        	}
    		fout.newLine();
    	}
    	fout.flush();
    	fout.newLine();
    	fout.write("b[i][j]");
    	fout.newLine();
    	for(int i=0; i<x.length; i++)
    	{
    		for(int j=0; j<y.length; j++)
        	{
    			fout.write(""+b[i][j]+"	");
        	}
    		fout.newLine();
    	}
    	fout.flush();
    	fout.newLine();
    	fout.write("common: ");
    	fout.newLine();
    	fout.write(con);
    	fout.flush();
    }
    
}

三 运行结果

四 总结收获

1. 明白了动态规划是什么
2. 动态规划构造最优解

五 不足改进

1. 动态规划依然无法很好地理解