字符串的最长回文子串
求字符串的最长回文子串 一般求“最长”这种基本都是用动态规划的思想来求解 我们申请二维数组表示dp[i][j]他表示字符串s[i...j]为回文子串 回文串本身的性质 去掉头、尾仍未回文串 所以状态转移方程dp[i][j] = dp[i+1][j-1] 但是还要注意一个问题 比如字符串 cbbd 此时bb是回文子串 但是此时i在b j也在b 没有i+1 j-1 所以我们要判断下标 看二者是否挨着 也就是j-1-(i+1)+1<2 这种情况 其实对于dp的问题 一般都是在填写一个表格 比如 abcba 这个字符串 比如dp[0][4] 他依赖dp[1][3]的结果 所以我们在填写表格的时候以列的方式填写 也就是填写右上角部分