回文子串

题目难度：一星
考察点：回文字符串

方法1：暴力

1. 分析：

算法实现:
(1). 输入字符数s，并获取长度len=s.size()
(2). 按照上述方法进行枚举所有子串,tmp表示区间[i,j]的子串
(3). 判断子串tmp是否为回文字符串，如果是回文字符串的话，结果ans++。
(4). 输出结果ans。

2. 复杂度分析：

3 代码：

1. #include <bits/stdc++.h>
   using namespace std;
   bool check(string s) {
    int len = s.size();
    for(int i=0; i<len/2; i++) if(s[i] != s[len-1-i]) return false;
    return true;
   }
   int main() {
    string s; cin>>s;
    int len = s.size(), ans = 0;
    for(int i=0; i<len; i++) {
        string tmp = "";
        for(int j=i; j<len; j++) {
            tmp += s[j];
            if(check(tmp)) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
   }

方法2：动态规划

1. 
   

   分析：

   上述的暴力算法固然能够解决这个问题，但是我们还是考虑一个更优的算法，动态规划。设dp[i][j]表示区间[i,j]的子串是否为回文字符串，那么对于字符i和字符j就有两种可能：
   (1). s[i] == s[j]， 那么此时dp[i][j] = dp[i+1][j-1];
   (2). s[i] != s[j], 那么此时dp[i][j] = false;
   上面的情况是建立在j-i>=2的情况下，接下来还有两种情况：
   (1). j-i==0， 那么显然一个字符为回文，那么dp[i][j] = true;
   (2). j-i==1， 那么显然判断s[i]是否和s[j]相等，即dp[i][j] = (s[i]==s[j])。
   综上，我们可以列出状态转移方程如下：
   (1) j - i = 0 dp[i][j] = 1;
   (2) j - i = 1 dp[i][j] = (s[i]==s[j]);
   (3) j - i >= 2 dp[i][j] = (dp[i+1][j-1]==1&&s[i]==s[j]);

2. 
   

   复杂度分析：

   时间复杂度：O(n^2)
   空间复杂度：O(n^2)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   int dp[55][55];
   int main() {
    string s; cin>>s;
    int len = s.size(), ans = 0;
    for(int i=len-1; i>=0; i--) {
        for(int j=i; j<len; j++) {
            if(i == j) dp[i][j] = 1;
            else if(j-i==1) dp[i][j] = (s[i]==s[j]);
            else dp[i][j] = (dp[i+1][j-1]==1&&s[i]==s[j]);
            ans += dp[i][j];
        }
    }
    cout<<ans<<endl;
    return 0;
   }