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