力扣链接：5.最长回文子串

难度：⭐⭐

解题关键词：动态规划

解题思路：动态规划，dp[i][j]代表从第 i 个位置到第 j 个位置是否能构成回文子串，能否构成取决于 dp[i+1][j-1]，我们就是从后面往前遍历。

function longestPalindrome(s: string): string {
  const len = s.length;

  const dp = new Array(len).fill(0).map(() => new Array(len).fill(false));
  let result = "";

  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      // 如果两个相等
      if (s[i] === s[j]) {
        // 判断是同一个 / 相邻的两个
        if (j - i <= 1) {
          dp[i][j] = true;
        } else {
          // 判断中间的是否是一个回文
          dp[i][j] = dp[i + 1][j - 1];
        }

        // j - i + 1 就是新的回文串长度，如果比之前碰到的回文串还长，那么就更新
        if (dp[i][j] && j - i + 1 > result.length) {
          result = s.slice(i, j + 1);
        }
      }
    }
  }

  return result;
}