问题：

给定一个字符串，求最少添加几个字母，能使的字符串成为回文字符串。

Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:
Input: s = "g"
Output: 0

Example 5:
Input: s = "no"
Output: 1
 
Constraints:
1 <= s.length <= 500
All characters of s are lower case English letters.

　　

解法：DP(动态规划)

1.确定【状态】：字符串s的

• 第i个字符：s[i]
• 第j个字符：s[j]

2.确定【选择】：分两种情况

• s[i] == s[j]：
  • 前一个子串状态<不包含当前这两个字符s[i]s[j]>的需要步数:  dp[i+1][j-1]
• s[i] != s[j]：有以下2种情况，取最小值 + 1（余下另一个字符，使之也成为回文需要补充1个字符）。
• 字串s[i~j-1]的需要步数：dp[i][j-1] （这里余下字符s[j]）
• 字串s[i+1~j]的需要步数：dp[i+1][j] （这里余下字符s[i]）

3. dp[i][j]的含义：

字符串s的第 i 个字符到第 j 个字符为止，能使得原字符串成为回文字符串，最少需要添加字符数。

4. 状态转移：

dp[i][j]=

• (s[i] == s[j])：=前一个子串状态：dp[i+1][j-1]
• (s[i] != s[j])：=min {
  • 上一个包含s[i]字符的状态：dp[i][j-1]
  • 上一个包含s[j]字符的状态：dp[i+1][j]    }

5. base case：

• dp[i][i]=0：单文字子串，自己本身就是回文字符串，不需要添加任何字符。

6. 遍历顺序：

根据状态转移公式，在求得dp[i][j]之前，需先求得dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]

 因此需要：i:大->小，j:小->大 遍历

 

⚠️ 注意：本问题，i一定<=j，因此dp[i][j]中i>j的memory基本不会被用到。

只有在base case计算dp[i][i+1]且s[i]==s[i+1]的时候，作为★dp[i+1][j-1]被用到。应该为0。这也是在后面♻️ 优化处pre的赋值理由。

 

代码参考：

 1 class Solution {
 2 public:
 3     //status: s[i], s[j]
 4     //dp[i][j]: the min cost to make s[i,j],to a palindrome
 5     //option:
 6     //    case_1: if s[i]==s[j]: dp[i+1][j-1]
 7     //    case_2: if s[i]!=s[j]: min{
 8     //                choose s[i,j-1]: dp[i][j-1]
 9     //                choose s[i+1,j]: dp[i+1][j]
10     //             } + 1: make the left alphbet to a palindrome
11     //base case:
12     //dp[i][i]=0
13     //for: i:i+1->i, j:j-1->j
14     //     i:i--,    j:j++
15     int minInsertions(string s) {
16         int n = s.length();
17         vector<vector<int>> dp(n, vector<int>(n,0));
18         for(int i=n-1; i>=0; i--) {
19             for(int j=i+1; j<n; j++) {
20                 if(s[i] == s[j]) {
21                     dp[i][j] = dp[i+1][j-1];
22                 } else {
23                     dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
24                 }
25             }
26         }
27         return dp[0][n-1];
28     }
29 };

 

♻️ 优化：

空间复杂度：2维->1维

去掉 i 

压缩所有行到一行。

左下角dp[i+1][j-1]会被上面的dp[i][j-1]覆盖，因此引入变量pre，在更新dp[i][j-1]之前，保存dp[i+1][j-1]

另，在刚开始刷新每行之前，pre的初始化=0；

 

 代码参考：

 1 class Solution {
 2 public:
 3     //status: s[i], s[j]
 4     //dp[i][j]: the min cost to make s[i,j],to a palindrome
 5     //option:
 6     //    case_1: if s[i]==s[j]: dp[i+1][j-1]
 7     //    case_2: if s[i]!=s[j]: min{
 8     //                choose s[i,j-1]: dp[i][j-1]
 9     //                choose s[i+1,j]: dp[i+1][j]
10     //             } + 1: make the left alphbet to a palindrome
11     //base case:
12     //dp[i][i]=0
13     //for: i:i+1->i, j:j-1->j
14     //     i:i--,    j:j++
15     int minInsertions(string s) {
16         int n = s.length();
17         vector<int> dp(n, 0);
18         int tmp;
19         for(int i=n-1; i>=0; i--) {
20             int pre=0;// dp[i+1][j-1]
21             for(int j=i+1; j<n; j++) {
22                 tmp = dp[j];
23                 if(s[i] == s[j]) {
24                     dp[j] = pre;
25                 } else {
26                     dp[j] = min(dp[j], dp[j-1]) + 1;
27                 }
28                 pre = tmp;
29             }
30         }
31         return dp[n-1];
32     }
33 };