DP：回文串模型

一、回文子串

. - 力扣（LeetCode）

 该题有3种解法

（1）中心扩展算法（在字符串章节有介绍）时间复杂度O（N^2）,空间复杂度O（1）

（2）马丁车算法（专门用来解决回文串问题，但是适用返回太窄）时间复杂度O（N）,空间复杂度O（N）

（3）动态规划（可以将所有回文信息都保存在dp表中）时间复杂度O（N^2）,空间复杂度O（N^2）

这边重点介绍动态规划的做法。

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（ifalse

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp表中true的个数

class Solution {
public:
    int countSubstrings(string s) {
      //动态规划的做法
      int ret=0;
      //s[i]==s[j]  1、i==j  2、i+1==j  3、dp[i+1][j-1]?
      int n=s.size();
      vector dp(n,vector(n));
      //只要右上半区 
      for(int i=n-1;i>=0;--i)  //要从下往上  左右无所谓，因为用不到
        for(int j=i;j=0;--i)
      for(int j=i;jmin(dp[i,j-1],dp[i+1][j])+1 
(2)s[i]==s[j]——>
 
      i==j  0
 
      i+1==j   0
 
      dp[i+1][j-1]
 
3、初始化
 
初始化为0 
 
4、填表顺序
 
下往上，左到右
 
5、返回值
 
dp[0][n-1]
 
class Solution {
public:
    int minInsertions(string s) {
       int n=s.size();
       vector dp(n,vector(n));
       for(int i=n-1;i>=0;--i)
         for(int j=i+1;j