学步园

要求插入最小数 那么求出最长公共子序列后N-最长公共子序列就是需要插入的最小数了 ，DP之LCS基础题 刚开始不会 想了好久没想出来 后来问志权 志权迅速画个LCS的图解析下就有点顿悟（看来有时侯站在巨人的肩膀上能让学习效率更加高啊！）LCS原理 设个二维数组 分为横列坐标，横坐标依次下去的是顺序列。纵坐标 从左到右是反序列。那么用

for(i=0;i<n;i++)

     for(j=0;j<n;j++)

遇到相等的tag[i][j]=tag[i-1][j-1]+;

不相等就tag[i][j]=max(tag[i-1][j],tag[i][j-1]);这样看比较抽象 画个图出来用例子去画一下就好明白很多了。。

我是J从最后一个元素开始回到0比较的 那样不用求反序列了。还有 这题数组下标从1开始ud好点 因为要用到i-1,j-1如果从0开始会越界数据不对 因为这样WA了很久 。代码:#include<iostream><br /> using namespace std;<br /> short dp[5010][5010];<br /> char str[5010];<br /> int max(int a,int b)<br /> {<br /> return (a>b?a:b);<br /> }<br /> int main()<br /> {<br /> short N,i,j;<br /> cin>>N;<br /> cin>>str+1;<br /> memset(dp,0,sizeof(dp));<br /> for(i=1;i<=N;i++)<br /> for(j=N;j>=1;j--)<br /> {<br /> if(str[i]==str[j])<br /> dp[i][j]=dp[i-1][j+1]+1;<br /> else<br /> dp[i][j]=max(dp[i-1][j],dp[i][j+1]);<br /> }<br /> cout<<N-dp[N][1]<<endl;<br /> return 0;<br /> }