输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

function longestPalindrome(s: string): string {
    // F[i][j]表示从i-j的子串是否是回文串
    // F[i][j] = F[i + 1][j - 1] & s[i] === s[j]
    // 因为i，j要由i+1，j-1推导得到，所以l==1和l==2的情况要单独处理，否则越界
    const n = s.length
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(false))
    let maxlen = 0, startIndex = 0
    // 因为状态回归方程的推倒顺序是从短串到长串，所以要按照长度从1->len进行遍历
    for(let l = 1; l <= n; l++){ // 按照长度进行遍历
        for(let i = 0; i < n; i++){ // i是行号，在每行找到对应长度的长度为1的串
            // 由i和l可以推导j，j是右边界
            let j = l + i - 1
            if(j >= n){ // j越界
                break
            }
            if(l === 1){ // 长度为1的串直接true，也就是矩阵对角线
                dp[i][j] = true
            }else if(l === 2){ // 长度为2的串直接比较s[i] s[j]
                dp[i][j] = s[i] === s[j]
            }else{
                dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j]
            }
            if(l > maxlen && dp[i][j]){
                maxlen = l
                startIndex = i
            }
        }
    }
    return s.slice(startIndex, maxlen + startIndex)
};