題目：給定一個字符串，問最少插入多少字符，使字符串變成回文字符串。

思路：X:原字符串 Y：逆字符串 需要插入的字符數=X的長度-(X與Y的LCS的長度)

　??? 這里使用了滾動數組，壓縮空間,原因：d[i][j]只依賴于 d[i-1][j] d[i][j-1]

1 #include <iostream> 2 #include <string> 3 #include <cmath> 4 #include <vector> 5 #include <algorithm> 6 #include <sstream> 7 #include <cstring> 8 9 using namespace std; 10 int dp[2][5005]; 11 int main() 12 { 13 14 string s1,s2; 15 16 while(cin>>s1) 17 { 18 s2=s1; 19 int n,i,j; 20 n=s1.size(); 21 reverse(s1.begin(),s1.end()); 22 memset(dp,0,sizeof(dp)); 23 24 for(i=1;i<=n;i++) 25 for(j=1;j<=n;j++) 26 if(s1[i-1]==s2[j-1]) 27 dp[i%2][j]=dp[(i-1)%2][j-1]+1; 28 else 29 dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]); 30 31 cout<<n-dp[n%2][n]<<endl; 32 33 } 34 return 0; 35 }

?

轉載于:https://www.cnblogs.com/xiaoying1245970347/p/4698668.html

總結

以上是生活随笔為你收集整理的Palindrome(插入字符变成回文字符串)的全部內容，希望文章能夠幫你解決所遇到的問題。

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