最长公共子序列5页.docx

动态规划一、 问题描述用动态规划法求两个字符串A=xzyzzyx和B=zxyyzxz的最长公共子序列二、 算法分析(1)、若xm=yn,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共自序列；(2)、若xmyn,且zkxm，则Zk是Xm-1和Yn的最长公共自序列；(3)、若xmyn,且zkyn，则Zk是Xm和Yn-1的最长公共自序列；设L(m,n)表示序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列的长度L表示已经决策的长度S表示每个决策的状态L(0,0)=L(0,j)=0 1im, 1jn L(i-1,j-1)+1 xi=yi,i1,j1L(i,j)= maxL(i,j-1),(L(i-1,j) xiyi,i1,j1 1 xi=yiS(i,j)= 2 xiyi 且L(i