算法沉淀——动态规划之回文串问题（上）（leetcode真题剖析）

算法沉淀——动态规划之回文串问题

• 01.回文子串
• 02.最长回文子串
• 03.分割回文串 IV
• 04.分割回文串 II
• 05.最长回文子序列
• 06.让字符串成为回文串的最少插入次数

  01.回文子串

  题目链接：https://leetcode.cn/problems/palindromic-substrings/

  给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

  回文字符串 是正着读和倒过来读一样的字符串。

  子字符串 是字符串中的由连续字符组成的一个序列。

  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

  示例 1：

  输入：s = "abc"
  输出：3
  解释：三个回文子串: "a", "b", "c"
  

  示例 2：

  输入：s = "aaa"
  输出：6
  解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
  

  提示：

  • 1 public: int countSubstrings(string s) { int n=s.size(); vector for(int j=i;j if(s[i]==s[j]) dp[i][j]=i+1 public: string longestPalindrome(string s) { int n=s.size(); vector for(int j=i;j if(s[i]==s[j]) dp[i][j]=i+1 public: bool checkPartitioning(string s) { int n=s.size(); vector public: int minCut(string s) { int n=s.size(); vector if(isp[0][i]) dp[i]=0; else{ for(int j=1;j public: int longestPalindromeSubseq(string s) { int n=s.size(); vector dp[i][i]=1; for(int j=i+1;j if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=max(dp[i+1][j],dp[i][j-1]); } } return dp[0][n-1]; } }; public: int minINSErtions(string s) { int n=s.size(); vector for(int j=i+1;j if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]; else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; } } return dp[0][n-1]; } };