代码随想录算法训练营第四十四天| 647. 回文子串 516.最长回文子序列

 1 // 要求：找出 正反相等，且连续字符，开始结束位置不同，也认为是一个
 2 // dp[n][n] 起始-中止位置
 3 // 
 4 // 如果两边相等，这两个起始节点相差1个或者0个，那么就直接可以判断是回文
 5 // 如果相差很多，需要看i+1 j-1
 6 // 
 7 //
 8 int countSubstrings(string s) {
 9     if (s.size() == 1) return 1;
10     int result = 0;
11 
12     vector<vector<int>>dp(s.size(), vector<int>(s.size(), false));
13 
14     //起始
15     for (int i = s.size()-1; i >=0; i--)
16     {
17         //中止
18         for (int j = i; j < s.size(); j++)
19         {
20             if (s[i] == s[j])
21             {
22                 if (j - i <= 1)
23                 {
24                     dp[i][j] = true;
25                 }
26                 else
27                 {
28                     dp[i][j] = dp[i + 1][j - 1];
29                 }
30                     
31                 if (dp[i][j])
32                     result++;
33             }
34             
35         }
36     }
37 
38     return result;
39 }