力扣：647. 回文子串

力扣：647. 回文子串
题目：
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

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

解析：

因为是两层for循环实现，所以一开始我就将dp设为二维数组，同时我将其含义视为题目的目的即 i ~ j 字符串中回文字符串的数目。此时思考递归公式即脑海中思考所有可能的情况，然后使用dp来表示出来，看能否表示出来。此时的dp数组就是i~ j-1的回文字符串数目+含有当前值的回文字符串。此时发现还需要一层for循环来将当前值与i~j-1的值进行比较同时判断两值其中是否是回文字符串。可以实现但是很麻烦，这就类似于暴力了。
此时通过此时的dp数组就是i~ j-1的回文字符串数目+含有当前值的回文字符串。这句话想到了何不将dp数组含义定为i~j是否为回文字符串。
其实可以看到正确的dp数组含义与首先思考的dp数组含义相比，正确的更加简单、更加朴素，那么用代码实现题目也会更加简单。
所以dp数组的含义设为true或false时可以解决题目时，那么dp数组就不应该定义和、数量这些复杂的东西等等。

遍历顺序：
从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。所以应该从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

初始化：
举例推导的时候发现遍历时候一开始的几个值并不需要先决条件，可以直接遍历，那么就相当于可以没有特殊的初始化了，只需要将值全部设为false即可。

代码：

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(),false));
        int result = 0;
        for(int i = s.size()-1; i >= 0; --i){
            for(int j = i; j < s.size(); ++j){
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21