http://poj.org/problem?id=1458
一道容易的DP,求最长公共子序列的
dp[i][j],代表str1中的第i个字母和str2中的第j个字母的最多的公共字母数
#include <stdio.h>
#include <iostream>
#include <string.h> using namespace std;
int dp[][]={}; int main()
{
char str1[],str2[];
while(~scanf("%s %s",str1,str2))
{
/* scanf("%s",str1)
scanf("%s",str2);*/
int len1=strlen(str1);
int len2=strlen(str2);
for(int i=;i<=len1;i++)
for(int j=;j<=len2;j++)
{
if(str1[i-]==str2[j-]) dp[i][j]=dp[i-][j-]+; //这个就是那个递推公式，但str1[i-1]和str2[j-1]想等于时dp[i][j]就会等于前一个加一，不等就是等于前面的最大的一个
else dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
printf("%d\n",dp[len1][len2]);
}
return ;
}
http://poj.org/problem?id=1159
这个是POJ1159的题目，试求插入的最少的字符，使其变成回文字符串
这个最少的字符MIN=N-N和N的逆序数的最长公共子序列
所以这道题也就是和上面的那个题目一样，求最长的公共子序列，不过有一个地方比上面要特殊一点，就是数组只可以开滚动数组，不然POJ就爆内存
也只是在部分地方进行了改动即可
在这里也使用了一个我以前从未用过的函数，reverse ，这个函数在algorithm的头文件里
作用是把远数组变成逆序的，使用方法也就是reverse(begin(),end());
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm> using namespace std; int dp[][];
string str1,str2; int main(){
int n;
while(scanf("%d",&n)!=EOF){
cin>>str1;
str2=str1;
memset(dp,,sizeof(dp));
reverse(str2.begin(),str2.end());
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(str1[i-]==str2[j-]){
int tem=dp[(i-)%][j-]+; //这个和上面的不同的原因在于这个是滚动数组，而滚动数组的话，原数组一般都是有值的，只不过是新的值在原数组上进行覆盖而已，求最大的公共子序列，就不能排除原来的数组的dp[i%2][j]会小于tmp；
dp[i%][j]=max(dp[i%][j],tem);
}
else dp[i%][j]=max(dp[(i-)%][j],dp[i%][j-]);
}
cout<<n-dp[n%][n]<<endl;
}
return ;
}