刷题之动态规划-回文串

前言

大家好，我是jiantaoyab，开始刷动态规划的回文串类型相关的题目

动态规划5个步骤

1. 状态表示 ：dp数组中每一个下标对应值的含义是什么>dp[i]表示什么
2. 状态转移方程： dp[i] 等于什么
3. 1 和 2 是动态规划的核心步骤，第三步是初始化，保证填表的时候不越界
4. 填表顺序：为了保证填写当前状态的时候，所需要的状态已经计算过
5. 返回值

回文子串

题目分析

代码

class Solution {
public:
    int countSubstrings(string s) {
      int n = s.size();
      int ret = 0;
      vector dp(n, vector(n));
      for(int i = n - 1; i >= 0; i--)
      {
        for(int j = i; j  len)
            {
               len = j - i + 1;
               begin = i;
               
            }
           
          }
        }
        return s.substr(begin, len);
    }
};

中心探测法

class Solution {
public:
    string longestPalindrome(string s) {
     string RetStr="";
     for(int i=0;i
         //回文串为奇数
         int left=i-1;
         int right=i+1;
         while(left=0&&right
             left--;
             right++;
         }
         if(RetStr.size()
             //babad
             //01234  letf=-1 i=1  right=3
             RetStr=s.substr(left+1,right-left-1);
         }
        //回文串为偶数
         left=i;
         right=i+1;
           while(left=0&&right
             left--;
             right++;
         }
          if(RetStr.size()
             
             RetStr=s.substr(left+1,right-left-1);
         }
     }
        return RetStr;
    }
};

public:
    bool checkPartitioning(string s) {
      int n = s.size();
      vector
        for(int j = i; j