Palindrome(dp)

题意：给定一个字符，问最少插入多少字符，使该字符串变成回文字符串。

思路：设原字符串序列为X，其逆字符串为Y，则最少插入的字符数=length(X)-X与Y的最长公共子序列的长度。

求LCS的状态转移方程为 max(dp[i-1][j],dp[i][j-1]) s1[i-1]!=s2[j-1]

dp[i][j] =

dp[i-1][j-1]+1; s1[i-1]==s2[j-1];

由于数据范围大，本题使用的滚动数组。

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <string>

 #include <sstream>

 #include <cstring>

 using namespace std;

 int dp[][];

 int main()

 {

     string s1,s2;

     int n;

     while(cin>>n)

     {

         cin>>s1;

         s2 = s1;

         reverse(s1.begin(),s1.end());

         memset(dp,,sizeof(dp));

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

         {

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

             {

                 if (s1[i-]==s2[j-])

                     dp[i%][j] = dp[(i-)%][j-]+;

                 else

                     dp[i%][j] = max(dp[(i-)%][j],dp[i%][j-]);

             }

         }

         int ans = n-dp[n%][n];

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

Palindrome(dp)

最新文章

热门文章