【算法day4】最长回文子串——动态规划方法

最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/

动态规划：

1. 回文串即是从前面开始读和从后面开始读，读出来的字符串均相同的字符串，可以理解字符串正中间是一面镜子，镜子的两侧字符串必然对称。
   

2. 实际上回文串如果只含一个字符，必然是回文串；如果含2个字符，若两个字符相等，则必然是回文串，否则不是回文串，例如ab，这就不是回文串，‘bb’就是；

3. 如果含多个字符，那么如果第一位和最后一位字符不相同，那肯定不是回文串（按照上图所示，回文串必然是对称的，如果第一位和最后一位字符不同，那么就必然存在不对称的情况了）

4. 如果含多个字符且第一位和最后一位字符相同，那么，如果它去除掉第一位和最后一位字符后，依然是回文串，那它肯定是回文串；否则，如果它去除掉第一位和最后一位字符后，不是回文串，那说明这个子串肯定不对称，不对称的话肯定就不是回文串了。所以问S[i,j]是不是字串，就要看它的子串S[i+1,j-1]是不是回文串。显然应该用动态规划。

5. 动态规划访问数组的时候一定要按照图里面的。1斜线，2斜线，3斜线……5斜线这个顺序去访问，
   
   否则例如下面图示的这个访问顺序，会出现访问dp[0,3]时，dp[1,2] 没赋值就访问的问题
   

6. vector最好用int，vector<vector<int>>，别用布尔bool，否则难以察觉到自己的算法是否有数组越界的问题。

class Solution {
public:string longestPalindrome(string s) {int s_len = s.size();if (s_len <= 1) {return s;}int max_len = 1, begin = 0; // 最大回文长度和起始位置vector<vector<int>> dp(s_len, vector<int>(s_len));// S[i][i]也就是串的i号位字符，由于所有长度为1的串都是回文，所以是truefor (int i = 0; i < s_len; i++) {dp[i][i] = true;}// 由于s[i][j]回文取决于S[i+1][j-1]是否是回文，所以优先填充斜线// 当前检测的子串长度为Lfor (int L = 2; L <= s_len; L++) {for (int i = 0; i < s_len; i++) {int j = L + i - 1;if (j >= s_len)//子串终点标记j不能大于父串break;if (s[i] == s[j]) {//看看字串是否是回文串if (j - i + 1 <= 2) {//长度2，又有s[i] == s[j],必然是回文串dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}} else {// s[i] != s[j]，出现了不对称的情况，不可能是回文串了dp[i][j] = false;}if (dp[i][j] && max_len < j - i + 1) {// 此次迭代检测到回文串，更新最大值begin = i;max_len = j - i + 1;}}}return s.substr(begin, max_len);}
};