UVA 字符串区间DP
UVA 10617 Again Palindrome
做题感悟：这题自己开始按照矩阵连乘的思路画了一个表然后就找到规律了
。
解题思路：首先我们设 dp[ i ] [ j ] 为 从i 到 j 最多有多少回文串。s[ i ] 与s[ j ] 相等或者不相等，
(1)、如果s[ i ] != s[ j ] ,那么如果去掉第 j 个字符回文数为 dp [ i ] [ j-1] ,如果去掉第 i 个字符回文数为dp [ i +1 ] [ j ] ,但是这样重复了区间 i+1 ,j -1 ,so~> dp [ i ] [ j ] = dp [ i ] [ j-1 ] + dp [ i+1 ] [ j ] - dp [ i+1 ] [ j-1 ] ;
(2)、如果s [ i ] == s [ j ] ,同理那么如果去掉第 j 个字符回文数为 dp [ i ] [ j-1] ,如果去掉第 i 个字符回文数为dp [ i +1 ] [ j ] ,还得减去 dp [ i+1 ] [ j - 1 ] ,但是 s[ i ] 与 s [ j ] 都不减去也可以那样的话就是 dp [ i+1 ] [ j-1 ] +1 , so~> dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp[ i + 1 ] [ j ] +1 ;
注意：这题要用long long 。
代码：
-
#include<stdio.h>
-
#include<iomanip>
-
#include<vector>
-
#include<queue>
-
#include<fstream>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<iostream>
-
#define INT long long int
-
using namespace std ;
-
const double INF = 99999999 ;
-
const int MY = 15 ;
-
const int MX = 100 + 10 ;
-
INT len ;
-
char s[MX] ;
-
INT dp[MX][MX] ;
-
void init()
-
{
-
memset(dp,0,sizeof(dp)) ;
-
for(INT i=1 ;i<=len ;i++)
-
dp[i][i]=1 ;
-
}
-
void DP()
-
{
-
for(INT t=2 ;t<=len ;t++)
-
for(INT i=1 ;i+t-1<=len ;i++)
-
{
-
INT j=i+t-1 ;
-
if(s[i]==s[j])
-
dp[i][j]=dp[i][j-1]+dp[i+1][j]+1 ;
-
else dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1] ;
-
}
-
cout<<dp[1][len]<<endl ;
-
}
-
int main()
-
{
-
INT Tx ;
-
scanf("%lld",&Tx) ;
-
while(Tx--)
-
{
-
scanf("%s",s+1) ;
-
len=strlen(s+1) ;
-
init() ;
-
DP() ;
-
}
-
return 0 ;
-
}
10739 - String to Palindrome
做题感悟：这题也是按照矩阵连乘的思路写的，但是开始写的代码有点挫，不好理解，其实这种题递推一下就好。
解题思路：设 dp[ i ] [ j ] 为 i 到 j 的构成回文的最好操作数。因为删除一个字符和添加一个字符一样的性质，因此看成一种操作。
(1)、如果 s [ i ] == s[ j ] dp [ i ] [ j ] = dp [ i+1 ] [ j - 1 ] ;
(2) 、如果s[ i ] ! = s [ j ] 删除第 i 个字符为 dp [ i+1 ] [ j ] ,删除第 j 个dp [ i ] [ j - 1 ] ,修改第 j 个字符使 s [ i ] = s[ j ] , so ~> dp [ i ] [ j ] = min( dp[ i ][ j-1 ] , min( dp[ i + 1 ][ j ],dp[ i+1 ][ j-1 ] ) ) + 1 ;
代码：
-
#include<stdio.h>
-
#include<iomanip>
-
#include<vector>
-
#include<queue>
-
#include<fstream>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<iostream>
-
#define INT long long int
-
using namespace std ;
-
const double INF = 99999999 ;
-
const int MY = 15 ;
-
const int MX = 1000 + 10 ;
-
int Tx,len ;
-
char s[MX] ;
-
int dp[MX][MX] ;
-
void DP()
-
{
-
memset(dp,0,sizeof(dp)) ;
-
for(int t=2 ;t<=len ;t++) // 区间个数
-
for(int i=1 ;i+t-1<=len ;i++) // 枚举所有区间
-
{
-
int j=i+t-1 ;
-
if(s[i]==s[j]) // 两个字符相等
-
dp[i][j] =dp[i+1][j-1] ;
-
else // 不相等
-
dp[i][j] = min(dp[i][j-1],min(dp[i+1][j],dp[i+1][j-1]))+1 ;
-
// 分别代表删除第 j 个字符 ，删除第 i 个字符 ，修改第 j 个字符
-
}
-
}
-
int main()
-
{
-
int Tx,cse=1 ;
-
scanf("%d",&Tx) ;
-
while(Tx--)
-
{
-
scanf("%s",s+1) ;
-
len = strlen(s+1) ;
-
DP() ;
-
cout<<"Case "<<cse++<<": "<<dp[1][len]<<endl ;
-
}
-
return 0 ;
-
}
11151 Longest Palindrome
做题感悟：这题挺有意思，早上想了好久都没有AC，下午头脑一热一写代码就Ac了。
解题思路：设 dp [ i ] [ j ] 为字符串 i 到 j 最长的回文串为多长，当然dp[ i ] [ i ] 为 1 ，如果 s[ i ] ==s [ j ] 是 dp[ i ] [ j ] = dp [ i+1 ] [ j -1 ] + 2 ,如果不相等那么dp[ i ] [ j ] = max( dp [ i ][ j-1 ] ,dp [ i+1 ] [ j ]) ;
代码：
-
#include<stdio.h>
-
#include<iomanip>
-
#include<vector>
-
#include<queue>
-
#include<fstream>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<iostream>
-
#define INT long long int
-
using namespace std ;
-
const int INF = 99999999 ;
-
const int MY = 15 ;
-
const int MX = 1000 + 10 ;
-
int len ;
-
char s[MX] ;
-
int dp[MX][MX],n ;
-
void DP()
-
{
-
memset(dp,0,sizeof(dp)) ;
-
for(int i=0 ;i<len ;i++)
-
dp[i][i]=1 ;
-
for(int t=2 ;t<=len ;t++)
-
for(int i=0 ;i+t-1<len ;i++)
-
{
-
int j=i+t-1 ;
-
if(s[i]==s[j])
-
dp[i][j]=dp[i+1][j-1]+2 ;
-
else dp[i][j]=max(dp[i][j-1],dp[i+1][j]) ;
-
}
-
cout<<dp[0][len-1]<<endl ;
-
}
-
int main()
-
{
-
int Tx ;
-
scanf("%d",&Tx) ;
-
getchar() ;
-
while(Tx--)
-
{
-
gets(s) ;
-
len=strlen(s) ;
-
DP() ;
-
}
-
return 0 ;
-
}
做题感悟：开始做时还感觉打印字符串不好打印，其实做起来就简单了。
解题思路：这题动态方程不在解释直接给出。
(1) s[ i ] == s[ j ] dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] ;
(2) s[ i ] != s[ j ] dp[ i ] [ j ] = min { dp [ i+1 ] [ j ] , dp [ i ] [ j-1 ] } +1 ;
关于输出的解释：递归打印路径 --->如果 s [ i ] == s[ j ] 则先输出 s[ i ] 的值（因为 s[ i ] 在左边先输出），然后调用 print( i+1, j-1 ) ,在此语句的后面输出 s [ [ j ]( 当调用完上面的语句后才输出它，因为它在最右边，输出是安从左往右输出的)，否则判断 dp[ i+1 ] [ j ] 与 dp [ i ] [ j - 1 ] 的大小，也就是动态方程的第二种情况，如果是dp [ i +1 ] [ j ] < dp [ i ] [ j - 1 ] ,那么说明当时选择的是 dp [ i +1 ] [ j ] ，添加了s [ i ] 字符到 j 的后面，我们就可以先输出 s [ i ] ,然后调用 print( i+1 , j ) ,输出 s [ i ] (此为添加上的字符)，如果dp [ i+1 ] [ j ] >= dp[ i ] [ j - 1 ] ,同理输出即可。
代码：
-
#include<stdio.h>
-
#include<iomanip>
-
#include<vector>
-
#include<queue>
-
#include<fstream>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<iostream>
-
#define INT long long int
-
using namespace std ;
-
const int INF = 99999999 ;
-
const int MY = 15 ;
-
const int MX = 1000 + 10 ;
-
int n,num ;
-
char s[MX] ;
-
int dp[MX][MX] ;
-
void DP()
-
{
-
memset(dp,0,sizeof(dp)) ;
-
for(int t=2 ;t<=n ;t++)
-
for(int i=0 ;i+t-1<n ;i++)
-
{
-
int j=i+t-1 ;
-
if(s[i]==s[j])
-
dp[i][j]=dp[i+1][j-1] ;
-
else
-
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1 ;
-
}
-
cout<<dp[0][n-1]<<" " ;
-
}
-
void print(int x,int y) // 递归输出
-
{
-
if(x==y)
-
{
-
cout<<s[x] ;
-
return ;
-
}
-
if(x+1==y&&(s[x]==s[y]))
-
{
-
cout<<s[x]<<s[y] ;
-
return ;
-
}
-
if(s[x]!=s[y]) // 说明变化了
-
{
-
if(dp[x+1][y]>dp[x][y-1]) // x 前
-
{
-
cout<<s[y] ;
-
print(x,y-1) ;
-
cout<<s[y] ;
-
}
-
else // y+1 前
-
{
-
cout<<s[x] ;
-
print(x+1,y) ;
-
cout<<s[x] ;
-
}
-
}
-
else
-
{
-
cout<<s[x] ;
-
print(x+1,y-1) ;
-
cout<<s[y] ;
-
}
-
}
-
int main()
-
{
-
while(cin>>s)
-
{
-
n=strlen(s) ;
-
DP() ;
-
print(0,n-1) ;
-
cout<<endl ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/38067853
- 点赞
- 收藏
- 关注作者
评论（0）