C++刷leetcode（1312. 让字符串成为回文串的最少插入次数）【动态规划】

糖逗

题目描述：

1. 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
   
2. 
   
3. 请你返回让 s 成为回文串的 最少操作次数 。
   
4. 
   
5. 「回文串」是正读和反读都相同的字符串。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：s = "zzazz"
    
12. 输出：0
    
13. 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
    
14. 示例 2：
    
15. 
    
16. 输入：s = "mbadm"
    
17. 输出：2
    
18. 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
    
19. 示例 3：
    
20. 
    
21. 输入：s = "leetcode"
    
22. 输出：5
    
23. 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
    
24. 示例 4：
    
25. 
    
26. 输入：s = "g"
    
27. 输出：0
    
28. 示例 5：
    
29. 
    
30. 输入：s = "no"
    
31. 输出：1
    
32.  
    
33. 
    
34. 提示：
    
35. 
    
36. 1 <= s.length <= 500
    
37. s&#160;中所有字符都是小写字母。
    
38. 
    
39. 来源：力扣（LeetCode）
    
40. 链接：https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome
    
41. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minInsertions(string s) {
   
4.         int len = s.size();
   
5.         vector<vector<int> > dp(len, vector<int>(len, 0));
   
6.         for(int i = 0; i < len; i++)dp[i][i] = 1;
   
7.         for(int i = len-1; i >= 0; i--){
   
8.             for(int j = i+1; j < len; j++){
   
9.                 if(s[i] == s[j]){
   
10.                     dp[i][j] = dp[i+1][j-1] + 2;
    
11.                 }else{
    
12.                     dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
    
13.                 }
    
14.             }
    
15.         }
    
16.         return len - dp[0][len-1];
    
17.     }
    
18. };

复制代码

注意事项：
1.返回的是字符串串长度减去字符串最长子序列个数