回文字元串（動态規劃解法）

時間限制：3000 ms | 記憶體限制：65535 KB

難度：4

<dl></dl>

<dt>描述</dt>

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

<dt>輸入</dt>

<dd>第一行給出整數N（0&lt;N&lt;100）</dd>

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

<dt>輸出</dt>

<dd>每行輸出所需添加的最少字元數</dd>

<dt>樣例輸入</dt>

<dd></dd>

<dt>樣例輸出</dt>

一道動态規劃題，輔助空間cost[i][j]表示要将從s[j]個字元開始長度為i的子串變為對稱串需要添加的字元個數；這樣，動态方程為：

cost[0][i] = cost[1][i] = 0;//長度為0和長度為1的串

cost[i][j] = 當s[j] == s[i+j-1]時，字元串長度加2，需要增加的字元個數相同，即cost[i][j] = cost[i-2][j+1];

                 否則，cost[i][j] = min{cost[i-1][j], cost[i-1][j+1]} + 1；

代碼如下：