題目37：回文字元串

題目連結：

http://acm.nyist.net/JudgeOnline/problem.php?pid=37

描述

所謂回文字元串，就是一個字元串，從左到右讀和從右到左讀是完全一樣的，比如”aba”。當然，我們給你的問題不會再簡單到判斷一個字元串是不是回文字元串。現在要求你，給你一個字元串，可在任意位置添加字元，最少再添加幾個字元，可以使這個字元串成為回文字元串。

輸入

第一行給出整數N（0<N<100）

接下來的N行，每行一個字元串，每個字元串長度不超過1000.

輸出

每行輸出所需添加的最少字元數

樣例輸入

1 Ab3bd

樣例輸出

2

算法思想：

是一道經典的動态規劃算法，算法思想與最大公共子串一樣，技巧就是将這個問題轉換成一個最大公共子串問題。将輸入str的字元串逆轉記為s，接下來的問題就變成求str和s的最大公共子串的長度，然後用str的長度len減去最大公共子串的長度，得到的差即為需要添加最少的字元數。

最大公共子串長度的遞推公式如下：

dp[i][j]={dp[i−1][j−1]+1max(dp[i−1][j], dp[i][j−1])str1[i]==str2[j]str1[i]≠str2[j]

源代碼

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[];
int main()
{
    int len, ans, N, tmp, old;
    string str[];
    cin >> N;
    for (int i = ; i < N; i++)
    {
        cin >> str[i];
        memset(dp,,sizeof(dp));
        string s = str[i];
        len = s.length();
        //逆轉字元串str[i]
        reverse(s.begin(),s.end());
        //這裡采用了壓縮動态數組存儲空間的方法
        //dp[k]代表的是dp[j - 1][k]，dp[k - 1]代表的是dp[j][k - 1]
        //old記錄的是dp[j - 1][k - 1].
        for (int j = ; j < len; j++) 
        {
            old = ;
            for (int k = ; k < len; k++)
            {
                tmp = dp[k];
                if (str[i][j] == s[k])
                {
                    dp[k] = old + ;
                }
                else
                {
                    if (dp[k - ] > dp[k])
                        dp[k] = dp[k - ];
                }
                old = tmp;
            }
        }
        cout << len - dp[len - ] << endl;
    }
    return ;
}
           

算法複雜度：

兩層循環周遊，算法時間複雜度為O(n^2)。