题目

中文

image.png

英文

image.png

题解

第一次

dp[i][j]代表字符串s在[i][j]区间子串是否是一个回文串。
状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
即

  1. 当只有一个字符，自然是回文串
  2. 当有两个字符如果相等则也是回文串
  3. 当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-1] 是不是一个回文串。
  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         int n = s.size();
  5.         int ans = 0;
  6.         //从 i 开始的长度为 len 的子串是否是回文子串
  7.         vector<vector<bool>>dp(n, vector<bool>(n , false));
  8.         for( int j=0; j< n;j++){
  9.             for (int i =0;i <= j; i++){
  10.                 if(s[i]==s[j] &&(j-i < 2 ||dp[i+1][j - 1])){
  11.                     dp[i][j]=true;
  12.                     ans++;
  13.                 }
  14.             }
  15.         }
  17.         return ans;
  18.     }
  19. };

看到有小马拉大车 中心扩展等方法。 下次一试。