原题连接

如果一个字符串 aba 是一个回文串，那么在它的左右分别添加一个相同的字符 a，那么它一定还是一个回文串 aabaa。

我们可以用dp[i][j] 表示 s 中从 i 到 j (包括 i 和 j) 是否可以形成回文串，将上面这段话翻译成代码，列出状态转移方程。

• dp[i][j] === true 是回文串
• dp[i][j] === false 不是回文串

状态转移方程

s[i] === s[j] && dp[i][j] = dp[i + 1][j - 1]

边界处理

需要考虑 j - i < 2 的情况，此时子串长度为 0 或 1。

例如：a，aa，对称点分别是字符本身和两个字符中间的虚拟点。

双重循环，不断向外延伸尝试得到可能的最大回文串长度。第一层倒着循环，是因为 dp[i] 依赖于 dp[i + 1]。

constlongestPalindrome=function(s){constlen=s.lengthconstdp=Array.from(newArray(len),()=>newArray(len).fill(0))letres=''for(leti=len-1;i>=0;i--){for(letj=i;j<len;j++){dp[i][j]=s[i]===s[j]&&(j-i<2||dp[i+1][j-1])if(dp[i][j]&&j-i+1>res.length){// 符合条件时截取得到最长的回文串res=s.slice(i,j+1)}}}returnres}

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)