hiho一下第162周《Making Palindrome》题目分析

4
3

本题是一道经典动态规划题目。

假设f(s[1..n])表示把长度为n的字符串s改写成回文串需要的操作。

如果s[1] == s[n]，那么f(s[1..n]) = f(s[2..n-1])。

否则f(s[1..n])是以下三种情况的最小值：

  1. 在s[n]后添加一个字符匹配s[1]，f(s[1..n]) = 1 + f(s[2..n])。
  2. 在s[1]前添加一个字符匹配s[n], f(s[1..n]) = 1 + f(s[1..n-1])。
  3. 把s[1]和s[n]其中一个修改为另外一个使其匹配，f(s[1..n]) = 1 + f(s[2..n-1])。

2 answer(s)

0

删除的情况不需要考虑吗？？？

1

90分是为什么

include

include

include

using namespace std; int f[300][300]; char c[200]; int maxx; int main(){ cin>>c;

 int n=strlen(c)-1;
 for(int k=0;k<=n;k++)
 {
    for(int i=k;i>=0;i--)
         {
            for(int j=k;j<=n;j++)
             {
                if(i>=j)continue;
                if(c[i]==c[j])
                 {  

                    f[i][j]=f[i+1][j-1];
                }
                else

                 {
                f[i][j]=min(1+f[i+1][j],min(1+f[i+1][j-1],1+f[i][j-1]));

                }
            maxx=max(maxx,f[i][j]);
            }
         }

}

cout<

write answer 切换为英文 切换为中文

转发分享

▲