力扣5. 最长回文子串C++详解

力扣5. 最长回文子串

注：子数组或者子字符串求解问题一般基本是用DP算法

最长回文子串的解释：正着读和反着读是一样的。

题目解析：

解法一：动态规划

   从回文子串的定义我们可以得出两个结论：

   （1）如果说一个子字符串是回文子串，那么给这个子字符串两边分别加一个数，如果这2个数相等，那么这个新的子字符串也是回文子串。

   （2）回文子串的开始和结束位置的字符一定是相等的。

   我们可以用i来表示一个子字符串的起始位置，j来表示一个子字符串的结束位置，用一个二维数组来存储i和j之间的子字符串是否是回文子串。看到这可以看出这个问题和背包问题很像。

  根据刚才分析得出的结论我们可知：

     dp[i][j] =  dp[i+1][j-1]    &&    i和j位置的值是否相等

     注：dp[i][j]表示以i开头，以j结尾的子字符串是否是回文子串。

     那么我们从哪里进入动规入口呢，很明显我们可以知道：当i和j的位置是同一个时，也就是单个字符时，肯定是一个回文子串。

    因此我们可以现在表中斜对角的地方都先写上T（True），然后进行递推。这里有一个问题，我们的递推顺序（也就是扫描顺序）是怎么样子的？