題目大意：給你一個字符串，問你最少加上幾個字符可以得到一個回文串
思路：給一個字符串添加字符，使其變成回文字符串。這個過程可以看成是：對這個字符串兩邊同時進行處理，讓兩邊第一個字符一樣了，然后刪去兩邊的這個字符，再繼續(xù)進行。理論遞推關(guān)系：使該字符串前i個和后j個完全相同至少所需添加的字符個數(shù)=min{使該字符串前i個和后j-1個完全相同的個數(shù)+1 ；使該字符串前i-1個和后j個完全相同的個數(shù)+1 ；使該字符串前i-1個和后j-1個完全相同的個數(shù)+2/0（第i個和倒數(shù)第j個字符不相同/相同）}
遞推關(guān)系代數(shù)化：設(shè)使該字符串前i個和后j個完全相同至少所需添加的字符個數(shù)為a[i][j];字符串有n個字符。
if(c[i]!=r[n+1-j]) a[i][j]=min{a[i-1][j],a[i][j-1],a[i-1][j-1]+2};else a[i][j]=min{a[i-1][j],a[i][j-1],a[i-1][j-1])};起始條件（邊界條件）：a[i][0]=a[0][i]=i;(0<=i<=n)還有一個問題就是：遞推之后，答案是a[?][?]。這個就可以理解成是a[?][?]的時候，該字符串就變成了回文串。然后根據(jù)表達的意思，應(yīng)該是min{a[i][j](i+j==n||i+j==n-1)}。(n為字符總個數(shù))沒仔細看，內(nèi)存太小了！得用滾動數(shù)組（不知道是不是這個名字），反正就是兩個一維數(shù)組滾動著用唄。也沒仔細看時間復(fù)雜度，這么仔細一想，時間復(fù)雜度O(n^2)；
之后查了題解，別人的一句話，很6啊：尋找串與其逆串的最長公共子序列。因為此子序列必是回文串，剩下的字符就是需要插入的。
新聞熱點
疑難解答
