題意：給定一個字符串，求添加最少的字母使得該串是回文串。

思路：區間dp+記憶化搜索。dp[i][j]為區間的最小添加數，那么dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1；相等時則為dp[i+1][j-1];

code：

#include <bits/stdc++.h> using namespace std;const int INF=0x3f3f3f3f; const int N=1005; char s[N]; int n,dp[N][N];int dfs(int i,int j) {if (i>j||i==j) return dp[i][j]=0;if (dp[i][j]!=INF) return dp[i][j];int& ans=dp[i][j];if (s[i]==s[j]) ans=dfs(i+1,j-1);ans=min(ans,min(dfs(i+1,j),dfs(i,j-1))+1);return dp[i][j]; } void print(int i,int j) {if (i>j) return;if (i==j) {printf("%c",s[i]);return;}if (s[i]==s[j]){printf("%c",s[i]);print(i+1,j-1);printf("%c",s[i]);} else if (dp[i][j]==dp[i+1][j]+1){printf("%c",s[i]);print(i+1,j);printf("%c",s[i]);}else {printf("%c",s[j]);print(i,j-1);printf("%c",s[j]);} } int main() {while (~scanf("%s",s)){int n=strlen(s);memset(dp,INF,sizeof(dp));dfs(0,n-1);printf("%d ",dp[0][n-1]);print(0,n-1);puts("");} }

總結

以上是生活随笔為你收集整理的UVA 10453—— Make Palindrome的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。